题解：洛谷 P2971 [USACO10HOL] Cow Politics G

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P2971 [USACO10HOL] Cow Politics G – 洛谷

【题目描述】

农夫约翰的奶牛住在

n

n

n 片不同的草地上，标号为

1

∼

n

1\\sim n

1∼n。

恰好有

n

−

1

n-1

n−1 条单位长度的双向道路，用各种各样的方法连接这些草地。而且从每片草地出发都可以抵达其他所有草地。也就是说，这些草地和道路构成了一种叫做树的图。输入包含一个详细的草地的集合，详细说明了每个草地的父节点

p

i

p_i

pi​。根节点的

p

i

=

0

p_i=0

pi​=0, 表示它没有父节点。

因为奶牛建立了

1

∼

k

1\\sim k

1∼k 一共

k

k

k 个政党。每只奶牛都要加入某一个政党，其中， 第

i

i

i 只奶牛属于第

a

i

a_i

ai​ 个政党。而且每个政党至少有两只奶牛。 每个政党都想知道自己的“范围”有多大。其中，定义一个政党的范围是这个政党离得最远的两只奶牛（沿着双向道路行走）的距离。

【输入】

第一行两个整数

n

,

k

n,k

n,k。

第

2

∼

n

+

1

2\\sim n+1

2∼n+1 行：第

i

+

1

i+1

i+1 行两个整数

a

i

,

p

i

a_i,p_i

ai​,pi​。

【输出】

一共

K

K

K 行，第

i

i

i 行一个整数表示第

i

i

i 个政党的范围。

【输入样例】

6 2
1 3
2 1
1 0
2 1
2 1
1 5

【输出样例】

3
2

【算法标签】

#普及plus

【代码详解】

#include <bits/stdc++.h>
using namespace std;
const int N = 200005, M = N * 2;
int n, k, root; // n: 节点数，k: 颜色种类数，root: 根节点
int h[N], e[M], ne[M], idx; // 邻接表存储树
int a[N], p; // a: 节点颜色，p: 父节点
int dep[N], fa[N][20], maxx[100005], id[100005], ans[100005]; // dep: 节点深度，fa: 倍增祖先数组，maxx: 每种颜色的最大深度，id: 每种颜色深度最大的节点，ans: 每种颜色的答案
queue<int> q; // BFS队列

// 添加无向边
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

// BFS预处理节点深度、倍增数组，并找到每种颜色深度最大的节点
void bfs(int u)
{
memset(dep, 0x3f, sizeof(dep)); // 初始化深度为无穷大
dep[0] = 0, dep[u] = 1; // 虚拟节点0深度为0，根节点深度为1
q.push(u);

while (!q.empty())
{
int t = q.front();
q.pop();
// 更新当前颜色的最大深度和对应的节点
if (maxx[a[t]] < dep[t])
{
maxx[a[t]] = dep[t]; // 更新最大深度
id[a[t]] = t; // 记录深度最大的节点
}

for (int i = h[t]; i != –1; i = ne[i]) // 遍历子节点
{
int j = e[i];
if (dep[j] > dep[t] + 1) // 如果j未被访问
{
dep[j] = dep[t] + 1; // 计算深度
q.push(j);
fa[j][0] = t; // j的2^0祖先为t
for (int k = 1; k < 20; k++) // 预处理倍增数组
{
fa[j][k] = fa[fa[j][k – 1]][k – 1];
}
}
}
}
}

// 求节点x和y的最近公共祖先
int lca(int x, int y)
{
if (dep[x] < dep[y]) // 保证x深度较大
swap(x, y);

// 将x向上跳，使x和y深度相同
for (int k = 19; k >= 0; k—)
{
if (dep[fa[x][k]] >= dep[y])
x = fa[x][k];
}

if (x == y) // 如果x等于y，说明y是x的祖先
return x;

// x和y同时向上跳，直到找到最近公共祖先的下一层
for (int k = 19; k >= 0; k—)
{
if (fa[x][k] != fa[y][k])
{
x = fa[x][k];
y = fa[y][k];
}
}
return fa[x][0]; // 返回最近公共祖先
}

int main()
{
cin >> n >> k; // 输入节点数和颜色种类数
memset(h, –1, sizeof(h)); // 初始化邻接表

for (int i = 1; i <= n; i++) // 输入每个节点的颜色和父节点
{
cin >> a[i] >> p;
if (p != 0) // 如果有父节点，添加边
add(i, p), add(p, i);
else // 否则是根节点
root = i;
}

bfs(root); // BFS预处理

// 计算每种颜色的答案：同颜色节点间的最大距离
for (int i = 1; i <= n; i++)
{
int p_1 = i; // 当前节点
int p_2 = id[a[i]]; // 当前颜色深度最大的节点
int l = lca(p_1, p_2); // 求最近公共祖先
int t = dep[p_1] + dep[p_2] – 2 * dep[l]; // 计算距离
ans[a[i]] = max(ans[a[i]], t); // 更新答案
}

for (int i = 1; i <= k; i++) // 输出每种颜色的答案
cout << ans[i] << endl;

return 0;
}

【运行结果】

6 2
1 3
2 1
1 0
2 1
2 1
1 5
3
2