题面链接

洛谷

sol

这是一篇%这位聚聚的毫无意义的题解。

就是背包，拆点的套路值得学习。

#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gt getchar()
#define ll long long
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
inline int in()
{
    int k=0;char ch=gt;
    while(ch<'-')ch=gt;
    while(ch>'-')k=k*10+ch-'0',ch=gt;
    return k;
}
const int N=4e4+5,K=5e5+5,NK=6e7+5;
using std::vector;
inline void clear(vector<int>&now){vector<int>emp;std::swap(emp,now);}
vector<int>G[N];int w[N],a[N],n,res,cnt,k,fa[N],q1[K<<1],q2[K<<1],h;
int dfn1[N],dfn2[N],df1,df2,siz[N],line[N],is[N],pos1[N],pos2[N],he,ta;
int dp1[NK],dp2[NK];
inline void init()
{
    for(int i=0;i<=cnt;++i)clear(G[i]),is[i]=line[i]=siz[i]=0;
    for(int i=0;i<=(cnt+1)*(k+1);++i)dp1[i]=dp2[i]=0;
    df1=df2=res=cnt=h=0;
}
inline void DP(int *dfn,int *dp)
{
    for(int i=1;i<=cnt;++i)
    {
        int v=dfn[i];he=ta=1;q1[ta]=q2[ta]=0;
        for(int j=1;j<=k;++j)
        {
            he+=q1[he]<j-a[v];int val=dp[(i-1)*(k+1)+j]-j*w[v];
            dp[i*(k+1)+j]=std::max(q2[he]+j*w[v],dp[(i-siz[v])*(k+1)+j]);
            while(he<=ta&&q2[ta]<=val)--ta;q1[++ta]=j,q2[ta]=val;
        }
    }
}
#define v G[u][i]
void dfs1(int u)
{
    siz[u]=1;int sz=G[u].size();
    for(int i=0;i<sz;++i)
        dfs1(v),siz[u]+=siz[v];
    dfn1[++df1]=u,pos1[u]=df1;
}
void dfs2(int u)
{
    int sz=G[u].size();
    for(int i=sz-1;~i;--i)
        line[v]=line[u]+w[v],dfs2(v);
    dfn2[++df2]=u,pos2[u]=df2;
}
#undef v
inline void work()
{
    n=in(),k=in();cnt=n;
    for(int i=1;i<=n;++i)fa[i]=in(),a[i]=in(),w[i]=in(),is[fa[i]]=1;
    for(int i=1;i<=n;++i)
    {
        G[fa[i]].push_back(i);
        if(a[i]>1)a[++cnt]=a[i]-1,a[i]=1,w[cnt]=w[i],G[i].push_back(cnt);
    }
    line[1]=w[1],dfs1(1),dfs2(1);DP(dfn1,dp1),DP(dfn2,dp2);
    for(int i=1;i<=n;++i)
        if(!is[i])
        {
            for(int j=0;j<=k;++j)
                res=std::max(res,dp1[(pos1[i]-1)*(k+1)+j]+
                             line[i]+dp2[(pos2[i]-siz[i])*(k+1)+(k-j)]);
        }
    printf("%d\n",res);
}
int main()
{
    int t=in();
    while(t--)work(),init();
    return 0;
}

SDOI2017苹果树

原文：https://www.cnblogs.com/cx233666/p/9926408.html