什么鬼noip互测题...
这题很显然是树形dp，但设计状态以及转移是个难点
记状态f[i][j][k]表示以i为根节点的子树，离i最近的祖宗节点编号为j放了虫洞（伐木场？），i的子树内放了k个伐木场的方案数
设to为i的某个子节点，当i不放伐木场时，有：
dp[i][j][k]=min(dp[to][j][k-c]+dp[i][j][c])
当i放伐木场时，有：
dp[i][i][k]=min(dp[to][i][k-c]+dp[i][i]c])
最后合并：
dp[i][j][k]+=num[i]*dis[i][j]
dp[i][j][k]=min(dp[i][j][k],dp[i][i][k])
其中dis[i][j]表示从i到j（j为i的某个祖先节点）的距离，可以预处理出来
特别的，当i为叶节点（即i没有子节点）时，dp[i][j][0]=dis[i][j]*num[i]直接赋值
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define ll long long
using namespace std;
int dp[][][];
struct Edge
{
int next;
int to;
}edge[];
int head[];
int dis[][];
int num[];
int f[];
int n,k;
int cnt=;
void init()
{
memset(head,-,sizeof(head));
memset(f,-,sizeof(f));
cnt=;
}
void add(int l,int r)
{
edge[cnt].next=head[l];
edge[cnt].to=r;
head[l]=cnt++;
}
void initdfs(int x)
{
if(x)
{
for(int i=f[x];i!=-;i=f[i])
{
dis[x][i]=dis[x][f[x]]+dis[f[x]][i];
}
dis[x][]=dis[x][f[x]]+dis[f[x]][];
}
for(int i=head[x];i!=-;i=edge[i].next)
{
int to=edge[i].to;
initdfs(to);
}
}
void dfs(int x)
{
if(head[x]==-)
{
for(int i=f[x];i!=-;i=f[i])
{
dp[x][i][]=dis[x][i]*num[x];
}
return;
}
if(x)
{
dp[x][x][]=0x3f3f3f3f;
}
for(int i=head[x];i!=-;i=edge[i].next)
{
int to=edge[i].to;
dfs(to);
for(int j=f[x];j!=-;j=f[j])
{
for(int t=k;t>=;t--)
{
int temp=0x3f3f3f3f;
for(int c=;c<=t;c++)
{
temp=min(temp,dp[x][j][c]+dp[to][j][t-c]);
}
dp[x][j][t]=temp;
}
}
for(int j=k;j>=;j--)
{
int temp=0x3f3f3f3f;
for(int c=(x!=);c<=j;c++)
{
temp=min(temp,dp[x][x][c]+dp[to][x][j-c]);
}
dp[x][x][j]=temp;
}
}
for(int i=f[x];i!=-;i=f[i])
{
for(int j=;j<=k;j++)
{
dp[x][i][j]+=dis[x][i]*num[x];
dp[x][i][j]=min(dp[x][i][j],dp[x][x][j]);
}
}
}
inline int read()
{
int f=,x=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int main()
{
// freopen("girls.in","r",stdin);
// freopen("girls.out","w",stdout);
n=read(),k=read();
init();
f[]=-;
for(int i=;i<=n;i++)
{
int v;
num[i]=read(),f[i]=read(),v=read();
dis[i][f[i]]=v;
add(f[i],i);
}
initdfs();
dfs();
printf("%d\n",dp[][][k]);
return ;
}