题目链接：https://www.luogu.com.cn/problem/P3258

大意：从a1 走到 an，所经过的位置+1，求每个位置的值。

重点在于利用lca进行树上差分，考虑对于x走到y，令x走到公共祖先的点+1，y走到公共祖先的点+1。公共祖先只加一次，所以减去，公共祖先的祖先不参与路径，-1。

最后遍历一遍，递推求和。对于a2 - an，因为之前被当做终点了，终点会在之后+1，所以要减去。

int answer(int x, int fa){
	for(int i=0;i<ve[x].size();i++){
		if(ve[x][i].fi!=fa){
			answer(ve[x][i].fi,x);
			num[x]+=num[ve[x][i].fi];
		}
	}
}

void solve()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int x,y;
	for(int i=1;i<n;i++){
		cin>>x>>y;
		ve[x].push_back(make_pair(y,1));	
		ve[y].push_back(make_pair(x,1));
	}
	dfs(1,0,0);
	
	for(int i=1;i<n;i++){
		int u = a[i],v = a[i+1];
		int t = lca(u,v);
		num[f[t][0]]--;
		num[t]--;
		num[u]++;
		num[v]++;
	}	
	answer(1,0);
	
	for(int i=2;i<=n;i++){
		num[a[i]]--;
	}
	for(int i = 1; i <=n; i++){
		cout<<num[i]<<endl;
	}
}