题意
一个树上每一个点都有一个组别,求相同组别的点对相差的最大距离。
分析
首先对于任意一个组别,深度最大的点一定在答案的点对里。
证明
假设答案的点对里没有深度最大的点,设深度最大的点为 \(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;
}
标签:USACO10HOL,子树内,更优,int,P2971,leq,ch,lca,Politics
From: https://www.cnblogs.com/jiangchenyyds/p/16840927.html