P11182 [ROIR 2018 Day2] 分形 题解

· · 题解

前言

本来是在备战 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;
}

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