题目大意：
数据范围：如题面。
题解：
第一想法是一个复杂度踩标程的算法.....
就是每种政党建一棵虚树，然后对于每棵虚树都暴力求直径就好了，复杂度是$O(n)$的。
想想就巨难写好么.....
思考这样的问题：我们求直径的第一种方法是任选一个点，然后暴力跑最长链对吧。那么我们不妨设任选这个点是根节点，那么此时的最长链就是不同正当中$dep$最大的一个是吧。
也就是说，我们已经知道了，每个政党的直径的一个端点。
接下来我们就枚举每个点，暴力求它到已知同政党端点的距离，这个用倍增$lca$来求就好。
复杂度$O(nlogn)$。
代码：
#include <bits/stdc++.h>
#define N 200010
using namespace std;
int to[N << 1], nxt[N << 1], head[N], tot;
int f[20][N], dep[N], id[N], a[N], p[N], ans[N];
char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
int rd() {
int x = 0, f = 1;
char c = nc();
while (c < 48) {
if (c == ‘-‘)
f = -1;
c = nc();
}
while (c > 47) {
x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();
}
return x * f;
}
inline void add(int x, int y) {
to[ ++ tot] = y;
nxt[tot] = head[x];
head[x] = tot;
}
void dfs(int p, int fa) {
f[0][p] = fa;
for (int i = 1; i <= 19; i ++ ) {
f[i][p] = f[i-1][f[i-1][p]];
}
dep[p] = dep[fa] + 1;
for (int i = head[p]; i; i = nxt[i]) {
if (to[i] != fa) {
dfs(to[i], p);
}
}
}
int lca(int x, int y) {
if (dep[x] < dep[y]) {
swap(x, y);
}
for (int i = 19; ~i; i -- ) {
if (dep[f[i][x]] >= dep[y]) {
x = f[i][x];
}
}
if (x == y) {
return x;
}
for (int i = 19; ~i; i -- ) {
if (f[i][x] != f[i][y]) {
x = f[i][x];
y = f[i][y];
}
}
return f[0][x];
}
int main() {
int n = rd(), k = rd();
for (int i = 1; i <= n; i ++ ) {
a[i] = rd(), p[i] = rd();
if (p[i]) {
add(p[i], i);
add(i, p[i]);
}
}
dfs(1, 1);
for (int i = 1; i <= n; i ++ ) {
if(dep[id[a[i]]] < dep[i]) {
id[a[i]] = i;
}
}
for (int i = 1; i <= n; i ++ ) {
ans[a[i]] = max(ans[a[i]], dep[id[a[i]]] + dep[i] - 2*dep[lca(id[a[i]], i)]);
}
for (int i = 1; i <= k; i ++ ) {
printf("%d\n", ans[i]);
}
return 0;
}
小结：思考问题一定要相处最简单的方法加以实践。
[bzoj1776][Usaco2010 Hol]cowpol 奶牛政坛_倍增lca
原文：https://www.cnblogs.com/ShuraK/p/11255574.html