树链剖分裸题。。。不多说。。 代码如下：
;mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-3;const int MAXN=50000+10;head[MAXN], cnt, tot;int siz[MAXN], top[MAXN], fa[MAXN], w[MAXN], son[MAXN], dep[MAXN];int sum[MAXN<<2];struct node{int u, v, w, next;}edge[MAXN<<1];void add(int u,int v, int w){edge[cnt].u=u;edge[cnt].v=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;}void init(){memset(head,-1,sizeof(head));cnt=tot=0;memset(dep,0,sizeof(dep));memset(son,0,sizeof(son));memset(sum,0,sizeof(sum));}void dfs1(int u, int p){siz[u]=1;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==p) continue ;fa[v]=u;dep[v]=dep[u]+1;dfs1(v,u);siz[u]+=siz[v];if(siz[son[u]]<siz[v])son[u]=v;}}void dfs2(int u, int tp){w[u]=++tot;top[u]=tp;if(son[u]) dfs2(son[u],tp);for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v!=fa[u]&&v!=son[u])dfs2(v,v);}}struct Line_Tree{void PushUp(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];}void Update(int p, int x, int l, int r, int rt){if(l==r){sum[rt]=x;return ;}int mid=l+r>>1;if(p<=mid) Update(p,x,lson);else Update(p,x,rson);PushUp(rt);}int Query(int ll, int rr, int l, int r, int rt){if(ll<=l&&rr>=r){return sum[rt];}int mid=l+r>>1, ans=0;if(ll<=mid) ans+=Query(ll,rr,lson);if(rr>mid) ans+=Query(ll,rr,rson);return ans;}}lt;int solve(int u, int v){int f1=top[u], f2=top[v], ans=0;while(f1!=f2){if(dep[f1]<dep[f2]){swap(u,v);swap(f1,f2);}ans+=lt.Query(w[f1],w[u],root);u=fa[f1];f1=top[u];}if(u==v) return ans;if(dep[u]<dep[v]) swap(u,v);return ans+lt.Query(w[son[v]],w[u],root);}int main(){int n, m, i, j, x, u, v, c, id;while(scanf(“%d%d”,&n,&m)!=EOF){init();for(i=1;i<n;i++){scanf(“%d%d%d”,&u,&v,&c);add(u,v,c);add(v,u,c);}dfs1(1,-1);dfs2(1,1);for(i=0;i<cnt;i+=2){u=edge[i].u;v=edge[i].v;if(dep[u]<dep[v]) swap(u,v);lt.Update(w[u],edge[i].w,root);}while(m–){scanf(“%d”,&x);if(x){scanf(“%d%d”,&u,&v);printf(“%d\n”,solve(u,v));}else{scanf(“%d%d”,&id,&c);u=edge[id-1<<1].u;v=edge[id-1<<1].v;if(dep[u]<dep[v]) swap(u,v);lt.Update(w[u],c,root);}}}return 0;}
，孜孜不倦的追求奋斗，加油。
