树链剖分

### 树链剖分 --- 树链剖分是把一个树上问题转换为区间问题的方法 例题 [P3384](https://www.luogu.org/problemnew/show/P3384) 考虑一个简化版的问题 给你一棵树，有两种操作： 1.给x的子树每个节点加上a 2.询问x的子树和 我们对这棵树进行dfs遍历，记录下所有节点的dfs序，如下图：  观察任意一个节点的子树的dfs序，可以发现每个子树都是一个区间 于是可以利用这个性质来维护 因为是区间问题，随便套一个数据结构就可以了 接下来我们看链问题的解决方式 如果利用这个性质，我们发现链在这棵树上被分成许多段 如从dfs序6到dfs序9，被分成了 [6],[4],[1-2],[7-9]四段 能不能找出一种dfs的方式，使得被分成的段在平均情况下尽量少呢？ 对于一个显然我们可以用贪心的方式，进行dfs序遍历时优先遍历比较大的子树。而定义对于每一个节点，通往最大的子树的那条边称作重边，最大的子树的顶点叫做重儿子 关于重链，可以看一下这张经典的图，其中加粗的边就是重边，没有点红点的就是重儿子  现在我们来分析一条链最多会被分成几段 对于任意一个有两个子树以上的节点，链都有两个“走向”，一是走非重边，二是走重 有两个重要的定理 1.如果边(u,v)是轻边，那么size(v)<=size(u/2) 2.从根到某节点的路径上，不超过logn条重链和logn条轻链 接下来结合一下代码 代码分为两次dfs，第一次是求出子树大小 代码如下： ```cpp void dfs(int u,int fa) { int i=0; size[u]=1; r[u]=r[fa]+1;//r：深度 father[u]=fa; for(i=first[u];i;i=nxt[i])//对i的每条出边 if(a[i]!=fa) {//若该出边连向儿子 dfs(a[i],u); size[u]+=size[a[i]];//size：子树大小 } } ``` 这部分代码很好理解，不多讲了 接下来是第二次dfs，是对于每个节点，向下拉一条重边