提交记录

#include<bits/stdc++.h>
using namespace std;
int n,m;
string s;
int dep[500015],jump[500015][20];//dep[x]为x到根的距离，jump[x][y]为x上方第2^y个祖先 
int a[500015],b[500015];//a是树上差分数组，b是节点访问顺序
vector<int>e[500015];//vector建边
void dfs(int u,int f){
	dep[u]=dep[f]+1;
	jump[u][0]=f;
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if(v==f)continue;
		dfs(v,u);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int j=18;j>=0;j--){
		if((dep[x]-dep[y])&(1<<j)){
			x=jump[x][j];
		}
	}
	if(x==y)return x;
	for(int j=18;j>=0;j--){
		if(jump[x][j]!=jump[y][j]){
			x=jump[x][j];
			y=jump[y][j];
		}
	}
	return jump[x][0];
}
void ask(int u,int f){
	for(int i=0;i<e[u].size();i++){
		int v=e[u][i];
		if (v==f) continue;
		ask(v,u);
		a[u]+=a[v];
	}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)cin>>b[i];
for(int i=1;i<n;i++){
	int u,v;
	cin>>u>>v;
	e[u].push_back(v);
	e[v].push_back(u);
}
dfs(1,0);
for(int j=1;j<=18;j++){
	for(int i=1;i<=n;i++){
		jump[i][j]=jump[jump[i][j-1]][j-1];
	}
}
for(int i=1;i<n;i++){
	int x=b[i],y=b[i+1];
	int u=lca(x,y);
	a[x]++;a[y]++;a[u]--;a[jump[u][0]]--;
}
ask(1,0);//a差分数组前缀和处理
for(int i=2;i<=n;i++)a[i]--;//2~n-1每个点都多走了一次，所以处理一下
for(int i=1;i<=n;i++)cout<<a[i]<<'\n';//最后输出答案即可
return 0;
}