一、相关定义
树链剖分：把一棵树剖分为若干条链，然后利用数据结构(树状数组，SBT，Splay，线段树等等)去维护每一条链，复杂度为O(logn)。
树链剖分是解决在树上进行插点问线，插线问点等一系列树上的问题。
假如现在给你一棵树，然后每两条边之间有一个权值，有一些操作，1：x---y之间的最大权值是多少，2：改变x---y之间的权值
当前这样的操作有很多，如果直接用暴力的方法的话肯定不行，那么就要想一个好的方法，我们可以想一下能不能借助线段树解决，能不能想一种方法对树上的边进行编号，然后就变成区间了。那么我们就可以在线段树上进行操作了，树链剖分就是这样的一个算法。
当然编号不是简单的随便编号，如果我们进行随便的编号，然后建立一个线段树，如果要更新一个边的权值，是log2（n）的复杂度，而查找的话，我们要枚举x--y的之间的所有的边，假如我们随便以一个点为根节点进行编号，最大的长度是树的直径，这个值本身是比较大的，而在线段树上查找任意一个区间的复杂度也是log2（n），这样查找一次的时间复杂度比直接暴力还要高，所以很明显是不行的。
那么就要想想办法了，我们能不能把x--y之间的一些边一块儿查找，这就是关于树链剖分的重边和轻边，
重边：某个节点x到孩子节点形成的子树中节点数最多的点child之间的边，由定义发现除了叶子节点其他节点只有一条重边
重边是可以放在一块儿更新的，而有
性质：从根到某一点的路径上轻边、重边的个数都不大于logn。
所以这样查找的时间复杂度相当于log2（n）。
其实树链剖分就是把边哈希到线段树上的数据结构。
实现的话很简单，用两个dfs处理数数的信息，重边以及轻边，然后就是一些线段树的操作了。
二、算法描述
那么，树链剖分的第一步当然是对树进行轻重边的划分。
定义size(x)为以x为根的子树节点个数，令v为u的儿子中size值最大的节点，那么(u,v)就是重边，其余边为轻边。
当然，关于这个它有两个重要的性质：
(1)轻边(u,v)中，size(v)<=size(u/2) //有人纠错为size(v)<=size(u)/2
(2)从根到某一点的路径上，不超过logn条轻边和不超过logn条重路径。
当然，剖分过程分为两次dfs，或者bfs也可以。
如果是两次dfs，那么第一次dfs就是找重边，也就是记录下所有的重边。然后第二次dfs就是连接重边形成重链，具体过程就是：以根节点为起点，沿着重边向下拓展，拉成重链，不在当前重链上的节点，都以该节点为起点向下重新拉一条重链。
剖分完毕后，每条重链相当于一段区间，然后用数据结构去维护，把所有重链首尾相接，放到数据结构上，然后维护整体。
在这里，当然有很多数组，现在我来分别介绍它们的作用：
siz[]数组，用来保存以x为根的子树节点个数
top[]数组，用来保存当前节点的所在链的顶端节点
son[]数组，用来保存重儿子
dep[]数组，用来保存当前节点的深度
fa[]数组，用来保存当前节点的父亲
tid[]数组，用来保存树中每个节点剖分后的新编号
rank[]数组，用来保存当前节点在线段树中的位置
那么，我们现在可以根据描述给出剖分的代码：
第一次dfs：记录所有的重边
void dfs1(int u,int father,int d){ dep[u]=d; fa[u]=father; siz[u]=1; for(int i=head[u];~i;i=next[i]) { int v=to[i]; if(v!=father) { dfs1(v,u,d+1); siz[u]+=siz[v]; if(son[u]==-1||siz[v]>siz[son[u]]) son[u]=v; } }} 第二次dfs：连重边成重链
void dfs2(int u,int tp){ top[u]=tp; tid[u]=++tim; rank[tid[u]]=u; if(son[u]==-1) return; dfs2(son[u],tp); for(int i=head[u];~i;i=next[i]) { int v=to[i]; if(v!=son[u]&&v!=fa[u]) dfs2(v,v); }} 当然，由于题目有时候要求边很多，所以最好不要用二维数组表示边，应用邻接表或者链式前向星。
当然，这里面有一个重要的操作，那就是修改树中边权的值。
如何修改u到v的边权的值呢？这里有两种情况：
(1)如果u与v在同一条重链上，那么就直接修改了
(2)如果u与v不在同一条重链上，那么就一边进行修改，一边将u与v往同一条重链上靠，这样就变成了第一种情况了
那么现在的关键问题就是如何将u和v往同一条重链上靠？这个问题此处我就省略了。
至此，树链剖分原理基本分析完毕！
三、沙场练兵
spoj 375
代码：
#include#include #include #include using namespace std;#define Del(a,b) memset(a,b,sizeof(a))const int N = 10005;int dep[N],siz[N],fa[N],id[N],son[N],val[N],top[N]; //top 最近的重链父节点int num;vector v[N];struct tree{ int x,y,val; void read(){ scanf("%d%d%d",&x,&y,&val); }};tree e[N];void dfs1(int u, int f, int d) { dep[u] = d; siz[u] = 1; son[u] = 0; fa[u] = f; for (int i = 0; i < v[u].size(); i++) { int ff = v[u][i]; if (ff == f) continue; dfs1(ff, u, d + 1); siz[u] += siz[ff]; if (siz[son[u]] < siz[ff]) son[u] = ff; }}void dfs2(int u, int tp) { top[u] = tp; id[u] = ++num; if (son[u]) dfs2(son[u], tp); for (int i = 0; i < v[u].size(); i++) { int ff = v[u][i]; if (ff == fa[u] || ff == son[u]) continue; dfs2(ff, ff); }}#define lson(x) ((x<<1))#define rson(x) ((x<<1)+1)struct Tree{ int l,r,val;};Tree tree[4*N];void pushup(int x) { tree[x].val = max(tree[lson(x)].val, tree[rson(x)].val);}void build(int l,int r,int v){ tree[v].l=l; tree[v].r=r; if(l==r) { tree[v].val = val[l]; return ; } int mid=(l+r)>>1; build(l,mid,v*2); build(mid+1,r,v*2+1); pushup(v);}void update(int o,int v,int val) //log(n){ if(tree[o].l==tree[o].r) { tree[o].val = val; return ; } int mid = (tree[o].l+tree[o].r)/2; if(v<=mid) update(o*2,v,val); else update(o*2+1,v,val); pushup(o);}int query(int x,int l, int r){ if (tree[x].l >= l && tree[x].r <= r) { return tree[x].val; } int mid = (tree[x].l + tree[x].r) / 2; int ans = 0; if (l <= mid) ans = max(ans, query(lson(x),l,r)); if (r > mid) ans = max(ans, query(rson(x),l,r)); return ans;}int Yougth(int u, int v) { int tp1 = top[u], tp2 = top[v]; int ans = 0; while (tp1 != tp2) { //printf("YES\n"); if (dep[tp1] < dep[tp2]) { swap(tp1, tp2); swap(u, v); } ans = max(query(1,id[tp1], id[u]), ans); u = fa[tp1]; tp1 = top[u]; } if (u == v) return ans; if (dep[u] > dep[v]) swap(u, v); ans = max(query(1,id[son[u]], id[v]), ans); return ans;}void Clear(int n){ for(int i=1;i<=n;i++) v[i].clear();}int main(){ //freopen("Input.txt","r",stdin); int T; scanf("%d",&T); while(T--) { int n; scanf("%d",&n); for(int i=1;i