引用到的大佬博客
代码来自：http://blog.csdn.net/jinglinxiao/article/details/72940746
具体算法讲解来自：http://blog.sina.com.cn/s/blog_7a1746820100wp67.html
参考博客： http://www.cnblogs.com/barrier/p/6067964.html
http://www.cnblogs.com/sagitta/p/5660749.html
“在一棵树上进行路径的修改、求极值、求和”乍一看只要线段树就能轻松解决，实际上，仅凭线段树是不能搞定它的。我们需要用到一种貌似高级的复杂算法——树链剖分。
树链，就是树上的路径。剖分，就是把路径分类为重链和轻链。
记siz[v]表示以v为根的子树的节点数，dep[v]表示v的深度(根深度为1)，top[v]表示v所在的链的顶端节点，fa[v]表示v的父亲，son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子），w[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位置。只要把这些东西求出来，就能用logn的时间完成原问题中的操作。
重儿子：siz[u]为v的子节点中siz值最大的，那么u就是v的重儿子。
轻儿子：v的其它子节点。
重边：点v与其重儿子的连边。
轻边：点v与其轻儿子的连边。
重链：由重边连成的路径。
轻链：轻边。
剖分后的树有如下性质：
性质1：如果(v,u)为轻边，则siz[u] * 2 < siz[v]；
性质2：从根到某一点的路径上轻链、重链的个数都不大于logn。
算法实现：
我们可以用两个dfs来求出fa、dep、siz、son、top、w。
dfs_1：把fa、dep、siz、son求出来，比较简单，略过。
dfs_2：⒈对于v，当son[v]存在（即v不是叶子节点）时，显然有top[son[v]] = top[v]。线段树中，v的重边应当在v的父边的后面，记w[son[v]] = totw+1，totw表示最后加入的一条边在线段树中的位置。此时，为了使一条重链各边在线段树中连续分布，应当进行dfs_2(son[v])；
⒉对于v的各个轻儿子u，显然有top[u] = u，并且w[u] = totw+1，进行dfs_2过程。
这就求出了top和w。
将树中各边的权值在线段树中更新，建链和建线段树的过程就完成了。
修改操作：例如将u到v的路径上每条边的权值都加上某值x。
一般人需要先求LCA，然后慢慢修改u、v到公共祖先的边。而高手就不需要了。
记f1 = top[u]，f2 = top[v]。
当f1 <> f2时：不妨设dep[f1] >= dep[f2]，那么就更新u到f1的父边的权值(logn)，并使u = fa[f1]。
当f1 = f2时：u与v在同一条重链上，若u与v不是同一点，就更新u到v路径上的边的权值(logn)，否则修改完成；
重复上述过程，直到修改完成。
求和、求极值操作：类似修改操作，但是不更新边权，而是对其求和、求极值。
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1e4+7; int n; int sz[N]; int fa[N]; //父节点 int son[N]; //重儿子 int d[N]; //深度 int in[N]; //in[i]记录结点i的dfs序 (优先搞定重儿子) ,这决定了该结点在线段树中映射到的位置 int top[N]; //记录结点i所在重链的起始结点 int time_tag; //时间戳 int lt[N]; //仅对重链的起始结点有效 vector<int> adj[N]; struct Edge { int u,v,c; }es[N]; int tree[N<<2]; void dfs1(int u,int father,int deep) //预处理出 fa[],sz[],d[],son[] { d[u]=deep; sz[u]=1; fa[u]=father; for(int v:adj[u]) { if(v==father) continue; dfs1(v,u,deep+1); sz[u]+=sz[v]; if(son[u]==-1||sz[v]>sz[son[u]]) son[u]=v; } } void dfs2(int u) //预处理出in[],top[] { in[u]=++time_tag; if(son[u]!=-1) //存在重儿子 { top[son[u]]=top[u];//同一重链上的top[]相同 dfs2(son[u]); //优先搞重儿子 } for(int v:adj[u]) { if(v==fa[u]||v==son[u]) continue; top[v]=v; //开辟一条新的重链 dfs2(v); } } void update(int rt,int l,int r,int q,int val) { if(l==q&&r==q) { tree[rt]=val; //在线段树的叶子上，记录该结点与重儿子间的边权值 return ; } int mid=(l+r)>>1; if(q<=mid) update(rt<<1,l,mid,q,val); else update(rt<<1|1,mid+1,r,q,val); tree[rt]=max(tree[rt<<1],tree[rt<<1|1]); } int query(int rt,int l,int r,int ql,int qr) //只能对同一条重链上的两个点间的区间最大值进行查询 { if(l>=ql&&r<=qr) return tree[rt]; int mid=(l+r)>>1; if(ql>mid) return query(rt<<1|1,mid+1,r,ql,qr); if(qr<=mid) return query(rt<<1,l,mid,ql,qr); return max(query(rt<<1,l,mid,ql,qr),query(rt<<1|1,mid+1,r,ql,qr)); } void init() { time_tag=0; memset(son,-1,sizeof(son)); for(int i=0;i<=n;i++) adj[i].clear(); top[1]=1; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); init(); for(int i=1;i<n;i++) { int u,v,c; scanf("%d%d%d",&u,&v,&c); es[i]=(Edge){u,v,c}; adj[u].push_back(v); adj[v].push_back(u); } dfs1(1,0,1); dfs2(1); for(int i=1;i<n;i++) { int u=es[i].u,v=es[i].v; if(top[u]==top[v]) //u,v在同一条重链上 { if(d[u]>d[v]) swap(u,v); //使得u在上，v在下 update(1,1,n,in[u],es[i].c); } else //u,v不在同一条重链上 { if(d[u]<d[v]) swap(u,v); //这样，u变成了一条新的重链的起始结点 lt[u]=es[i].c; //lt[u]表示u与父亲结点间的边权值 } } char s[10]; while(~scanf("%s",s)) { if(s[0]=='D') break; if(s[0]=='Q') { int u,v; scanf("%d%d",&u,&v); int ans=0; while(top[u]!=top[v]) { if(d[top[u]]<d[top[v]]) swap(u,v); if(u!=top[u]) ans=max(ans,query(1,1,n,in[top[u]],in[u]-1)); u=top[u]; ans=max(ans,lt[u]); u=fa[u]; } if(d[u]>d[v]) swap(u,v); //使得u在上，v在下，in[u]<in[v] if(u!=v) ans=max(ans,query(1,1,n,in[u],in[v]-1)); printf("%d\n",ans); } else { int x,c; scanf("%d%d",&x,&c); int u=es[x].u,v=es[x].v; if(d[u]>d[v]) swap(u,v); //使得u在上，v在下 if(top[u]==top[v]) update(1,1,n,in[u],c); else lt[v]=c; } } } }