树上求解:差分求交

发布于 2017-10-16  163 次阅读



这个求法非常巧妙:
首先无根树转有根树,
设一个数组c,c[i]表示第i个点到其父亲节点的这条边被经过了c[i]次。
然后,设某起点为p,其终点q,lca(p,q)为LCA,
接下来,运用差分的性质:
使c[p]++,c[q]++,c[LCA]-=2,
然后dfs一遍,dfs代码如下:

void dfs(int u)
{
	for (int i=head[u];i;i=e[i].nxt) //邻接表存储
	{
		int v=e[i].vk;//u的子节点v
		if (v==p[u][0]) continue; //p[u][0]为u的父亲节点
		dfs(v);
		c[u]+=c[v];
		//先递归,后求交
	}
}

简直巧妙。
如果还是不怎么理解的话,看下图