话不多说，直接看题：
这里与前面的树形DP不同，在这里，对于一个节点，它被覆盖的情况有3种，1.被父亲节点覆盖2.自己选3.其中的一个儿子选了。
因此，我们令dp[i][0]表示一定选i，dp[i][1]为不选i,i被一定被他的儿子覆盖，dp[i][2]表示不选i，i一定被他的父亲覆盖。
因此，我们可以得到状态转移方程：
dp[i][0]=1+
对于dp[i][1]，即它可以被它的儿子覆盖（不一定全部），我们发现对于儿子节点，他们除覆盖父亲的节点外是选dp[u][0]与dp[u][1]的min,而为了覆盖父亲必须有一个dp[u][0]，因此，我们分类讨论：
如果取min时取到了dp[u][0]，那么就和dp[i][2]操作一样，否则，我们挑abs(dp[u][0]-dp[u][1])min的加上差值即可。
我们用伪代码：
if(i无叶子) dp[i][1]=inf else +inc;
同时，我们注意这是一个无向树，我们要存两倍的边，同时为了遍历我们要添加fa来保证按照树进行DFS。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,a,b,head[10010],cnt,dp[10010][3];
struct node{int dian,next;
}edge[20010];
void merge(int x,int y){edge[++cnt].dian=y;edge[cnt].next=head[x];head[x]=cnt;
}
void dfs(int root,int fa){dp[root][0]=1;dp[root][2]=0;dp[root][1]=0;int ccc=1000000;for(int i=head[root];i!=-1;i=edge[i].next){int hp=edge[i].dian;if(hp==fa) continue;dfs(edge[i].dian,root);dp[root][0]+=min(dp[hp][0],min(dp[hp][1],dp[hp][2]));dp[root][2]+=min(dp[hp][0],dp[hp][1]);dp[root][1]+=min(dp[hp][0],dp[hp][1]);ccc=min(ccc,dp[hp][0]-dp[hp][1]);}if(ccc<0) ccc=0;dp[root][1]+=ccc;
}
int main(){memset(head,-1,sizeof(head));cin>>n;int root=n*(n+1)/2;for(int i=1;i<=n-1;i++){cin>>a>>b;merge(b,a);merge(a,b);}dfs(1,-1);cout<<min(dp[1][0],dp[1][1]);
} 接题：
我们令dp[i][j]表示以i为根节点的子树保留j个点的最大数量。
易得状态转移方程：
dp[i][j]=max(dp[i][j],dp[v1][k]+w+dp[v2][j-k-1]).
同时我们注意把边上的权值下放给点即可。
下面是AC代码：
#include<bits/stdc++.h>
using namespace std;
int n,q,x,y,head[200],v[200],cnt,z,dp[110][110],pos[110][110];
struct node{int dian,next,quan;
}edge[210];
void merge(int x,int y,int z){edge[++cnt].dian=y;edge[cnt].quan=z;edge[cnt].next=head[x];head[x]=cnt;
}
void dfsquan(int root,int fa){for(int i=head[root];i!=-1;i=edge[i].next){if(edge[i].dian==fa) continue;v[edge[i].dian]=edge[i].quan;dfsquan(edge[i].dian,root);}return;
}
void dfsdp(int root,int fa,int q){if(pos[root][q]==1) return;if(q==0){dp[root][q]=0;pos[root][q]=1;return;}int f=0;int vk=0;int tr[3];for(int i=head[root];i!=-1;i=edge[i].next){if(edge[i].dian==fa) continue;tr[++vk]=edge[i].dian;f=1;for(int j=0;j<=q;j++){dfsdp(edge[i].dian,root,j);}}if(!f){if(q==1) dp[root][q]=v[root];else dp[root][q]=-10000000;pos[root][q]=1;return; }for(int j=0;j<=q-1;j++){dp[root][q]=max(dp[root][q],v[root]+dp[tr[1]][j]+dp[tr[2]][q-1-j]);}pos[root][q]=1;return;
}
int main(){cin>>n>>q;memset(head,-1,sizeof(head));for(int i=1;i<=n-1;i++){cin>>x>>y>>z;merge(x,y,z);merge(y,x,z);}dfsquan(1,-1);dfsdp(1,-1,q+1);cout<<dp[1][q+1];
}
