自动搬运

查看原文

来自洛谷，原作者为

	Little_x_starTYJ 愿时光能缓，愿故人不散！ || 众所周知，如果把灯泡放在嘴里，即使你自己一个人也取得出来灯泡。

搬运于2025-08-24 23:05:00，当前版本为作者最后更新于2024-10-18 16:23:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

本来是在备战 CSP-S 的，无意间翻到了第 $214$ 页，看到开头两道黄，于是就想着刷刷水黄。看完题目发现是八月份我们学校考过的题，只是题目清晰很多，于是就来水一水题解。

解题思路

两黄居然都是贪心？！

不难发现，$T^m$ 的直径需要经过 $T^1$ 的直径。那么我们就可以只考虑在直径的两端添加树。因为在其他地方添加都不是最优的。

很明显，$T^1$ 的直径对 $T^{2\sim m}$ 的答案都是没有贡献的（除非是条链），那么我们只需要找到 $T^1$ 的最长链再接在两端就可以了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
	int k = 0, f = 1;
	char c = getchar();
	while (c < '0' || c > '9')
		f = (f == -1 ? -1 : f), c = getchar();
	while (c >= '0' && c <= '9') {
		k = (k << 1) + (k << 3) + (c ^ 48);
		c = getchar();
	}
	return k * f;
}
inline void write(int k) {
	if (k < 0)
		putchar('-'), k = -k;
	if (k > 9)
		write(k / 10);
	putchar(k % 10 + '0');
}
inline void print(int x, char c = ' ') {
	write(x), putchar(c);
}

const int N = 2e5 + 10;
int ans, dep[N];
vector<int> v[N];
  inline int dfs(int x, int fa) {  //求 T^1 的直径与最长链
	dep[x] = dep[fa] + 1;
	int cd = 0, maxn = 0;
	for (auto u : v[x]) {
		if (u != fa) {
			int k = dfs(u, x);
			if (k > maxn) {
				cd = maxn;
				maxn = k;
			} else if (k > cd)
				cd = k;
		}
	}
	if (cd && maxn)
		ans = max(ans, cd + maxn + 1);
	return maxn + 1;
}
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int n = read(), m = read(), a;
	for (int i = 2; i <= n; i++) {
		a = read();
		v[a].push_back(i);
		v[i].push_back(a);
	}
	dfs(1, 0);
	int tanBing = -1e9;
	for (int i = 1; i <= n; i++) {
		tanBing = max(tanBing, dep[i]);
	}
	if (ans)
		ans = (ans + 2LL * tanBing * (m - 1));
	write(max(ans, 1LL * tanBing * m));
	return 0;
}

额代码是八月份写的，当时还不会求直径（不要问我考场上是怎么写出来的），所以代码写得有点屎。。