MnZn 刚学树上差分 $\frac{1}{1145141919810}$ 秒，样例不过求调。

#include<cstdio>
#include<vector>
using namespace std;
const int N=3e5+10; int a[N],d[N],anc[N][30],t[N]; vector<int>g[N];
void dfs(int u,int fa) {
  for(auto v:g[u]) {
  	if(v==fa) continue;
  	d[v]=d[u]+1,anc[v][0]=u,dfs(v,u);
  }
}
int LCA(int u,int v) {
  if(d[u]<d[v]) { u^=v,v^=u,u^=v; }
  for(int i=20;i>=0;i--) if(d[anc[u][i]]>=d[v]) u=anc[u][i];
  if(u==v) return u;
  for(int i=20;i>=0;i--) if(anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i];
  return anc[u][0];
}
void dfs2(int u,int fa) {
  for(auto v:g[u]) {
  	if(v==fa) continue;
  	dfs2(v,u);
	a[u]+=a[v];
  }
}
int main() {
  int n,u,v; scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&t[i]);
  for(int i=1;i<n;i++) {
  	scanf("%d %d",&u,&v);
  	g[u].push_back(v),g[v].push_back(u);
  }
  dfs(1,0);
  for(int j=1;j<=20;j++)
    for(int i=1;i<=n;i++) anc[i][j]=anc[anc[i][j-1]][j-1];
  for(int i=1;i<n;i++) {
  	int tmp=LCA(t[i],t[i+1]);
  	a[t[i]]++,a[t[i+1]]++,a[tmp]--,a[anc[tmp][0]]--;
  }
  dfs2(1,0);
  for(int i=2;i<=n;i++) a[t[i]]--;
  for(int i=1;i<=n;i++) printf("%d\n",a[i]);
  return 0;
}