私以为没必要转二叉树
本题应为三维dp,体现的是泛化物品的背包的思想(详见<背包九讲>)
只是决定价值(本题体现为节省的费用)的因素不是单一的重量(体现为产树量),此外还有一个维度据上一个伐木场的距离
具体来说,一个伐木场节省的费用可以是其自己和儿子们的产树量之和和上一个伐木场的距离的成绩,这样我们就简单地设计出了状态转移策略
代码见下.蒻的英语不是很好请见谅
//by beautyyu
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#define ull unsigned long long
using namespace std;
struct edge{
int v,w,nxt;
}e[40000];
int head[200],pwp[200],pre[200],memf[200][200][100],memd[200][200][100];
//pwp--sum weight of a subtree,pre--distance from a node to root
//memf--memory for function'f',the same as memd
int w[200],n,k;
int f(int rt,int fa,int kk);
int d(int l,int fa,int kk);
int dfs(int rt,int pr){//calculate 'pwp' and 'pre'
pre[rt] = pr;
pwp[rt] = w[rt];
for (int i = head[rt];i;i = e[i].nxt)
pwp[rt] += dfs(e[i].v,pr + e[i].w);
return pwp[rt];
}
int main (){
scanf("%d%d",&n,&k);
int al,be,cnt = 0;
for (int i = 1;i <= n;++ i){
scanf("%d%d%d",&w[i],&al,&be);
e[++ cnt] = edge{i,be,head[al]};
head[al] = cnt;
}
//read end
//first set
dfs(0,0);
int sum_ = 0;
for (int i = 1;i <= n;++ i)
sum_ += w[i] * pre[i];
memset(memf,-1,sizeof(memf));
memset(memd,-1,sizeof(memd));
//main code
cout << sum_ - f(0,0,k);
return 0;
}
int f(int rt,int fa,int kk){
//the value produced by a subtree'rt',the last sawmill 'fa',the rest sawmill I can build
if(memf[rt][fa][kk] != -1) return memf[rt][fa][kk];
if(!kk) return memf[rt][fa][kk] = 0;
return memf[rt][fa][kk] = max(d(head[rt],fa,kk),
d(head[rt],rt,kk - 1) + pwp[rt] * (pre[rt] - pre[fa]));
}
int d(int l,int fa,int kk){
//the value produced by a list begin with 'l','fa'and'kk'are the same as the function 'f'
if ((!l)||(!kk)) return memd[l][fa][kk] = 0;
if(memd[l][fa][kk] != -1) return memd[l][fa][kk];
int ans = 0;
for (int i = 0;i <= kk;++ i)
ans = max(ans,f(e[l].v,fa,i) + d(e[l].nxt,fa,kk - i));
return memd[l][fa][kk] = ans;
}