[文章目录]
Description
农夫约翰的奶牛住在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计算路径。
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 201000
int n,m,root;
int head[N],nxt[N],to[N],cnt;
vector<int>v[N];
inline void add(int x,int y)
{
to[++cnt]=y;
nxt[cnt]=head[x];
head[x]=cnt;
}
int fa[N][20],rt[N],deep[N],col[N];
void dfs(int x)
{
if(deep[x]>deep[rt[col[x]]]) rt[col[x]]=x;
for(int i=head[x];i;i=nxt[i])
{
fa[to[i]][0]=x; deep[to[i]]=deep[x]+1;
dfs(to[i]);
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=18;~i;--i) if(deep[fa[x][i]]>=deep[y]) x=fa[x][i];
if(x==y) return x;
for(int i=18;~i;--i) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int main()
{
scanf("%d%d",&n,&m); int x;
for(int i=1;i<=n;++i)
{
scanf("%d%d",col+i,&x); v[col[i]].push_back(i);
if(x) add(x,i); else root=i;
}
dfs(root);
for(int i=1;i<=18;++i)
for(int j=1;j<=n;++j)
fa[j][i]=fa[fa[j][i-1]][i-1];
for(int i=1;i<=m;++i)
{
int ans=0;
for(int j=0;j!=v[i].size();++j) if(v[i][j]!=rt[i])
ans=max(ans,deep[rt[i]]+deep[v[i][j]]-2*deep[lca(v[i][j],rt[i])]);
printf("%d\n",ans);
}
return 0;
}