【洛谷P3258】松鼠的新家

很好的一道题

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 ;
 }