LCA的例题

[金杭东]

看题。
这题要用树上差分，我们在 x,y 这两个点加 1 在他俩 LCA 和 LCA 的父亲处减 1 ，然后 dfs 一遍就能计算了，这里给出 dfs 的代码，因为之前有 dfs 只能换个函数名了。

void jhd(int x,int father)
{
	for(auto i:v[x])
	{
		if(i==father) continue;
		jhd(i,x);
		a[x]+=a[i];
	}
}

看第二题。
首先我们肯定选最大生成树上的边。
这里我们多一个倍增数组，记入从 x 向上走 2^i 步这几条边中的最小值。
转移式子比较简单请自行思考。
最后在 LCA 的时候顺便计入答案即可，这里注意图可能不连通，所以 dfs 预处理的时候要注意，那如何判断 -1 呢，不需要额外打个 bfs 来判，这里之前不是求过生成树吗，所以直接 find 一下就行。

不定时更新讲解。