洛谷2971 [USACO10HOL]牛的政治Cow Politics

原题链接

假设只有一个政党，那么这题就退化成求树的直径的问题了，所以我们可以从此联想至\(k\)个政党的情况。

先处理出每个政党的最大深度，然后枚举每个政党的其它点，通过\(LCA\)计算长度取\(\max\)即可。

因为枚举只是枚举该政党的所有点，所以总的枚举复杂度依旧是\(O(n)\)，总复杂度\(O(nlog_2n)\)。

#include<cstdio>

#include<cmath>

using namespace std;

const int N = 2e5 + 10;

const int M = N << 1;

const int K = 19;

int fi[N], di[M], ne[M], f[N][K], de[N], p[N], ma_p[N], ma_de[N], an[N], gn, l;

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

inline void add(int x, int y)

{

	di[++l] = y;

	ne[l] = fi[x];

	fi[x] = l;

}

inline int maxn(int x, int y)

{

	return x > y ? x : y;

}

inline void sw(int &x, int &y)

{

	int z = x;

	x = y;

	y = z;

}

void dfs(int x)

{

	int i, y;

	if (ma_de[p[x]] < de[x])

	{

		ma_de[p[x]] = de[x];

		ma_p[p[x]] = x;

	}

	for (i = 1; i <= gn; i++)

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

	for (i = fi[x]; i; i = ne[i])

		if (!de[y = di[i]])

		{

			f[y][0] = x;

			de[y] = de[x] + 1;

			dfs(y);

		}

}

int lca(int x, int y)

{

	int i;

	if (de[x] > de[y])

		sw(x, y);

	for (i = gn; ~i; i--)

		if (de[f[y][i]] >= de[x])

			y = f[y][i];

	if (!(x ^ y))

		return x;

	for (i = gn; ~i; i--)

		if (f[x][i] ^ f[y][i])

		{

			x = f[x][i];

			y = f[y][i];

		}

	return f[x][0];

}

int main()

{

	int i, n, m, x, ro;

	n = re();

	m = re();

	gn = log2(n);

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

	{

		p[i] = re();

		x = re();

		if (!x)

		{

			ro = i;

			continue;

		}

		add(i, x);

		add(x, i);

	}

	de[ro] = 1;

	dfs(ro);

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

		an[p[i]] = maxn(an[p[i]], ma_de[p[i]] + de[i] - (de[lca(ma_p[p[i]], i)] << 1));

	for (i = 1; i <= m; i++)

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

	return 0;

}