洛谷P3354 [IOI2005]Riv 河流——“承诺”DP

题目：https://www.luogu.org/problemnew/show/P3354

状态中要记录一个“承诺”，只需相同承诺之间相互转移即可；

然后就是树形DP的套路了。

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

typedef long long ll;

int n,m,head[],ct,siz[],fa[],len[];

ll ed[],f[][][][];//点，伐木场个数，前伐木场，是否有伐木场

ll a[],c[][];//c:从i到j代价

struct N{

    int to,next;

    ll w;

    N(int t=,int n=,ll w=):to(t),next(n),w(w) {}

}edge[];

void init(int cr,int cnt,ll dis,int nw)

{

    c[cr][cnt]=dis*a[cr];

    if(cnt)f[cr][][cnt][]=c[cr][cnt];

    if(!nw)

    {

        len[cr]=cnt;return;

    }

    init(cr,cnt+,dis+ed[nw],fa[nw]);

}

void dfs(int x)

{

    siz[x]=;

    for(int j=;j<=n;j++)f[x][j][][]=;

    for(int k=;k<=len[x];k++)f[x][][k][]=;

    for(int i=head[x],v;i;i=edge[i].next)

    {

        dfs(v=edge[i].to);

        for(int j=min(m,siz[x]+siz[v]);j>=;j--)

        {

            for(int k=;k<=len[x];k++)

            {

                f[x][j][k][]+=min(f[v][][k+][],f[v][][k+][]);

                f[x][j][k][]+=min(f[v][][][],f[v][][][]);

                for(int l=max(,j-siz[x]);l<=j&&l<=siz[v];l++)

                {

                    f[x][j][k][]=min(f[x][j][k][],f[x][j-l][k][]+min(f[v][l][k+][],f[v][l][k+][]));

                    f[x][j][k][]=min(f[x][j][k][],f[x][j-l][k][]+min(f[v][l][][],f[v][l][][]));

                }

            }

        }

        siz[x]+=siz[v];

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int i=,x;i<=n;i++)

    {

        scanf("%lld%d%lld",&a[i],&x,&ed[i]);

        edge[++ct]=N(i,head[x],ed[i]);head[x]=ct;

        fa[i]=x;

    }

    memset(f,,sizeof f);f[][][][]=;//!

    for(int i=;i<=n;i++)init(i,,,i);

    dfs();

    printf("%lld",f[][m][][]);

    return ;

}