本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-11 10:36:02

做法

使用差分来做，设 $cf_i$ 表示 $i$ 点到根节点的路径上每一个点加上 $cf_i$。这样对于 $u \rightarrow t$ 的路径上每一个点加一，处理方式如下：

1. $cf_u$ 加一
2. $cf_t$ 加一
3. $cf_{lca(u,t)}$ 减一
4. $cf_{lca(u,t).father}$ 减一

这是十分显然的。然后 dfs 处理出每个点的值大小即可
另外，由于每个 $a_i (i \in [2,n-1])$都算了两次（既做过起点又做过终点），所以这些点要减去 1，对于 $a_n$，因为这个点不需要作为终点单独放置糖，但是计算的时候它被作为终点算了一次，所以也要减去 1。

代码

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=3e5+5;
	int a[maxn];
	int n;
	int head[maxn<<1];
	ll cf[maxn];
	struct EDGE
	{
		int to,nxt;
	}edge[maxn<<1];
	int cnt;
	inline void add(int u,int to)
	{
		edge[++cnt].to=to;
		edge[cnt].nxt=head[u];
		head[u]=cnt;
	}
	int dep[maxn];
	int father[maxn][31];
	void dfs(int u,int fa)
	{
		dep[u]=dep[fa]+1;
		father[u][0]=fa;
		for(int i=1;i<=30;i++)
		{
			father[u][i]=father[father[u][i-1]][i-1];
		}
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==fa)continue;
			dfs(to,u);
		}
	}
	inline int lca(int a,int b)
	{
		if(dep[a]<dep[b])swap(a,b);
		for(int i=30;i>=0;i--)
		{
			if(dep[father[a][i]]>=dep[b])
			{
				a=father[a][i];
			}
		}
		if(a==b)return a;
		for(int i=30;i>=0;i--)
		{
			if(father[a][i]!=father[b][i])
			{
				a=father[a][i];
				b=father[b][i];
			}
		}
		return father[a][0];
	}
	void dfs2(int u,int fa)
	{
		for(int i=head[u];i;i=edge[i].nxt)
		{
			int to=edge[i].to;
			if(to==fa)continue;
			dfs2(to,u);
			cf[u]+=cf[to];
		}
	}
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&a[i]);
		}
		int x,y;
		for(int i=1;i<n;i++)
		{
			scanf("%d%d",&x,&y);
			add(x,y);
			add(y,x);
		}
		dfs(1,0);
		for(int i=1;i<n;i++)
		{
			int as=a[i],bs=a[i+1];
			int _lca=lca(as,bs);
			cf[as]++;
			cf[bs]++;
			cf[_lca]--;
			cf[father[_lca][0]]--;
		}
		dfs2(1,0);
		for(int i=2;i<=n;i++)
		{
			cf[a[i]]--;
		}
		for(int i=1;i<=n;i++)
		{
			printf("%lld\n",cf[i]);
		}
	}
}
int main()
{
	Main::main();
	return 0;
}