这题目确实是比较经典的树形dp，里面确实还是有很多需要理解的地方
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=1005; 4 5 int n,q; 6 int dis[N][N],l[N],r[N],a[N],f[N][N]; 7 8 int get(){ 9 char zy=getchar(); 10 int z=1,y=0; 11 while(zy>'9'||zy<'0'){ 12 if(zy=='-')z=-1; 13 zy=getchar(); 14 } 15 while(zy>='0'&&zy<='9'){ 16 y=y*10+zy-'0'; 17 zy=getchar(); 18 } 19 return z*y; 20 } 21 22 void build(int u){ 23 for(int i=1;i<=n;i++){ 24 if(dis[u][i]>=0){ 25 if(!l[u]){ 26 a[i]=dis[u][i]; 27 dis[u][i]=dis[i][u]=-1; 28 l[u]=i; 29 build(i); 30 continue; 31 } 32 a[i]=dis[u][i]; 33 dis[u][i]=dis[i][u]=-1; 34 r[u]=i; 35 build(i); 36 break; 37 } 38 } 39 } 40 41 int Max(int a,int b){return a>b?a:b;} 42 43 int tdp(int u,int t){ 44 if(t==0) return 0; 45 if(l[u]==0&&r[u]==0)return a[u]; 46 if(f[u][t])return f[u][t]; 47 for(int i=0;i<t;i++){ 48 f[u][t]=Max(f[u][t],tdp(l[u],i)+tdp(r[u],t-i-1)+a[u]); 49 } 50 return f[u][t]; 51 } 52 53 int main(){ 54 n=get();q=get()+1; 55 for(int i=1;i<=n;i++){ 56 for(int j=1;j<=n;j++){ 57 dis[i][j]=-1; 58 } 59 } 60 for(int i=1;i<n;i++){ 61 int u=get(),v=get(); 62 dis[u][v]=dis[v][u]=get(); 63 } 64 build(1); 65 printf("%d ",tdp(1,q)); 66 return 0; 67 }