题解：CF1059E Split the Tree

Left_i_Forever · 2025-11-13 18:39:07 · 题解

调了半天，我是猪猪。

贪心思路：预处理以一个点为一条链的底端，向上最远能延伸到哪里。然后贪心从儿子中找一条能向上最远的链接上，向上长度减一。如果儿子没有链可接，就再起一条。同时记录每个点子树中最少要用几条链。

本体难点在于容易去想单独的以 S 或 L 为贪心。但是两者具有相同的单调性。可以结合起来考虑，用 S 预处理，用 L 贪心和 DP。

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 1e5 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
int n, L, S;
vector <int> v[N];
int a[N], st[N][17], val[N][17], h[N], f[N], maxh[N];

void dfs(int u)
{
    val[u][0] = a[u];
    for (int j = 1; j <= 16; j++)
        st[u][j] = st[st[u][j - 1]][j - 1], val[u][j] = val[u][j - 1] + val[st[u][j - 1]][j - 1];//注意 val[u][i] 是 fa[u]~st[u][i] 整体下移一位的和
    int pos = u, x = 0;
    // cout << u << " " << x << "---\n";
    for (int i = 16; i >= 0; i--)
    {
        // cout << i << "--" << x << " " << pos << " " << st[pos][i] << " " << val[pos][i] + a[st[pos][i]] << "\n";
        if (!st[pos][i] || x + val[pos][i] + a[st[pos][i]] > S) continue;//加上a[st[pos][i]]的值才是真实的
        x += val[pos][i];//避免算重这里不加 a[st[pos][i]]
        pos = st[pos][i];
        h[u] += (1 << i);
    }
    // cout << u << " " << h[u] << "\n";
    h[u] = min (h[u], L - 1);
    maxh[u] = -1;
    for (int j : v[u])
    {
        st[j][0] = u;
        dfs (j);
        f[u] += f[j];
        maxh[u] = max (maxh[j] - 1, maxh[u]);
    }
    if (!f[u]) f[u] = 1, maxh[u] = h[u];
    else
    {
        // f[u]--;
        if (maxh[u] < 0) f[u]++, maxh[u] = h[u];
    }
}

signed main()
{
    cin >> n >> L >> S;
    int maxn = 0;
    for (int i = 1; i <= n; i++) cin >> a[i], maxn = max (maxn, a[i]);
    if (maxn > S) return puts ("-1"), 0;
    for (int i = 2; i <= n; i++)
    {
        int x;
        cin >> x;
        v[x].push_back (i);
    }
    dfs (1);
    // for (int i = 1; i <= n; i++)
    //     cout << h[i] << " " << f[i] << " " << maxh[i] << "\n";
    cout << f[1] << "\n";
    return 0;
}