[ABC311Ex] Many Illumination Plans

hikkio / 2023-08-01 / 原文

银牌题，zlt差点ak。

发现我们只关注保留下来的结点，每个保留的结点的父亲是他祖先中第一个保留的结点，则数颜色不同的条件相当于新树相邻结点颜色不同。

考虑dp，设 \(dp_{u,X,0/1}\) 表示 \(u\) 子树内最上方的结点颜色为 \(0/1\)，树的总重量为 \(X\) 的最大价值。每次转移就是暴力做 \((max,+)\) 卷积，或者说合并背包，复杂度是 \(X^2\) 的，总复杂度 \(nX^2\)，无法接受。

我们发现，合并背包的复杂度很大，但是由于 \(n\) 很小，一个一个加入甚至比合并快。这启示我们使用启发式合并。每次继承重儿子的两个背包，对于轻儿子，我们暴力扫一遍，加入之前做的背包，更新当前的背包状态。如果要求解所有子树，保留重儿子的答案，其他子树重新计算即可。

具体的，我们背包传一个大小为 \(X\) 的数组，表示之前做的背包，之后做的背包就以这个背包为基础，得到颜色 \(0/1\) 的两个背包，即为所需要的。

复杂度有证明是 \(\mathcal{O}(n^{1.59}X)\)，但感觉无论怎么想复杂度都不会太高，当它对吧。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=205,inf=1e18;
int n,X,p[maxn],b[maxn],w[maxn],c[maxn],son[maxn],siz[maxn];
vector<int> G[maxn];
void predfs(int u)
{
    siz[u]=1;
    for(int v:G[u])
    {
        predfs(v);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
int ans[maxn];
vector<int> ini;
pair< vector<int>,vector<int> > dfs(int u,vector<int> dp,bool f)
{
    if(f)for(int v:G[u])if(v!=son[u])dfs(v,dp,1);
    vector<int> ndp[2];
    if(!son[u])ndp[0]=ndp[1]=dp;
    else 
    {
        auto pp=dfs(son[u],dp,f);
        ndp[0]=pp.first;
        ndp[1]=pp.second;
        for(int v:G[u])
            if(v!=son[u])
            {
                ndp[0]=dfs(v,ndp[0],0).first;
                ndp[1]=dfs(v,ndp[1],0).second;
            }
    }
    for(int i=0;i<=X-w[u];i++)
    {
        ndp[c[u]][i+w[u]]=max(ndp[c[u]][i+w[u]],ndp[1-c[u]][i]+b[u]);
        if(f)ans[u]=max(ans[u],ndp[1-c[u]][i]+b[u]);
    }
    return {ndp[0],ndp[1]};
}
signed main()
{
    cin>>n>>X;for(int i=2;i<=n;i++)cin>>p[i],G[p[i]].push_back(i);
    for(int i=1;i<=n;i++)cin>>b[i]>>w[i]>>c[i];
    ini=vector<int>(X+1,-inf);ini[0]=0;
    predfs(1);
    dfs(1,ini,1);
    for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
    return 0;
}