poj2763树链剖分边权+区间和

自己写的比原来的板子常数小了不少嘻嘻，边权处理起来比点权要复杂一下

由于根节点没有被映射的边，其被访问到的顺序是0，直接排除在线段树外

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 100005

struct Edge{

    int to,next;

}edge[maxn<<];

int head[maxn],tot,e[maxn][];

int fa[maxn],son[maxn],num[maxn],deep[maxn];

int top[maxn],p[maxn],fp[maxn],pos;

inline void addedge(int u,int v){

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

void dfs1(int u,int pre,int dep){

    fa[u]=pre;deep[u]=dep;num[u]=;

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].to;

        if(v==pre) continue;

        dfs1(v,u,dep+);

        num[u]+=num[v];

        if(son[u]==- || num[son[u]]<num[v]) son[u]=v;

    }

}

void getpos(int u,int sp){

    top[u]=sp;p[u]=pos++;fp[p[u]]=u;

    if(son[u]==-) return;

    getpos(son[u],sp);

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].to;

        if(v==fa[u] || v==son[u]) continue;

        getpos(v,v);

    }

}

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

int sum[maxn<<];

inline void pushup(int rt){sum[rt]=sum[rt<<]+sum[rt<<|];}

void update(int pos,int val,int l,int r,int rt){

    if(l==r) {sum[rt]=val;return;}

    int m=l+r>>;

    if(pos<=m) update(pos,val,lson);

    else update(pos,val,rson);

    pushup(rt);

}

int query(int L,int R,int l,int r,int rt){

    if(L<=l && R>=r) return sum[rt];

    int m=l+r>>,res=;

    if(L<=m) res+=query(L,R,lson);

    if(R>m) res+=query(L,R,rson);

    return res;

}

int query2(int u,int v){

    int f1=top[u],f2=top[v],res=;

    while(f1!=f2){

        if(deep[f1]<deep[f2]) swap(f1,f2),swap(u,v);

        res+=query(p[f1],p[u],,pos,);

        u=fa[f1],f1=top[u];

    }

    if(u==v) return res;

    if(deep[u]>deep[v]) swap(u,v);

    res+=query(p[son[u]],p[v],,pos,);

    return res;

}

void init(){

    tot=pos=;

    memset(head,-,sizeof head);

    memset(son,-,sizeof head);

    memset(sum,,sizeof sum);

}

int main(){

    int n,q,now,op,a,b;

    while(scanf("%d%d%d",&n,&q,&now)!=EOF){

        init();

        for(int i=;i<n;i++){

            scanf("%d%d%d",&e[i][],&e[i][],&e[i][]);

            addedge(e[i][],e[i][]);addedge(e[i][],e[i][]);

        }

        dfs1(,,);getpos(,);

        for(int i=;i<n;i++){

            if(deep[e[i][]]>deep[e[i][]]) swap(e[i][],e[i][]);

            update(p[e[i][]],e[i][],,pos,);

        }

        while(q--){

            scanf("%d",&op);

            if(op==) {scanf("%d",&a);printf("%d\n",query2(now,a));now=a;}

            else {scanf("%d%d",&a,&b);update(p[e[a][]],b,,pos,);}//第a条边改为b

        }

    }

    return ;

}