松鼠的新家是一棵树，前几天刚刚装修了新家，新家有n个房间，并且有n-1根树枝连接，每个房间都可以相互到达，且俩个房间之间的路线都是唯一的。天哪，他居然真的住在“树”上。松鼠想邀请小熊维尼前来参观，并且还指定一份参观指南，他希望维尼能够按照他的指南顺序，先去a₁，再去a₂，……，最后到a_n，去参观新家。
可是这样会导致维尼重复走很多房间，懒惰的维尼不听地推辞。可是松鼠告诉他，每走到一个房间，他就可以从房间拿一块糖果吃。维尼是个馋家伙，立马就答应了。
现在松鼠希望知道为了保证维尼有糖果吃，他需要在每一个房间各放至少多少个糖果。因为松鼠参观指南上的最后一个房间a_n是餐厅，餐厅里他准备了丰盛的大餐，所以当维尼在参观的最后到达餐厅时就不需要再拿糖果吃了。

第一行一个整数n，表示房间个数
第二行n个整数，依次描述a₁-a_n
接下来n-1行，每行两个整数x，y，表示标号x和y的两个房间之间有树枝相连。

一共n行，第i行输出标号为i的房间至少需要放多少个糖果，才能让维尼有糖果吃。

5
1 4 5 3 2
1 2
2 4
2 3
4 5

1
2
1
2
1

30%的数据，n<=4000
80%的数据，n<=50000
100%的数据，2<= n <=300000

题目分析：

蒟蒻不会写树链剖分 只好写树上差分
对于x,y 我们在sum[x],sum[y]处加1; 在sum[fa[lca(x,y)]],sum[lca(x,y)]处减1;
因为a[2]~a[n]被算了两次，所以最后再减一；

这里为了方便回推，记录了BFS序，即使用BFS预处理LCA

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int a[300100];
int next[600100];
int to[600100];
int que[600100];
int head[300100];
int fa[300100][20];
int deep[300100];
int sum[300100];
queue<int>q;
void bfs()
{
	q.push(1);
	fa[1][0]=0;
	deep[1]=1;
	while(q.size())
	{
		int nmp=q.front();
		q.pop();
		que[++que[0]]=nmp;
		for(int i=head[nmp];i;i=next[i])
			if(to[i]!=fa[nmp][0])
			{
				fa[to[i]][0]=nmp;
				q.push(to[i]);
				deep[to[i]]=deep[nmp]+1;
			}
	}
}
int tot;
void add(int x,int y)
{
	next[++tot]=head[x];
	to[tot]=y;
	head[x]=tot;
}
void work()
{
	for(int j=1;j<=18;j++)
		for(int i=1;i<=n;i++)
			fa[i][j]=fa[fa[i][j-1]][j-1];
}
void Swp(int &x,int &y)
{
    int tmp=x;
    x=y;y=tmp;
    return;
}
int lca(int x,int y)
{
    if(deep[x]<deep[y])Swp(x,y);
    int temp=18;
    while(temp>=0)
    {
        if(deep[fa[x][temp]]>=deep[y])
            x=fa[x][temp];
        temp--;
    }
    if(x==y)return x;
    temp=18;
    while(temp>=0)
    {
        if(fa[x][temp]!=fa[y][temp])
            x=fa[x][temp],y=fa[y][temp];
        temp--;
    }
    return fa[x][0];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	bfs();
	work();
	for(int i=1;i<n;i++)
	{
		int tmp=lca(a[i+1],a[i]);
		sum[tmp]--;sum[fa[tmp][0]]--;
		sum[a[i]]++;sum[a[i+1]]++;
	}
	for(int i=n;i>=1;i--)
		sum[fa[que[i]][0]]+=sum[que[i]];
	for(int i=2;i<=n;i++) sum[a[i]]--;
	for(int i=1;i<=n;i++) printf("%d\n",sum[i]);
	return 0;
}