树链剖分（边）

树链剖分（边）

将边权下放至两端点中深度大的点中，当做点权维护。

#include<iostream>
#include<algorithm>
using namespace std;
#define gc getchar
template<typename T>
inline void read(T&x) {
    int flag=x=0;
    char ch=gc();
    while (ch<'0'||ch>'9')flag|=ch=='-',ch=gc();
    while (ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-48,ch=gc();
    if(flag)x=-x;
}
#define Init(arr,val) memset(arr,val,sizeof(arr))
#define lson (i<<1)
#define rson (i<<1|1)
#define mid ((l+r)>>1)
#define lowbit(x) ((x)&(-x))
const int inf=0x3f3f3f3f,MAXN=1e5+8;
struct E{int x,y,v,nt;}e[MAXN<<1];
int cnt,head[MAXN];
void add(int x,int y,int v){
    e[++cnt].x=x;
    e[cnt].y=y;
    e[cnt].v=v;
    e[cnt].nt=head[x];
    head[x]=cnt;
}
int n,q,s;
int deep[MAXN],fa[MAXN],tot[MAXN],son[MAXN]；
int to_son_val[MAXN];//某点与其重儿子的距离，便于与点权转换。
int dfs1(int now,int pre,int dep){
    deep[now]=dep;fa[now]=pre;tot[now]=1;
    int max_son=-1;
    for(int i=head[now];i;i=e[i].nt){
        int y=e[i].y;
        if(y==pre)continue;
        tot[now]+=dfs1(y,now,dep+1);
        if(tot[y]>max_son)max_son=tot[y],son[now]=y,to_son_val[now]=e[i].v;
    }return tot[now];
}
int top[MAXN],a[MAXN],id[MAXN],num;
void dfs2(int now,int topfa,int v){
    //v；pre->now的距离。
    id[now]=++num;
    top[now]=topfa;
    a[num]=v;
    if(!son[now])return;
    dfs2(son[now],topfa,to_son_val[now]);
    for(int i=head[now];i;i=e[i].nt){
        int y=e[i].y;
        if(!id[y])dfs2(y,y,e[i].v);
    }
}
int sum[MAXN<<2];
inline void up(int i){sum[i]=sum[lson]+sum[rson];}
void build(int i=1,int l=1,int r=n){
    if(l==r){sum[i]=a[l];return;}
    build(lson,l,mid);
    build(rson,mid+1,r);
    up(i);
}
void point_change(int p,int v,int i=1,int l=1,int r=n){
    if(l==r){sum[i]=v;return;}
    if(p<=mid)point_change(p,v,lson,l,mid);
    else point_change(p,v,rson,mid+1,r);
    up(i);
}
int interval_sum(int x,int y,int i=1,int l=1,int r=n){
    if(x<=l&&r<=y)return sum[i];
    int res=0;
    if(x<=mid)res+=interval_sum(x,y,lson,l,mid);
    if(y>mid)res+=interval_sum(x,y,rson,mid+1,r);
    return res;
}
int path_sum(int x,int y){
    //与点权类似，只是最后要减去点lca(x,y)的值。
    int res=0;
    while(top[x]^top[y]){
        if(deep[top[x]]<deep[top[y]])swap(x,y);
        res+=interval_sum(id[top[x]],id[x]);
        x=fa[top[x]];
    }
    if(x^y){//相同的话说明只有lca点的权值没有加上。
        if(deep[x]<deep[y])swap(x,y);
        //y点即是lca，所以不用加上y点的值。
        res+=interval_sum(id[y]+1,id[x]);
    }
    return res;
}
int main(){
    read(n),read(q),read(s);
    int x,y,v;
    for(int i=1;i<n;++i){
        read(x),read(y),read(v);
        add(x,y,v),add(y,x,v);
    }
    dfs1(s,0,1);
    dfs2(s,s,0);
    build();
    int op,i;
    while(q--){
        read(op);
        if(op==1){
            read(i),read(v);
            x=e[i<<1].x,y=e[i<<1].y;
            if(deep[x]>deep[y])point_change(id[x],v);
            else point_change(id[y],v);
        }else{
            read(x);
            printf("%d\n",path_sum(x,s));
            s=x;
        }
    }
    return 0;
}