[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)个政党。而且每个政党至少有两只奶牛。 这些政党互相吵闹争。每个政党都想知道自己的“范围”有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。 输入输出格式 输入格式： * Line 1: Two space-separated integers: N and K * Lines 2..N+1: Line i+1 contains two space-separated integers: A_i and P_i 输出格式： * Lines 1..K: Line i contains a single integer that is the range of party i. 输入输出样例 输入样例#1： 6 2 1 3 2 1 1 0 2 1 2 1 1 5 输出样例#1： 3 2
首先需要知道在只有一个政党的情况下，
题目弱化为求一个树中最远的两个点的距离，这个是可以用两遍BFS的方法求出，
具体步骤为：
随便选择一个节点x，BFS求出距离x最远的节点y（有相同的随便选）。
以节点y为起点，BFS求出距离y最远的节点z（有相同的随便选）。
节点y和节点z之间的距离，就是这棵树中最远距离。
有了上面这个之后，在本题中，我们对每个政党都做一遍这个方法即可，
但是我们不能进行BFS了。注意到BFS只是为了求距离最远的点，
那么如果我们可以通过其他方法来求得任意两点间距离的话，步骤就可以转变为：
随便选择该政党的一个节点x，枚举该政党的其他节点，求出距离x最远的节点y。
以节点y为起点，枚举该政党的其他节点，求出距离y最远的节点z。
节点y和节点z的距离，就是该政党的最远距离。
对于求树上任意两点间的距离，一般转化为求LCA的，即
Dist(x, y) = Depth(x) + Depth(y) - 2 * Depth(LCA(x, y))
求LCA的方法有很多，这里就不再描述了。
#include<bits/stdc++.h> using namespace std; const int N=2e5+20; int h[N],n,tot,k; struct node{ int v,ne; }e[N]; void add(int u,int v) { tot++;e[tot]=(node){v,h[u]};h[u]=tot; } int rt,f[N][30],d[N]; vector<int>bg[N/2]; void dfs(int x) { for(int i=h[x];i;i=e[i].ne) { int rr=e[i].v; d[rr]=d[x]+1; dfs(rr); } } int lca(int x,int y) { if(d[x]<d[y]) swap(x,y); int h=d[x]-d[y]; for(int j=27;j>=0;--j) if((1<<j)&h) x=f[x][j]; for(int j=27;j>=0;--j) if(f[x][j]!=f[y][j]) x=f[x][j],y=f[y][j]; if(x==y) return x; else return f[x][0]; } int main() { scanf("%d%d",&n,&k); for(int i=1,x,y;i<=n;++i) { scanf("%d%d",&x,&y); bg[x].push_back(i); if(y) add(y,i),f[i][0]=y; else rt=i; } d[rt]=1;dfs(rt); for(int j=1;j<=27;++j) for(int i=1;i<=n;++i) f[i][j]=f[f[i][j-1]][j-1]; for(int i=1,x,y,z,dis;i<=k;++i) { x=bg[i][0];y=0; for(int j=1;j<bg[i].size();++j) { dis=d[bg[i][j]]+d[x]-2*d[lca(bg[i][j],x)]; if(dis>y) y=dis,z=bg[i][j]; } y=0; for(int j=0;j<bg[i].size();++j) { dis=d[bg[i][j]]+d[z]-2*d[lca(bg[i][j],z)]; if(dis>y) y=dis,x=bg[i][j]; } printf("%d ",y); } return 0; }