二叉苹果树
题目链接
思路：
对于x为根的子树最大值可以从左右儿子选，只需要遍历左右儿子保留的数量即可。但由于题目要求与根节点（1）相连，也就是说如果选了左儿子，左儿子与根x的边就要连。由于给的是边权，先把边权转化成子节点的点权。
代码：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const ll mod=1e9+7;
const int N=2e5+10;
#define int ll
const double eps=1e-6;ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;
}int n,q;
vector<int> v[3000],l[3000];
int dp[500][500];
int a[3000];void c(int x,int f,int value){a[x]=value;for(int i=0;i<v[x].size();i++){int j=v[x][i],w=l[x][i];if(j==f) continue;c(j,x,w);}
}void dfs(int x,int f){vector<int> p;for(int k=0;k<v[x].size();k++){int y=v[x][k];if(y==f) continue;dfs(y,x);/*for(int i=q;i>=1;i--){for(int j=0;j<i;j++){dp[x][i]=max(dp[x][i],dp[x][i-j-1]+dp[y][j]+a[y]);}}*/p.push_back(y);}if(p.size()==0) return;int t=p[0],tt=p[1];for(int i=0;i<=q;i++){for(int j=0;j<=q;j++){if(!i&&!j) continue;if(i&&!j){dp[x][i+j]=max(dp[x][i+j],dp[t][i-1]+a[t]);}else if(!i&&j){dp[x][i+j]=max(dp[x][i+j],dp[tt][j-1]+a[tt]);}else{dp[x][i+j]=max(dp[x][i+j],dp[t][i-1]+dp[tt][j-1]+a[t]+a[tt]);}}}
}void solve(){while(cin>>n>>q){for(int i=0;i<=n;i++){v[i].clear();}for(int i=1;i<n;i++){int x,y,z;cin>>x>>y>>z;v[x].push_back(y);v[y].push_back(x);l[x].push_back(z);l[y].push_back(z);}c(1,0,0);dfs(1,0);cout<<dp[1][q]<<endl;}}signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;while (t--){solve();}return 0;
}