传送门: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;
}
分类: 文章

quhengyi11

喵(ฅ>ω<*ฅ)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *