树上差分

#include<bits/stdc++.h>

using namespace std;

int n,m,h[600001],e[600001][2],cnt,d[600001],f[600001][25],po[21],num[600001],sum[600001];

inline int read() {
	int x=0;
	char ch=getchar();
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9')
		x=x*10+ch-'0',ch=getchar();
	return x;
}

void add(int x,int y) {
	e[++cnt][0]=y;
	e[cnt][1]=h[x];
	h[x]=cnt;
	e[++cnt][0]=x;
	e[cnt][1]=h[y];
	h[y]=cnt;
}

void init() {
	po[0]=1;
	for(int i=1; i<=20; i++)
		po[i]=po[i-1]*2;
	n=read(),m=read();
	for(int i=1; i<n; i++)
		num[i]=read();
	for(int i=1; i<n; i++)
		add(read(),read());
}

void dfs(int p) {
	for(int i=1; i<=n&&f[f[p][i-1]][i-1]; i++)
		f[p][i]=f[f[p][i-1]][i-1];
	for(int i=h[p]; i; i=e[i][1])
		if(!d[e[i][0]]) {
			d[e[i][0]]=d[p]+1;
			f[e[i][0]][0]=p;
			dfs(e[i][0]);
			sum[p]+=sum[e[i][0]];
		}
}

int lca(int a,int b) {
	if(d[a]!=d[b]) {
		if(d[a]<d[b])
			swap(a,b);
		for(int i=20; i>=0; i--)
			if(f[a][i]&&d[f[a][i]]>=d[b])
				a=f[a][i];
	}
	if(a==b)
		return a;
	for(int i=20; i>=0; i--)
		if(f[a][i]==f[b][i])
			continue;
		else
			a=f[a][i],b=f[b][i];
	return f[a][0];
}

int main() {
	init();
	d[1]=1;
	dfs(1);
	for(int i=1; i<n; i++) {
		int c=lca(num[i],num[i+1]);
		sum[num[i]]++,sum[f[num[i+1]][0]]++,sum[c]--,sum[f[c][0]]--;
	}
	memset(d,0,sizeof(d));
	d[1]=1;
	dfs(1);
	for(int i=1; i<=n; i++)
		printf("%d\n",sum[i]);
}