【题解】Split the Tree 树型 dp 贪心 CF1059E ——quhengyi11

传送门：Split the Tree

题意：给棵树，每个点有权值，求把整棵树剖分成最少的路径（路径中每个点必须是深度依次递增的），每条路径上的点数要小于等于 L，路径上所有点的权值和小于等于 S

其实是一道想到题解蛮简单的题啦 QAQ，可惜我比赛的时候调 D 题调了几年（感觉就算让我读到第 E 题也要调几年 QwQ 我数据结构太菜）

考虑以 i 点为起点，往祖先延伸的路径，显然要想让这条路径最有价值我们只需要记录它最高能延伸到的点 (并且不影响全局最优)，记为 $far[i]$

考虑一个点 u，如果它的所有子节点为根的子树的答案已经算出来了，那么它的答案是多少呢？

记当前点 i 为根的子树最长能延伸到点 $path[i]$，容易知道，如果点 u 的所有儿子 v 中有一个点的 $path[v_0]$的深度是小于等于点 u 的，那么点 u 是一定可以被它的一个儿子所在的路径包含的，这时候我们就不需要以 u 为起点新建一条路径，而可以直接更新 $path[u]=max(path[v])$。否则就以 u 为起点建一条新路径，此时 $path[u]=far[u]$

然后你就 AC 了（很水是不是 qwq

代码：

#include<bits/stdc++.h>
#include<iostream>
#define fo(i, a, b) for (ll i = (a); i <= (b); ++i)
#define fd(i, a, b) for (ll i = (a); i >= (b); --i)
#define edge(i, u, v) for (ll i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define inf 1e9
#define ll long long
ll head[N], L, S, n, w[N], x, f[N][20], tot, d[N], up, path[N], sum[N], far[N];
struct Edge{
    ll v, nxt;
}e[N];
inline void addedge (ll u, ll v)
{
    e[++tot] = (Edge) {v, head[u]};
    head[u] = tot;
}
inline void dfs (ll u, ll fa)
{
    f[u][0] = fa;
    d[u] = d[fa] + 1;
    sum[u] = sum[fa] + w[u];
    up = log(n) / log(2);
    fo (i, 1, up)
        f[u][i] = f[f[u][i - 1]][i - 1];
    edge (i, u, v)
        dfs(v, u);
    ll now = u, l = L, s = S;
    fd (i, up, 0)
    {
        if (f[now][i] && (1 << i) < l && sum[now] - sum[f[now][i]] + w[f[now][i]] <= s)
        {
            l -= 1 << i;
            s -= sum[now] - sum[f[now][i]];
            now = f[now][i];
        }
    }
    far[u] = now;
}
inline ll getans (ll u)
{
    ll ret = 0, nowp = 0;
    edge (i, u, v)
    {
        ret += getans(v);
        if (!nowp || d[path[v]] < d[nowp])
        {
            nowp = path[v];
        }
    }
    if (!nowp || d[u] < d[nowp])
    {
        path[u] = far[u];
        ++ret;
    }
    else
        path[u] = nowp;
    return ret;
}
int main ()
{
    scanf("%lld %lld %lld", &n, &L, &S);
    fo (i, 1, n)
    {
        scanf("%lld", &w[i]);
        if (w[i] > S)
        {
            printf("-1");
            return 0;
        }
    }
    fo (i, 2, n)
    {
        scanf("%lld", &x);
        addedge(x, i);
    }
    dfs(1, 0);
    printf("%lld", getans(1));
    /*
    printf("\nsum = ");
    fo (i, 1, n)
        printf("%d ", sum[i]);
    printf("\nfar = ");
    fo (i, 1, n)
        printf("%d ", far[i]);
    printf("\npath = \n");
    fo (i, 1, n)
        printf("%d ", path[i]);
    */
    return 0;
}