有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共 NN 个节点，标号 11 至 NN，树根编号一定为 11。
我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。
首先明确一点，就是输入不能保证前面是后面的父亲，所以要建树
然后用记忆化搜索进行DP
DP方程很好推
先枚举两个儿子各取多少个，然后取最大值
下面给出代码：
#include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<string> using namespace std; inline int rd(){ int x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch==‘-‘) f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-‘0‘; return x*f; } inline void write(int x){ if(x<0) putchar(‘-‘),x=-x; if(x>9) write(x/10); putchar(x%10+‘0‘); return ; } int dp[1006][1006]; int q,n; int head[100006]; int to[10006],nxt[10006],v[10006]; int total=0; void add(int x,int y,int z){ total++; to[total]=y; v[total]=z; nxt[total]=head[x]; head[x]=total; return ; } int l[10006],r[10006]; int vis[10006]; int s[100006]; void get_tree(int x){ vis[x]=1; for(int e=head[x];e;e=nxt[e]){ if(!vis[to[e]]){ if(!l[x]) l[x]=to[e]; else r[x]=to[e]; s[to[e]]=v[e]; get_tree(to[e]); } } return ; } inline int dfs(int x,int y){ if(y==0) return 0; if(!l[x]&&!r[x]) return s[x]; if(dp[x][y]) return dp[x][y]; for(int i=0;i<y;i++){ dp[x][y]=max(dp[x][y],dfs(l[x],i)+dfs(r[x],y-i-1)+s[x]); } return dp[x][y]; } int main(){ n=rd(),q=rd(); for(int i=1;i<n;i++){ int x=rd(),y=rd(),z=rd(); add(x,y,z),add(y,x,z); } get_tree(1); write(dfs(1,q+1)); return 0; }