LCA【洛谷P2971】 [USACO10HOL]牛的政治Cow Politics

P2971 [USACO10HOL]牛的政治Cow Politics

农夫约翰的奶牛住在N (2 <= N <= 200,000)片不同的草地上，标号为1到N。恰好有N-1条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合，详细说明了每个草地的父节点P_i (0 <= P_i <= N)。根节点的P_i == 0, 表示它没有父节点。因为奶牛建立了1到K一共K (1 <= K <= N/2)个政党。每只奶牛都要加入某一个政党，其中， 第i只奶牛属于第A_i (1 <= A_i <= K)个政党。而且每个政党至少有两只奶牛。 这些政党互相吵闹争。每个政党都想知道自己的“范围”有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。

先找到每个政党中深度最大的点。

在枚举别的点求LCA距离即可。

思路很妙啊。

code：

#include <iostream>

#include <cstdio>

using namespace std;

const int wx=200017;

inline int read(){

	int sum=0,f=1; char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}

	while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}

	return sum*f;

}

int num,n,k;

int ans[wx],head[wx],a[wx],zmj[wx];

int dep[wx],f[wx][23];

struct e{

	int nxt,to;

}edge[wx*2];

void add(int from,int to){

	edge[++num].nxt=head[from];

	edge[num].to=to;

	head[from]=num;

}

void dfs(int u,int fa){

	dep[u]=dep[fa]+1;

	for(int i=head[u];i;i=edge[i].nxt){

		int v=edge[i].to;

		if(v==fa)continue;

		f[v][0]=u;

		dfs(v,u);

	}

}

int LCA(int x,int y){

	if(dep[x]<dep[y])swap(x,y);

	for(int i=21;i>=0;i--)if(dep[f[x][i]]>=dep[y])x=f[x][i];

	if(x==y)return x;

	for(int i=21;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];

	return f[x][0];

}

void pre(){

	for(int j=1;j<=21;j++)

		for(int i=1;i<=n;i++)

			f[i][j]=f[f[i][j-1]][j-1];

}

int find_ans(int x,int y){

	return dep[x]+dep[y]-2*dep[LCA(x,y)];

}

int main(){

	n=read(); k=read();

	for(int i=1;i<=n;i++){

		a[i]=read();

		int x;x=read();

		if(x==0)continue;

		add(x,i); add(i,x);

	}

	dfs(1,0); pre();

	for(int i=1;i<=n;i++)

		if(dep[i]>dep[zmj[a[i]]])

			zmj[a[i]]=i;

	for(int i=1;i<=n;i++)

		ans[a[i]]=max(ans[a[i]],find_ans(zmj[a[i]],i));

	for(int i=1;i<=k;i++)

		printf("%d\n",ans[i]);

	return 0;

}