题解【洛谷P5958】[POI2017]Sabota?

题面

考虑树形 \(\text{DP}\)。

设 \(dp_i\) 为使 \(i\) 变成叛徒的最大值，同时 \(dp_i\) 也是使 \(i\) 不变成叛徒的最小值。

然后考虑如何转移状态。

• 如果 \(i\) 是叶子节点，那么 \(dp_i=1\)；
• 否则，设 \(size_i\) 表示 \(i\) 的子树大小，不难发现 \(dp_i=\max_{j\in son_i}\{\min\{dp_j,\frac{size_j}{size_i-1}\}\}\) 。

如果 \(size_i > k\) ，那么 \(ans = \max\{dp_i\}\)。

#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define itn int
#define gI gi
#define Max(x, y) ((x > y) ? x : y)
#define Min(x, y) ((x < y) ? x : y)

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return f * x;
}

const int maxn = 500003;

int n, k, fa[maxn], sz[maxn], tot, head[maxn], ver[maxn * 2], nxt[maxn * 2];
vector <int> son[maxn];
double dp[maxn], ans; 

void dfs1(int u, int f)
{
    sz[u] = 1;
    for (int i = head[u]; i; i = nxt[i])
    {
        int v = ver[i];
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
    }
}

inline void add(int u, int v) {ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;}

void dfs(int u, int f)
{
    if (sz[u] == 1) {dp[u] = 1.0; return;}
    for (int i = head[u]; i; i = nxt[i])
    {
        int v = ver[i];
        if (v == f) continue;
        dfs(v, u);
    } 
    int len = son[u].size();
    for (int i = 0; i < len; i+=1)
    {
        dp[u] = Max(dp[u], Min(dp[son[u][i]], 1.0 * sz[son[u][i]] / (sz[u] - 1)));
    }
    if (sz[u] > k) ans = max(ans, dp[u]);
}

int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    n = gi(), k = gi();
    for (int i = 1; i < n; i+=1)
    {
        fa[i + 1] = gi();
        son[fa[i + 1]].push_back(i + 1);
        add(i + 1, fa[i + 1]), add(fa[i + 1], i + 1);
    }
    dfs1(1, 0);
    dfs(1, 0);
    printf("%.10lf\n", ans);
    return 0;
}

题解【洛谷P5958】[POI2017]Sabota?

原文：https://www.cnblogs.com/xsl19/p/12283555.html