树上求解：差分求交

这个求法非常巧妙：
首先无根树转有根树，
设一个数组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];
		//先递归，后求交
	}
}

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