P5391 [Cnoi2019]青染之心 题解

stoorz · 2021-03-15 20:20:04 · 题解

设 n 是物品数量，m 是背包容量，Q 是操作次数。

不难发现其实就是按照 dfs 序给出了一棵树，树上每一个点 x 都有一个权值为 v_x，重量为 w_x 的物品，然后把每一个节点到根的路径上的物品拎出来求完全背包。

首先最坏情况就是一条链，时间复杂度显然是 O(Qn) 的，但是我们空间并没办法承受 O(nm) 的复杂度，所以这道题瓶颈在于优化空间。

考虑重链剖分，每一条重链只开一个 dp 数组，因为每一个点到根节点上重链是 O(\log n) 的，所以这样空间是 O(m\log n) 的。

假设我们 dfs 到了点 x，x 位于它到根上第 \text{dep} 条重链，我们先遍历其所有轻儿子 y，用 f[\text{dep}][0\sim m] 更新 f[\text{dep+1}][0\sim m]，然后继续 dfs 节点 y。

回溯回来后 x 子树内就只有 x 的重儿子为根的子树没有被 dp 过了，此时也就意味着可以直接在 f[\text{dep}][0\sim m] 中加入 x 重儿子的贡献了。

时间复杂度 O(Qn)，空间复杂度 O(m\log n)。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=20010,LG=15;
int n,m,Q,tot,v[N],w[N],head[N],son[N],siz[N],id[N],ans[N],f[LG+1][N];
bool vis[N];
char ch[10];
stack<int> st;

struct edge
{
    int next,to;
}e[N];

void add(int from,int to)
{
    e[++tot]=(edge){head[from],to};
    head[from]=tot;
}

void dfs1(int x,int fa)
{
    siz[x]=1; vis[x]=1;
    for (int i=head[x];~i;i=e[i].next)
    {
        int v=e[i].to;
        if (v!=fa)
        {
            dfs1(v,x);
            siz[x]+=siz[v];
            if (siz[v]>siz[son[x]]) son[x]=v;
        }
    }
}

void dfs2(int dep,int last,int x,int fa)
{
    for (int i=0;i<=m;i++)
    {
        f[dep][i]=f[last][i];
        if (i>=w[x]) f[dep][i]=max(f[dep][i],f[dep][i-w[x]]+v[x]);
        ans[x]=max(ans[x],f[dep][i]);
    }
    for (int i=head[x];~i;i=e[i].next)
    {
        int v=e[i].to;
        if (v!=fa && v!=son[x]) dfs2(dep+1,dep,v,x);
    }
    if (son[x]) dfs2(dep,dep,son[x],x);
}

int main()
{
    memset(head,-1,sizeof(head));
    scanf("%d%d",&Q,&m);
    for (int i=1;i<=Q;i++)
    {
        scanf("%s",ch);
        if (ch[0]=='a')
        {
            n++;
            if (st.size()) add(st.top(),n);
            scanf("%d%d",&w[n],&v[n]);
            st.push(n);
        }
        else st.pop();
        if (st.size()) id[i]=st.top();
    }
    for (int i=1;i<=n;i++)
        if (!vis[i]) dfs1(i,0),dfs2(1,0,i,0);
    for (int i=1;i<=Q;i++)
        printf("%d\n",ans[id[i]]);
    return 0;
}