容易发现是树剖裸题。
然后毒瘤选手AKC表示好像可以用树上差分+LCA做。
就这样。水题。
诶那你咋没秒切。
妈也看错样例，然后画错图，接着就是理解错题目，最后R成傻逼之时发现我ST表开数组的顺序错了。。。
废物。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct node { int x,y,next; }a[610000];int len,last[310000]; void ins(int x,int y) { len++; a[len].x=x;a[len].y=y; a[len].next=last[x];last[x]=len; } int Bin[30],f[310000][30]; int dep[310000]; void dfs(int x) { for(int i=1;i<=25;i++) if(dep[x]>=Bin[i])f[x][i]=f[f[x][i-1]][i-1]; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=f[x][0]) { f[y][0]=x; dep[y]=dep[x]+1; dfs(y); } } } int LCA(int x,int y) { if(dep[x]<dep[y])swap(x,y); for(int i=25;i>=0;i--) if(dep[x]-dep[y]>=Bin[i])x=f[x][i]; if(x==y)return x; for(int i=25;i>=0;i--) if(f[x][i]!=f[y][i]&&dep[x]>=Bin[i]) x=f[x][i], y=f[y][i]; return f[x][0]; } //------LCA--------- int ch[310000]; int tmp[310000]; void update(int x) { for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=f[x][0]) { update(y); tmp[x]+=tmp[y]; } } } int main() { int n,x,y; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&ch[i]); len=0;memset(last,0,sizeof(last)); for(int i=1;i<n;i++) { scanf("%d%d",&x,&y); ins(x,y);ins(y,x); } //----sc---- Bin[0]=1;for(int i=1;i<=25;i++)Bin[i]=Bin[i-1]*2; dep[1]=1;f[1][0]=0;dfs(1); for(int i=1;i<=n-1;i++) { tmp[ch[i]]++; tmp[ch[i+1]]++; int lca=LCA(ch[i],ch[i+1]); tmp[lca]--; if(f[lca][0]!=0)tmp[f[lca][0]]--; } update(1); tmp[ch[1]]++; for(int i=1;i<=n;i++)printf("%d ",tmp[i]-1); return 0; }