【[IOI2005]Riv 河流】

趁魏佬去英语演讲了，赶快%%%%%%%%%%%%%%魏佬

基本上是照着魏佬的代码写的

这其实还是一个树上背包

我们用\(dp[i][j][k]\)表示在以\(i\)为根的子树里，我们修建\(k\)个伐木场，且\(i\)这个节点的树木我们运到\(j\)，也就是说在\(j\)上修建了一个伐木场，但是这个\(j\)并不包含在\(k\)中，除非\(j=i\)

显然这又变成一个树上背包了

具体看注释吧

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define maxn 105

#define min(a,b) ((a)<(b)?(a):(b))

#define max(a,b) ((a)>(b)?(a):(b))

#define LL long long

#define INF 9999999999

struct E

{

    int v,nxt,w;

}e[maxn<<1];

int n,m,num,sz;

int st[maxn];

int deep[maxn],head[maxn];

LL c[maxn];

int sum[maxn];

LL pre[maxn];

LL dp[maxn][maxn][55];

inline LL read()

{

    char c=getchar();

    LL x=0;

    while(c<'0'||c>'9') c=getchar();

    while(c>='0'&&c<='9')

        x=(x<<3)+(x<<1)+c-48,c=getchar();

    return x;

}

inline void add_edge(int x,int y,int z)

{

    e[++num].v=y;

    e[num].nxt=head[x];

    e[num].w=z;

    head[x]=num;

}

void dfs(int x)

{

    st[++sz]=x;//开一个栈来存储x节点到根路径上所有的点

    sum[x]=1;

    for(re int i=head[x];i;i=e[i].nxt)

    if(!deep[e[i].v])

    {

        deep[e[i].v]=deep[x]+1;

        pre[e[i].v]=pre[x]+e[i].w;

        dfs(e[i].v);

        sum[x]+=sum[e[i].v];

        for(re int j=1;j<=sz;j++)

        {

            for(re int k=min(sum[x],m);k>=0;k--)//倒序枚举，01背包

            {

                LL mid=INF;

                    for(re int p=0;p<=k;p++)//枚举子树里选多少个

                        mid=min(mid,dp[x][st[j]][k-p]+min(dp[e[i].v][e[i].v][p],dp[e[i].v][st[j]][p]));//儿子可以将自己的运到st[j]，也可以就地解决

                dp[x][st[j]][k]=mid;

            }

        }

    }

    for(re int j=1;j<=sz;j++)

        for(re int k=0;k<=min(sum[x],m);k++)

            dp[x][st[j]][k]+=(pre[x]-pre[st[j]])*c[x];

    for(re int k=min(sum[x],m);k;--k)

        dp[x][x][k]=dp[x][x][k-1];//在就地解决这种情况里，我们没有算上x上建的那个伐木场，于是在这里更新一下

    dp[x][x][0]=INF;

    sz--;

}

int main()

{

    n=read(),m=read()+1;

    int fa,z;

    for(re int i=1;i<=n;i++)

    {

        c[i]=read(),fa=read(),z=read();

        add_edge(fa,i,z);

    }

    deep[0]=1;

    dfs(0);

    printf("%lld\n",dp[0][0][m]);

    return 0;

}