说句实话，写完这道题，很想吐一口血出来，以示我心情的糟糕；
题目很简单，树形dp，正常做30分钟，硬是做了好几个小时，真是伤心。
题解不写了，只是吐个槽，网上没有用背包写的dp，全是左儿子右兄弟写法，没法对照一下，难受啊。
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 #define LL long long 6 int n,K; 7 const int maxn=210; 8 const LL inf=3000000000LL; 9 struct node{ 10 int y,next,v; 11 }e[maxn]; 12 int linkk[maxn],len=0,w[maxn],d[maxn][maxn],siz[maxn],q[maxn],tail=0,fa[maxn],ru[maxn],vis[maxn]; 13 int read(){ 14 int x=0;char ch=getchar();bool flag=0; 15 while(ch<'0'||ch>'9'){if(ch=='-')flag=1;ch=getchar();} 16 while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} 17 return flag?-x:x; 18 } 19 void insert(int x,int y,int v){ 20 e[++len].y=y; 21 e[len].v=v; 22 e[len].next=linkk[x]; 23 linkk[x]=len; 24 } 25 void print(int x){printf("%d ",x);} 26 void print(int x,int y){printf("%d %d ",x,y);} 27 void init(){ 28 int y,v; 29 n=read(),K=read(); 30 memset(d,10,sizeof(d)); 31 for(int i=1;i<=n;i++){ 32 w[i]=read(),y=read(),v=read(); 33 insert(i,y,v);insert(y,i,v); 34 d[i][y]=v,d[y][i]=v; 35 } 36 37 } 38 void findd(){ 39 for(int i=1;i<=n;i++)d[i][i]=0; 40 for(int k=0;k<=n;k++) 41 for(int i=0;i<=n;i++) 42 for(int j=0;j<=n;j++) 43 if(d[i][k]+d[k][j]<d[i][j])d[i][j]=d[i][k]+d[k][j]; 44 } 45 LL f[110][60][110]; 46 void dfs(int x,int f){ 47 siz[x]=1; 48 fa[x]=f; 49 for(int i=linkk[x];i;i=e[i].next){ 50 if(e[i].y==f)continue; 51 dfs(e[i].y,x); 52 siz[x]+=siz[e[i].y]; 53 ru[x]++; 54 } 55 if(siz[x]==1)q[++tail]=x; 56 } 57 void work(){ 58 memset(f,-1,sizeof(f)); 59 findd(); 60 dfs(0,0); 61 for(int head=1;head<=tail;head++){ 62 int x=q[head]; 63 ru[fa[x]]--; 64 if(ru[fa[x]]==0)q[++tail]=fa[x]; 65 LL g[56]; 66 for(int k=0;k<=siz[x]&&k<=K;k++){ 67 for(int prev=fa[x];prev!=-1;prev=fa[prev]){ 68 69 for(int p=0;p<=k;p++)g[p]=0; 70 for(int i=linkk[x];i;i=e[i].next){ 71 if(e[i].y==fa[x])continue; 72 LL minn=inf; 73 for(int j=k;j>=0;j--){ 74 minn=inf; 75 for(int l=0;l<=siz[e[i].y]&&l<=j;l++) 76 minn=min(minn,g[j-l]+f[e[i].y][l][prev]); 77 g[j]=minn; 78 } 79 } 80 LL ans=g[k]+w[x]*d[prev][x]; 81 for(int p=0;p<=k;p++)g[p]=0; 82 for(int i=linkk[x];i;i=e[i].next){ 83 if(e[i].y==fa[x])continue; 84 LL minn=inf; 85 for(int j=k-1;j>=0;j--){ 86 minn=inf; 87 for(int l=0;l<=siz[e[i].y]&&l<=j;l++) 88 minn=min(minn,g[j-l]+f[e[i].y][l][x]); 89 g[j]=minn; 90 } 91 } 92 f[x][k][prev]=min(ans,k-1<0?inf:g[k-1]); 93 if(!prev)break; 94 } 95 } 96 } 97 cout<<f[0][K][0]<<endl; 98 } 99 int main(){ 100 freopen("1.in","r",stdin); 101 freopen("1.out","w",stdout); 102 init(); 103 work(); 104 }