树链剖分模板

树链剖分的目的：1.维护树/路径上的信息

2.将树剖分成若干条链，用数据结构去维护链上的信息，复杂度为O(logn)

过程：2次BFS

第一次BFS找出所有节点的重儿子(子节点数最多的儿子)，并更新相关信息

第二次BFS将所有的重儿子连成链，赋予新的标记，并记录对应的原标记

图中红色的链即为一条重边(重儿子连成的链)

int dep[MAX];//节点的深度
int fa[MAX];//节点的父亲节点
int siz[MAX];//节点的儿子个数（子节点个数）
int son[MAX];//节点的重儿子

int top[MAX];//这条链的顶端节点
int tid[MAX];//按照链顺序的新编号
int rank1[MAX];//新编号对应的原编号

模板如下:

 1 //树链剖分模板
 2 //dfs1
 3 int dep[MAX];//节点的深度
 4 int fa[MAX];//节点的父亲节点
 5 int siz[MAX];//节点的儿子个数（子节点个数）
 6 int son[MAX];//节点的重儿子
 7 //dfs2
 8 int top[MAX];//这条链的顶端节点
 9 int tid[MAX];//按照链顺序的新编号
10 int rank1[MAX];//新编号对应的原编号
11 
12 void dfs1(int u,int father,int d)//分出重儿子
13 {
14     dep[u]=d;
15     fa[u]=father;
16     siz[u]=1;
17     for(int i=head[u];~i;i=next1[i])
18     {
19         int v=to[i];
20         if(v!=father)
21         {
22             dfs1(v,u,d+1);
23             siz[u]+=siz[v];
24             if(son[u]==-1||siz[v]>siz[son[u]])
25             {
26                 son[u]=v;
27             }
28         }
29     }
30 }
31 
32 void dfs2(int u,int tp)//连点成链
33 {
34     top[u]=tp;
35     tid[u]=++tim;
36     rank1[tid[u]]=u;
37     if(son[u]==-1) return;
38     dfs2(son[u],tp);
39     for(int i=head[u];~i;i=next1[i])
40     {
41         int v=to[i];
42         if(v!=son[u]&&v!=fa[u])
43         {
44             dfs2(v,v);
45         }
46     }
47 }