【博客】树链剖分学习笔记

---同步发表于本人博客---

---安利一波浙江省选2019游记---

这里就不写具体实现了...只是为刚看懂什么是树链剖分的同学提供习题

其实树剖部分都差不多的，关键是线段树

可以把这里面5题A了大概就可以熟悉树链剖分了...

（头文件被吃掉了，但不是重点qaq,有不会的可以评论留言，或者加我QQ：1134524176）

T1:LuoguP3384 【模板】树链剖分

都说了是模板，那就是模板咯...

考虑线段树实现区间加、区间和，又是线段树模板...

树剖跳的时候，因为要更新子树，然后这里更新的话直接idx[x]+sz[x]-1就可以了（因为这些编号是相连的）

取模不要漏！！！

// luogu-judger-enable-o2
#include
#include
#include
#include
#define int long long
using namespace std;
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans*f;
}const int M=300005;
int n,m,head[M<<1],ver[M<<1],nxt[M<<1],tot,son[M],dep[M],sz[M],idx[M],fa[M],tp[M],root,ha,a[M],b[M],sum[M<<2],lz[M<<2],rk[M];
inline void add(int x,int y){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;}
void dfs1(int x,int f){
    sz[x]=1,fa[x]=f,dep[x]=dep[f]+1;
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==f) continue;
        dfs1(ver[i],x);
        sz[x]+=sz[ver[i]];
        if(sz[ver[i]]>sz[son[x]]) son[x]=ver[i];
    }
}int t;
void dfs2(int x,int topf){
    tp[x]=topf;idx[x]=++t;a[t]=b[x];rk[t]=x;
    if(!son[x]) return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nxt[i])
        if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
}
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
inline void Push_Up(int i){sum[i]=(sum[ls]+sum[rs]+ha)%ha;}
inline void Push_Down(int i,int l,int r){
    if(!lz[i]) return;
    sum[ls]=(sum[ls]+lz[i]*(mid-l+1)%ha)%ha,sum[rs]=(sum[rs]+lz[i]*(r-mid)%ha)%ha;
    lz[ls]=(lz[ls]+lz[i])%ha,lz[rs]=(lz[rs]+lz[i])%ha,lz[i]=0;
}
void Build(int i,int l,int r){
    if(l==r){sum[i]=a[l];return;}
    Build(ls,l,mid),Build(rs,mid+1,r);
    Push_Up(i);
}
void Update(int i,int l,int r,int ql,int qr,int z){
    if(ql<=l&&r<=qr){sum[i]=((r-l+1)*z+sum[i])%ha;lz[i]=(lz[i]+z)%ha;return;}
    Push_Down(i,l,r);
    if(ql<=mid) Update(ls,l,mid,ql,qr,z);
    if(qr>mid)  Update(rs,mid+1,r,ql,qr,z);
    Push_Up(i);
}
int Query(int i,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sum[i];
    Push_Down(i,l,r);int s=0;
    if(ql<=mid) s=(s+Query(ls,l,mid,ql,qr))%ha;
    if(qr>mid)  s=(s+Query(rs,mid+1,r,ql,qr))%ha;
    Push_Up(i);
    return s;
}
void Query_1(int x,int y,int val){
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
        Update(1,1,n,idx[tp[x]],idx[x],val);
        x=fa[tp[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    Update(1,1,n,idx[x],idx[y],val);
}
void Query_2(int x,int y){
    int Ans=0;
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
        Ans=(Ans+Query(1,1,n,idx[tp[x]],idx[x]))%ha;
        x=fa[tp[x]];
    }if(dep[x]>dep[y]) swap(x,y);
    Ans=(Ans+Query(1,1,n,idx[x],idx[y]))%ha;
    printf("%lld\n",Ans);
}
void Query_3(int x,int y){Update(1,1,n,idx[x],idx[x]+sz[x]-1,y%ha);}
void Query_4(int x){printf("%lld\n",Query(1,1,n,idx[x],idx[x]+sz[x]-1));}
int Q_d(int i,int l,int r,int p){
    if(l==r)return sum[i];
    Push_Up(i);
    if(p<=mid) return Q_d(ls,l,mid,p);
    else return Q_d(rs,mid+1,r,p);
}
signed main(){
    n=read(),m=read(),root=read(),ha=read();
    for(int i=1;i<=n;++i) b[i]=read();
    for(int i=1,x,y,z;i<n;++i){x=read(),y=read(),add(x,y),add(y,x);}
    dfs1(root,0),dfs2(root,root),Build(1,1,n);
    while(m--){int opt=read(),x,y,z;
        if(opt==4)    x=read(),Query_4(x);
        else{x=read(),y=read();
            if(opt==3) Query_3(x,y%ha);
            else if(opt==2) Query_2(x,y);
            else z=read(),Query_1(x,y,z%ha);
        }
    }return 0;
}

T2:LuoguP4114 Qtree1

单调修改+区间查询，线段树是板子不讲了

树剖部分：因为修改的是加边的时候的第k条边，就用到链式前向星的性质了...自己手推一下应该改哪条边即可

（我的代码线段树打的是区间修改还支持区间加的...主要是模板懒得改了，不影响树剖部分的阅读性）

// luogu-judger-enable-o2
#include
#include
#include
#define int long long
using namespace std;
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans*f;
}const int M = 100005;char opt[10];
int n,head[M<<1],ver[M<<1],nxt[M<<1],val[M<<1],tot,fa[M],dep[M],sz[M],b[M],a[M],son[M],idx[M],tp[M],mx[M<<2],lz1[M<<2],lz2[M<<2],rk[M],x,y,z;
inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];val[tot]=z;head[x]=tot;}
void dfs1(int x,int f){
    dep[x]=dep[f]+1;sz[x]=1;fa[x]=f;
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==f) continue;
        b[ver[i]]=val[i],dfs1(ver[i],x),sz[x]+=sz[ver[i]];
        if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i];
    }
}int t;
void dfs2(int x,int topf){
    tp[x]=topf;idx[x]=++t;a[t]=b[x];
    if(!son[x]) return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nxt[i])
        if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
}
#define ls (i<<1)
#define rs (i<<1|1)
#define mid (l+r>>1)
inline void Push_Up(int i){mx[i]=max(mx[ls],mx[rs]);}
inline void Push_Down(int i){
    if(lz1[i]!=-1)
        mx[ls]=mx[rs]=lz1[ls]=lz1[rs]=lz1[i],lz2[ls]=lz2[rs]=0,lz1[i]=-1;
    if(!lz2[i]) return;
    lz2[ls]+=lz2[i],lz2[rs]+=lz2[i];
    mx[ls]+=lz2[i],mx[rs]+=lz2[i],lz2[i]=0;
}
void Build(int i,int l,int r){lz1[i]=-1;
    if(l==r){mx[i]=a[l];return;}
    Build(ls,l,mid),Build(rs,mid+1,r);
    Push_Up(i);
}
void Update_1(int i,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){mx[i]=x;lz1[i]=x,lz2[i]=0;return;}
    Push_Down(i);
    if(ql<=mid) Update_1(ls,l,mid,ql,qr,x);
    if(qr>mid)  Update_1(rs,mid+1,r,ql,qr,x);
    Push_Up(i);
}
void Update_2(int i,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){mx[i]+=x;lz2[i]+=x;return;}
    Push_Down(i);
    if(ql<=mid) Update_2(ls,l,mid,ql,qr,x);
    if(qr>mid)  Update_2(rs,mid+1,r,ql,qr,x);
    Push_Up(i);
}
int Query(int i,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return mx[i];
    int ans=0;Push_Down(i);
    if(ql<=mid) ans=max(ans,Query(ls,l,mid,ql,qr));
    if(qr>mid)  ans=max(ans,Query(rs,mid+1,r,ql,qr));
    return Push_Up(i),ans;
}
inline void Change(int x,int y){if(dep[ver[2*x-1]]<dep[ver[2*x]]) x=ver[2*x];else x=ver[2*x-1];Update_1(1,1,n,idx[x],idx[x],y);}
inline void Max(int x,int y){
    int maxn=0,t=0;
    if(x==y) puts("0");
    if(x==y) return;
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
        t=Query(1,1,n,idx[tp[x]],idx[x]);
        maxn=max(maxn,t);
        x=fa[tp[x]]; 
    }if(dep[x]>dep[y]) swap(x,y);
    t=Query(1,1,n,idx[x]+1,idx[y]);maxn=max(t,maxn);
    printf("%lld\n",maxn);
}
signed main(){
    n=read();
    for(int i=1;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    dfs1(1,0);dfs2(1,1);Build(1,1,n);
    while(1){
        scanf("%s",opt);
        if(opt[1]=='O') return 0;
        if(opt[1]=='H')x=read(),y=read(),Change(x,y);
        else x=read(),y=read(),Max(x,y);
    }
    return 0;
}

T3:LuoguP4315 月下“毛景树”

知道为什么上一题要写区间加了吗...因为我是先做这题才做上面那题的!!!

难点是线段树，开两个lazy_tag(lz1,lz2),lz1记录区间覆盖,lz2记录区间加，更新顺序很重要，不过这是线段树部分注意的，这里既然是江树剖，那就不具体讲实现线段树了

#include
#include
#include
#define int long long
using namespace std;
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans*f;
}const int M = 100005;char opt[10];
int n,head[M<<1],ver[M<<1],nxt[M<<1],val[M<<1],tot,fa[M],dep[M],sz[M],b[M],a[M],son[M],idx[M],tp[M],mx[M<<2],lz1[M<<2],lz2[M<<2],rk[M],x,y,z;
inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];val[tot]=z;head[x]=tot;}
void dfs1(int x,int f){
    dep[x]=dep[f]+1;sz[x]=1;fa[x]=f;
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==f) continue;
        b[ver[i]]=val[i],dfs1(ver[i],x),sz[x]+=sz[ver[i]];
        if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i];
    }
}int t;
void dfs2(int x,int topf){
    tp[x]=topf;idx[x]=++t;a[t]=b[x];
    if(!son[x]) return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nxt[i])
        if(!idx[ver[i]]) dfs2(ver[i],ver[i]);
}
#define ls (i<<1)
#define rs (i<<1|1)
#define mid (l+r>>1)
inline void Push_Up(int i){mx[i]=max(mx[ls],mx[rs]);}
inline void Push_Down(int i){
    if(lz1[i]!=-1)
        mx[ls]=mx[rs]=lz1[ls]=lz1[rs]=lz1[i],lz2[ls]=lz2[rs]=0,lz1[i]=-1;
    if(!lz2[i]) return;
    lz2[ls]+=lz2[i],lz2[rs]+=lz2[i];
    mx[ls]+=lz2[i],mx[rs]+=lz2[i],lz2[i]=0;
}
void Build(int i,int l,int r){lz1[i]=-1;
    if(l==r){mx[i]=a[l];return;}
    Build(ls,l,mid),Build(rs,mid+1,r);
    Push_Up(i);
}
void Update_1(int i,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){mx[i]=x;lz1[i]=x,lz2[i]=0;return;}
    Push_Down(i);
    if(ql<=mid) Update_1(ls,l,mid,ql,qr,x);
    if(qr>mid)  Update_1(rs,mid+1,r,ql,qr,x);
    Push_Up(i);
}
void Update_2(int i,int l,int r,int ql,int qr,int x){
    if(ql<=l&&r<=qr){mx[i]+=x;lz2[i]+=x;return;}
    Push_Down(i);
    if(ql<=mid) Update_2(ls,l,mid,ql,qr,x);
    if(qr>mid)  Update_2(rs,mid+1,r,ql,qr,x);
    Push_Up(i);
}
int Query(int i,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return mx[i];
    int ans=0;Push_Down(i);
    if(ql<=mid) ans=max(ans,Query(ls,l,mid,ql,qr));
    if(qr>mid)  ans=max(ans,Query(rs,mid+1,r,ql,qr));
    return Push_Up(i),ans;
}
inline void Change(int x,int y){if(dep[ver[2*x-1]]<dep[ver[2*x]]) x=ver[2*x];else x=ver[2*x-1];Update_1(1,1,n,idx[x],idx[x],y);}
inline void Cover(int x,int y,int z){
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
        Update_1(1,1,n,idx[tp[x]],idx[x],z);
        x=fa[tp[x]];
    }if(dep[x]>dep[y]) swap(x,y);
    Update_1(1,1,n,idx[x]+1,idx[y],z);
}
inline void Add(int x,int y,int z){
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
        Update_2(1,1,n,idx[tp[x]],idx[x],z);
        x=fa[tp[x]];
    }if(dep[x]>dep[y]) swap(x,y);
    Update_2(1,1,n,idx[x]+1,idx[y],z);
}
inline void Max(int x,int y){
    int maxn=0,t=0;
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
        t=Query(1,1,n,idx[tp[x]],idx[x]);
        maxn=max(maxn,t);
        x=fa[tp[x]]; 
    }if(dep[x]>dep[y]) swap(x,y);
    t=Query(1,1,n,idx[x]+1,idx[y]);maxn=max(t,maxn);
    printf("%lld\n",maxn);
}
signed main(){
    n=read();
    for(int i=1;i<n;++i)x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
    dfs1(1,0);dfs2(1,1);Build(1,1,n);
    while(1){
        scanf("%s",opt);
        if(opt[1]=='t') return 0;
        if(opt[1]=='h')x=read(),y=read(),Change(x,y);
        else if(opt[1]=='o')x=read(),y=read(),z=read(),Cover(x,y,z);
        else if(opt[1]=='d')x=read(),y=read(),z=read(),Add(x,y,z);
        else x=read(),y=read(),Max(x,y);
    }
    return 0;
}

T4:[ZJOI2008]树的统计

还是板子啊...不讲了...ZJOI也是有简单的时候的啊！

（这是很久很久以前码的...可能码风比较神奇）

// luogu-judger-enable-o2
#include
#include
#include
#include
#define int long long 
#define inf 1000000000
using namespace std;
inline int read(){
    char chr=getchar();    int f=1,ans=0;
    while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
    return ans*f;
}
void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
const int M=300005;
int n,head[M<<1],nxt[M<<1],ver[M<<1],son[M],ttot,fa[M],dfn[M],top[M],d[M],tot[M],a[M],b[M],cnt,sum[M<<1],t[M<<1];
inline void add(int x,int y){ver[++ttot]=y;nxt[ttot]=head[x];head[x]=ttot;}
void dfs1(int x,int ff){
    d[x]=d[ff]+1;tot[x]=1;fa[x]=ff;
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==ff) continue;
        dfs1(ver[i],x);
        tot[x]+=tot[ver[i]];
        if(tot[son[x]]<tot[ver[i]]) son[x]=ver[i];
    }
}
void dfs2(int x,int topf){
    dfn[x]=++cnt;a[cnt]=b[x];top[x]=topf;
    if(son[x]) dfs2(son[x],topf);
    for(int i=head[x];i;i=nxt[i])
        if(!dfn[ver[i]])    dfs2(ver[i],ver[i]);
}
#define ls i<<1
#define rs i<<1|1
inline void Push_Up(int i){t[i]=max(t[ls],t[rs]);sum[i]=sum[ls]+sum[rs];}
void Build(int i,int l,int r){
    if(l==r){t[i]=sum[i]=a[l];return;}int mid=l+r>>1;
    Build(ls,l,mid);Build(rs,mid+1,r);
    Push_Up(i);
}
int Query_Max(int i,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)    return t[i];
    int maxn=-inf,mid=l+r>>1;
    if(ql<=mid) maxn=max(Query_Max(ls,l,mid,ql,qr),maxn);
    if(qr>mid)  maxn=max(Query_Max(rs,mid+1,r,ql,qr),maxn);
    return maxn;
}
int Query_Sum(int i,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)    return sum[i];
    int ans=0,mid=l+r>>1;
    if(ql<=mid) ans+=Query_Sum(ls,l,mid,ql,qr);
    if(qr>mid)  ans+=Query_Sum(rs,mid+1,r,ql,qr);
    return ans;
}
void Updata(int i,int l,int r,int pos,int x){
    if(l==r){t[i]=sum[i]=x;return;}
    int mid=l+r>>1;
    if(pos<=mid) Updata(ls,l,mid,pos,x);
    else        Updata(rs,mid+1,r,pos,x);
    Push_Up(i);
}
inline void Tree_Sum(int x,int y){
    int ans=0;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        ans+=Query_Sum(1,1,n,dfn[top[x]],dfn[x]);
        x=fa[top[x]];
    }if(d[x]>d[y]) swap(x,y);
    ans+=Query_Sum(1,1,n,dfn[x],dfn[y]);
    printf("%lld\n",ans);
}
inline void Tree_Max(int x,int y){
    int ans=-inf;
    while(top[x]!=top[y]){
        if(d[top[x]]<d[top[y]]) swap(x,y);
        ans=max(Query_Max(1,1,n,dfn[top[x]],dfn[x]),ans);
        x=fa[top[x]];
    }if(d[x]>d[y]) swap(x,y);
    ans=max(Query_Max(1,1,n,dfn[x],dfn[y]),ans);
    printf("%lld\n",ans);
}int x,y,T;char opt[100];
signed main(){
    n=read();
    for(int i=1;i<n;i++)    x=read(),y=read(),add(x,y),add(y,x);
    for(int i=1;i<=n;i++)    b[i]=read();
    dfs1(1,0),dfs2(1,1);Build(1,1,n);T=read();
    while(T--){
        scanf("%s",opt+1);x=read(),y=read();
        if(opt[strlen(opt+1)]=='X')    Tree_Max(x,y);
        else if(opt[strlen(opt+1)]=='M')    Tree_Sum(x,y);
        else Updata(1,1,n,dfn[x],y);
    }
    return 0;
}

T5:P4949 最短距离

基环树上的树剖

把非树边拎出来单独计算即可

非树边可以在dfs1的时候记录下来...

之后这条边就不算进去了，每次询问和更改都单独处理这条边，分类讨论即可

Tip:我的线段树打法因为传参多，常数有点大...但是貌似比一些写树状数组的人还要快好多...

#include
#include
#include
#define int long long
using namespace std;
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans*f;
}const int M=500010;
int aa[M],bb[M];
int n,m,head[M<<1],ver[M<<1],nxt[M<<1],val[M<<1],tot=1,b[M],idx[M],dep[M],son[M],fa[M],sz[M],ext,frm[M<<1],tp[M],mn[M<<2],a[M],x,y,z,opt;
inline void add(int x,int y,int z){ver[++tot]=y,nxt[tot]=head[x],val[tot]=z,frm[tot]=x,head[x]=tot;}
void dfs1(int x,int f){
    dep[x]=dep[f]+1,sz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        if(f==ver[i]) continue;
        if(dep[ver[i]]){ext=i;continue;}
        b[ver[i]]=val[i];fa[ver[i]]=x;
        dfs1(ver[i],x);sz[x]+=sz[ver[i]];
        if(sz[son[x]]<sz[ver[i]]) son[x]=ver[i];
    }
}int t;
void dfs2(int x,int topf){
    idx[x]=++t;tp[x]=topf;a[t]=b[x];
    if(!son[x]) return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nxt[i])
        if(!idx[ver[i]]&&i!=ext) dfs2(ver[i],ver[i]);
}
#define ls (i<<1)
#define rs (i<<1|1)
#define mid (l+r>>1)
void Push_Up(int i){mn[i]=mn[ls]+mn[rs];}
void Build(int i,int l,int r){
    if(l==r){mn[i]=a[l];return;}
    Build(ls,l,mid),Build(rs,mid+1,r);
    Push_Up(i);
}
void Update(int i,int l,int r,int p,int x){
    if(l==r){mn[i]=x;return;}
    if(p<=mid)  Update(ls,l,mid,p,x);
    else         Update(rs,mid+1,r,p,x);
    Push_Up(i);
}
int Query(int i,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return mn[i];
    int ans=0;
    if(ql<=mid) ans+=Query(ls,l,mid,ql,qr);
    if(qr>mid)  ans+=Query(rs,mid+1,r,ql,qr);
    return ans;
}
void Change(int x,int z){
    int y=bb[x];x=aa[x];
    if(x==ver[ext]&&y==frm[ext]||x==ver[ext^1]&&y==frm[ext^1]){val[ext]=val[ext^1]=z;return;}
    if(dep[x]<dep[y]) x=y;
    Update(1,1,n,idx[x],z);
}
int Sum(int x,int y){
    int sum=0;
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]<dep[tp[y]]) swap(x,y);
        sum+=Query(1,1,n,idx[tp[x]],idx[x]);
        x=fa[tp[x]];
    }if(dep[x]>dep[y]) swap(x,y);
    sum+=Query(1,1,n,idx[x]+1,idx[y]);
    return sum;
}
void Q_Min(int x,int y){
    int ans=Sum(x,y);
    int t1=Sum(x,frm[ext])+Sum(ver[ext],y)+val[ext];
    int t2=Sum(x,ver[ext])+Sum(frm[ext],y)+val[ext];
    ans=min(t1,ans);
    ans=min(t2,ans);
    printf("%lld\n",ans);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)    x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z),aa[i]=x,bb[i]=y;
    dfs1(1,0);dfs2(1,1);Build(1,1,n);
    while(m--){
        opt=read();x=read(),y=read();
        if(opt==1) Change(x,y);
        else Q_Min(x,y);
    }
    return 0;
}