树链部分

说句闲话

这个东西已经20多天没写了，感觉已经忘没了，非常糟糕，只好赶快补一补，确实还是得多打代码，不然都忘光就丸辣。

前言

树链问题通常是关于树上路径的操作，将路径拆分成一条条链，然后用线段树维护链的权值。

注：本题解并不适用于毫无基础的oier，只是做简单讲解，想了解具体定义请自行查阅。

2次dfs成链

第一次

我们先用第一次 dfs 找到每个节点的以下东西（不懂先放着，继续向下看）：

• 节点深度：为了查路径时确定哪个作为起点终点及先动深度更深的点。

• 节点大小：一个子树是一个连续的dfs序，为了操作整颗子树。

• 父节点：当达到链顶时为了转移到另一个链上。

• 重儿子：为了形成重链。

void dfs1(int x,int f,int d){//当前节点，父节点，深度
	deep[x]=d;//深度 
	siz[x]=1;//大小 
	fa[x]=f;//父节点 
	int mxson=-1;//重儿子大小 
	for(int y:v[x]){
		if(y==f)
			continue;
		dfs1(y,x,d+1);
		siz[x]+=siz[y];
		if(siz[y]>mxson){//比当前已有重儿子更大，更新 
			son[x]=y;
			mxson=siz[y]; 
		} 
	}
}