MZOJ 1134 && LuoGu P2015 二叉苹果树 [传送门]
#include<bits/stdc++.h> using namespace std; const int maxn=500; int N,Q; int head[maxn],k=0; int w[maxn][maxn],f[maxn][maxn]; struct edge{ int v,w,nxt; }e[maxn<<1]; void init(){ freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); } void adde(int u,int v){ e[k].v=v; e[k].nxt=head[u]; head[u]=k++; } void readdata(){ int u,v,c; memset(head,-1,sizeof(head)); scanf("%d%d",&N,&Q); for(int i=1;i<N;i++){ scanf("%d%d%d",&u,&v,&c); adde(u,v); adde(v,u); w[u][v]=w[v][u]=c; } } int dp(int u,int fa){ f[u][0]=0;f[u][1]=w[u][fa]; int size=1; for(int i=head[u];~i;i=e[i].nxt){ int v=e[i].v; if (v==fa) continue; int s=dp(v,u); size+=s; for(int j=size;j>0;j--){ for(int k=0;k<j;k++){ if(k>s)continue; else f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]); } } } return size; } void work(){ dp(1,0); printf("%d",f[1][Q+1]); } int main(){ //init(); readdata(); work(); return 0; }