River
枫林晚
2018-05-18 11:13:56
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100+10;
const int K=55;
const ll inf=2000000000+1000;
struct node{
int nxt,to;
ll val;
}bian[2*N];
int hd[N],cnt;
int w[N];
int n,k;
ll f[N][N][K];
int fa[N];
int disf[N];
bool vis[N];
void add(int x,int y,ll z)
{
bian[++cnt].nxt=hd[x];
bian[cnt].to=y;
bian[cnt].val=z;
hd[x]=cnt;
}
void dfs(int x)
{
cout<<" now "<<x<<endl;
vis[x]=1;
for(int i=1;i<=k;i++)
f[x][x][i]=0;//build one
ll dis=0;
for(int i=x;i!=0;i=fa[i])// not
{
dis+=disf[i];
//if(x==3) cout<<fa[i]<<" "<<dis<<endl;
f[x][fa[i]][0]=dis*w[x];
f[x][fa[i]][1]=0;
}
for(int i=hd[x];i;i=bian[i].nxt)
{
int y=bian[i].to;
if(!vis[y])
{
dfs(y);
ll g[N][K];
for(int o=0;o<N;o++)
for(int u=0;u<K;u++)
g[o][u]=inf;
for(int p=1;p<=k;p++)//build one
{
for(int q=0;q<=p;q++)
{
g[x][p]=min(g[x][p],f[x][x][p-q]+f[y][x][q]);
}
}
ll dis=0;
for(int j=x;j!=0;j=fa[j])//not
{
dis+=disf[j];
for(int p=0;p<=k;p++)
{
for(int q=0;q<=p;q++)
{
g[fa[j]][p]=min(g[fa[j]][p],f[x][fa[j]][p-q]+f[y][fa[j]][q]);
}
}
}
for(int j=x;j!=-1;j=fa[j])
{
for(int p=0;p<=k;p++)
f[x][j][p]=g[j][p];
}
if(x==2)
{
cout<<"222222"<<endl;
for(int p=0;p<=n;p++)
{
for(int q=0;q<=k;q++)
cout<<p<<" "<<q<<" : "<<f[x][p][q]<<endl;
}
cout<<endl;
}
}
}
}
int main()
{
scanf("%d%d",&n,&k);
k++;//warning!!!
int x,y,z;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&w[i],&y,&z);
fa[i]=y;disf[i]=z;
cout<<i<<" "<<" y "<<y<<" "<<fa[i]<<endl;
add(i,y,z);
add(y,i,z);
}
for(int i=0;i<=n;i++)
cout<<i<<" fa "<<fa[i]<<" disf "<<disf[i]<<endl;
fa[0]=-1;
for(int i=0;i<N;i++)
for(int j=0;j<N;j++)
for(int o=0;o<K;o++)
f[i][j][o]=inf;
dfs(0);
for(int i=0;i<=n;i++)
{
cout<<i<<" : "<<endl;
for(int j=0;j<=n;j++)
for(int o=0;o<=k;o++)
{
cout<<" anc "<<j<<" build "<<o<<" -> "<<f[i][j][o]<<endl;
}
}
printf("%d",f[0][0][k]);
return 0;
}
```