18.10.03模拟赛T3。
xcj丧心病狂出了道IOI的题？？？（虽然是2005年的）
而且被zwz当场切掉？？？（这个已经习惯了）
树形DP。
本来以为是二维的：f[p][k]表示p的子树里放k个得到的最小值。
然后就没搞出来。
正解是三维的：f[p][fa][k]表示p的子树里放k个，p的祖先节点里的最近的在fa，得到的最小值。
转移之前需要先求出点之间的距离。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 6 int n,k; 7 int fa[105],v[105]; 8 int dis[105][105]; 9 int f[105][105][55]; 10 int hd[105],nx[105],to[105],ec; 11 12 void edge(int af,int at) 13 { 14 to[++ec]=at; 15 nx[ec]=hd[af]; 16 hd[af]=ec; 17 } 18 19 void dfs(int p) 20 { 21 int s=p; 22 for(int i=fa[p];i!=-1;i=fa[i]) 23 { 24 dis[p][i]=dis[p][s]+dis[s][i]; 25 s=i; 26 } 27 if(!hd[p]) 28 { 29 for(int i=fa[p];i!=-1;i=fa[i]) 30 f[p][i][0]=dis[p][i]*v[p]; 31 return; 32 } 33 if(p)f[p][p][0]=0x3f3f3f3f; 34 for(int i=hd[p];i;i=nx[i]) 35 { 36 int t=to[i]; 37 dfs(t); 38 for(int ff=fa[p];ff!=-1;ff=fa[ff]) 39 { 40 for(int j=k;j>=0;j--) 41 { 42 int tv=0x3f3f3f3f; 43 for(int l=0;l<=j;l++) 44 { 45 tv=min(tv,f[p][ff][l]+f[t][ff][j-l]); 46 } 47 f[p][ff][j]=tv; 48 } 49 } 50 for(int j=k;j>=0;j--) 51 { 52 int tv=0x3f3f3f3f; 53 for(int l=(p!=0);l<=j;l++) 54 { 55 tv=min(tv,f[p][p][l]+f[t][p][j-l]); 56 } 57 f[p][p][j]=tv; 58 } 59 } 60 for(int i=fa[p];i!=-1;i=fa[i]) 61 { 62 for(int j=0;j<=k;j++) 63 { 64 f[p][i][j]+=dis[p][i]*v[p]; 65 f[p][i][j]=min(f[p][i][j],f[p][p][j]); 66 } 67 } 68 } 69 70 int main() 71 { 72 scanf("%d%d",&n,&k); 73 for(int i=1;i<=n;i++) 74 { 75 int w; 76 scanf("%d%d%d",&v[i],&fa[i],&w); 77 dis[i][fa[i]]=w; 78 edge(fa[i],i); 79 } 80 fa[0]=-1; 81 dfs(0); 82 printf("%d ",f[0][0][k]); 83 return 0; 84 }