树形dp
状态表示:$f_{i,j,k,0/1}$ 以$i$为根的子树,离$i$(根节点方向)最近的伐木场是$j$,该节点子树建造了$k$个伐木场,该点是否建立伐木场
状态转移:
如果该点建立伐木场,枚举前面子树建造伐木场个数$j$以及当前子树建造伐木场个数$k$进行更新
如果该点没有建立伐木场,不单单枚举上面的$j,k$以及要枚举离他们最近的伐木场编号(枚举祖先节点)
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=110;
const int INF=0x3f3f3f3f;
int n,m;
int h[N],e[N],ne[N],w[N],idx;
int f[N][N][N][2],g[N];// f[i][j][k][0/1] 以i为根的子树 离i进的木场是j 子树中造了k个伐木场 0/1 存不存在
int sz[N],cnt[N],fa[N],d[N];
void add(int a,int b,int c)
{
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void update(int u,int p,int cnt,int op)
{
if(u==-1)
for(int i=0;i<=cnt;i++) g[i]=INF;
else
for(int i=0;i<=cnt;i++) f[u][p][i][op]=g[i];
}
void dfs(int u)
{
sz[u]=1;
f[u][u][1][1]=0;
int p=fa[u];
while(p!=-1)
{
f[u][p][0][0]=cnt[u]*(d[u]-d[p]);
p=fa[p];
}
for(int i=h[u];i!=-1;i=ne[i])
{
int son=e[i];
d[son]=d[u]+w[i];
dfs(son);
update(-1,-1,sz[u]+sz[son],-1);
for(int j=0;j<=sz[u];j++)
for(int k=0;k<=sz[son];k++)
g[j+k]=min(g[j+k],f[u][u][j][1]+min(f[son][u][k][0],f[son][son][k][1]));
update(u,u,sz[u]+sz[son],1);
int p=fa[u];
while(p!=-1)
{
update(-1,-1,sz[u]+sz[son],-1);
for(int j=0;j<=sz[u];j++)
for(int k=0;k<=sz[son];k++)
g[j+k]=min(g[j+k],f[u][p][j][0]+min(f[son][p][k][0],f[son][son][k][1]));
update(u,p,sz[u]+sz[son],0);
p=fa[p];
}
sz[u]+=sz[son];
}
}
int main()
{
cin>>n>>m;
memset(f,0x3f,sizeof f);
memset(h,-1,sizeof h);
fa[0]=-1;
for(int i=1;i<=n;i++)
{
int a,b,c;
cin>>a>>b>>c;
fa[i]=b;
cnt[i]=a;add(b,i,c);
}
dfs(0);
cout<<f[0][0][m+1][1]<<'\n';
return 0;
}