这篇博文你可以完全不用看，因为这道题实在太简单了。
我只是写难题写累了来找找自信qwq（所以就5分钟A了……）
如果你想研究树形dp，建议看一看我的上几篇博文。
这道题……都不知道怎么说了……
每一次从儿子节点回来的时候，利用儿子节点的值更新这个父亲节点的值。
取父亲，加不取儿子的最优解；不取父亲，加上取儿子和不取儿子中的最优解。
如果你写完了发现和题解一样，那就对了…… （哭笑）
代码如下：
#include<cstdio> #include<iostream> #include<vector> using namespace std; #define maxn 20000 vector<int> son[maxn]; int f[maxn][3],n,w[maxn],root=1; bool vis[maxn]; void dfs(int x) { f[x][0]=0; f[x][1]=w[x]; for(int i=0;i<son[x].size();i++) { int y=son[x][i]; dfs(y); f[x][0]+=max(f[y][1],f[y][0]); f[x][1]+=f[y][0]; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n-1;i++) { int x,y; scanf("%d%d",&x,&y); son[y].push_back(x); vis[x]=1; } int s,k; scanf("%d%d",&s,&k); while(vis[root]) root++; dfs(root); printf("%d",max(f[root][0],f[root][1])); return 0; }
原文：https://www.cnblogs.com/popo-black-cat/p/10188303.html