P2971 [USACO10HOL]Cow Politics G

· · 题解

题意

一个树上每一个点都有一个组别，求相同组别的点对相差的最大距离。

分析

首先对于任意一个组别，深度最大的点一定在答案的点对里。

证明

假设答案的点对里没有深度最大的点,设深度最大的点为 x,设点对中的点为 y,z，假设 d[y]\leq d[z]\leq d[x] ，t 为 y,z 的 lca。

1.若 z,y 属于 t 的不同子树，因为 d[y]\leq d[x]，d[z]\leq d[x] ，若 x 不在 t 的子树内，那么，把 y 换为 x 会更优。若 x 在 t 的子树内，如果 lca(x,z)=t，显然可以将 y 换成 x。如果 lca(x,z)\ne t，那么很明显，将 z 换成 x 一定比点对 y,z 的答案更优，或者点对 x,z 比点对 x,y 更优，显然不论哪种情况，x 都在答案里。

2.若 z,y 属于 t 的同一棵子树，即 y=t，因为 d[y]\leq d[x]，d[z]\leq d[x] ，若 x 不在 y 的子树内，那么把 y 换成 x 会更优，若在 y 子树内，那么显然把 z 换成 x 更优。

所以，对于不同组别，我们只需要求出深度最大的点即可，在 O(n) 枚举每一个点，与同组别深度最大的点求一遍 lca 更新答案。

code

#include<bits/stdc++.h>
#define N 200005
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*f;
}
queue<int> q;
int n,k,root,tot,t;
int a[N],p[N],d[N],f[N][25],maxd[N],ans[N],pos[N];
int Head[N],to[N<<1],Next[N<<1];
void add(int u,int v){to[++tot]=v,Next[tot]=Head[u],Head[u]=tot;}
void bfs(int s){
    q.push(s);d[s]=1,maxd[a[s]]=1;
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=Head[x];i;i=Next[i]){
            int y=to[i];if(d[y]) continue;
            d[y]=d[x]+1,f[y][0]=x;
            if(maxd[a[y]]<d[y]) pos[a[y]]=y;
            maxd[a[y]]=max(maxd[a[y]],d[y]);
            for(int j=1;j<=t;j++) f[y][j]=f[f[y][j-1]][j-1];
            q.push(y); 
        }
    }
}
int lca(int x,int y){
    if(d[x]>d[y]) swap(x,y);
    for(int j=t;j>=0;--j)
        if(d[f[y][j]]>=d[x]) y=f[y][j];
    if(x==y) return x;
    for(int j=t;j>=0;--j)
        if(f[y][j]!=f[x][j]) x=f[x][j],y=f[y][j];
    return f[x][0];
}
int DIS(int x,int y){return d[x]+d[y]-2*d[lca(x,y)];}
signed main(){
    n=read(),k=read();
    for(int i=1;i<=n;++i){
        a[i]=read(),p[i]=read();
        if(p[i]==0) root=i;
        else add(i,p[i]),add(p[i],i);
    }
    t=log(n)/log(2)+1;
    bfs(root);
    for(int i=1;i<=n;++i) ans[a[i]]=max(ans[a[i]],DIS(pos[a[i]],i));
    for(int i=1;i<=k;++i) printf("%d\n",ans[i]);
    return 0;
}