一：用处
对一棵树分成几条链，把树形变为线性，减少处理难度
需要处理的问题：
1.将树从x到y结点最短路径上所有节点的值都加上z
2.求树从x到y结点最短路径上所有节点的值之和
3.将以x为根节点的子树内所有节点值都加上z
4.求以x为根节点的子树内所有节点值之和
二：相关概念：
1.重儿子：对于每一个非叶子节点，它的儿子中以那个儿子为根的子树节点数（包括自身）最大的儿子为该节点的重儿子
2.轻儿子：非重儿子
3.重边：一个父节点与其重儿子的连边
4.轻边：非重边
5.重链：相邻重边相连形成的链
tips：叶子结点若为轻儿子，则自成一条长度为1的链
重链以轻儿子或根节点为起点
三：常规操作
1.预处理
（1）dfs1：
处理：
各点深度； 各点重儿子编号； 各点最大子树大小 ；各点父亲
代码：
void dfs1(int now,int fa,int deep)
{
siz[now]=1;
fat[now]=fa;
dep[now]=deep;
zs=-1;
for(int i=head[now];i;i=nxt[i])
{
if(to[i]==now)
continue; //别忘了
dfs1(to[i],now,deep+1);
siz[now]+=siz[to[i]];
if(siz[to[i]]>zs)//处理重儿子
zhoson[now]=to[i],zs=siz[to[i]];
}
}
（2）dfs2
处理：
标记每个点的新编号
赋值每个点的初始值到新编号上
处理每个点所在链的顶端
处理每条链
顺序规定：先重后轻
代码：
void dfs2(int now,int top) { tp[now]=top; id[now]=++cnt; wt[cnt]=w[x]; if(!zhoson[now]) return; dfs2(zhoson[now],top); for(int i=head[now];i;i=nxt[i]) { if(to[i]==fat[now]||to[i]==zhoson[now]) continue; dfs2(to[i],to[i]); } }
原文：https://www.cnblogs.com/charlesss/p/10474190.html