很好的一道题
LCA+树上前缀和
sum数组是前缀和数组，
分类讨论一下，
1.访问到一个点p1，若下一个点p2需要往儿子下面找的话，那么lca就是这个点p1，则sum[p1]--; sum[p2]++;
2.访问到一个点p1，若下一个点p2需要往父亲上找的话，那么lca就是p2,则sum[f[p2][0]]--; sum[f[p1][0]]++
3.访问到一个点p1，若下一个点p2需要跨过p1,p2的lca的话，则sum[lca]--; sum[f[lca][0]]--; sum[p1]++; sum[p2]++;
需要注意的就是判重（有些地方会重复加）
#include<cstdio>
#include<cstring>
using namespace std;
const int N=,p=;
int n,size,head[N<<],a[N];
int nxt[N<<],to[N<<];
int father[N][p+],sum[N],cnt[N],deep[N];
void swap(int &a,int &b){
int tmp=a;
a=b;
b=tmp;
}
void uni(int x,int y){
size++;
nxt[size]=head[x];
head[x]=size;
to[size]=y;
}
void dfs(int fa,int x){
for (int k=head[x];k;k=nxt[k]){
int y=to[k];
if (y==fa)
continue;
deep[y]=deep[x]+;
father[y][]=x;
dfs(x,y);
}
}
void pre(){
for (int j=;j<=p;j++)
for (int i=;i<=n;i++)
father[i][j]=father[father[i][j-]][j-];
}
int LCA(int x,int y){
if (deep[x]<deep[y])
swap(x,y);
int d=deep[x]-deep[y];
for (int j=p;j>=;j--)
if (d&(<<j))
x=father[x][j];
if (x==y)
return x;
for (int j=p;j>=;j--)
if (father[x][j]!=father[y][j]){
x=father[x][j];
y=father[y][j];
}
return father[x][];
}
void Dfs(int fa,int x){
if (!nxt[head[x]]&&x!=){
cnt[x]=sum[x];
return;
}
for (int k=head[x];k;k=nxt[k]){
int y=to[k];
if (fa==y)
continue;
Dfs(x,y);
cnt[x]+=cnt[y];
}
cnt[x]+=sum[x];
}
int main(){
int x,y;
size=;
scanf("%d",&n);
for (int i=;i<=n;i++)
scanf("%d",&a[i]);
for (int i=;i<n;i++){
scanf("%d %d",&x,&y);
uni(x,y);
uni(y,x);
}
deep[]=;
dfs(,);
pre();
int lca=LCA(a[],a[]);
sum[a[]]++;
sum[a[]]++;
sum[lca]--;
sum[father[lca][]]--;
for (int i=;i<n;i++){
x=a[i];
y=a[i+];
int lca=LCA(x,y);
if (x==lca){//down
sum[x]--;
sum[y]++;
}
else if (y==lca){//up
sum[father[y][]]--;
sum[father[x][]]++;
}
else{
sum[y]++;
sum[father[x][]]++;
sum[lca]--;
sum[father[lca][]]--;
}
}
Dfs(,);
cnt[a[n]]--;
for (int i=;i<=n;i++)
printf("%d\n",cnt[i]);
return ;
}