有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？
输入格式第一行包含一个整数 n 。
接下来的一行包含 n 个正整数，第 i 个正整数代表点 i 的权值。
接下来一共 n-1 行，每行描述树上的一条边。
输出格式 输出一个整数，代表选出的点的权值和的最大值。 样例输入 5 1 2 3 4 5 1 2 1 3 2 4 2 5 样例输出 12 样例说明 选择3、4、5号点，权值和为 3+4+5 = 12 。 数据规模与约定对于20%的数据， n <= 20。
对于50%的数据， n <= 1000。
对于100%的数据， n <= 100000。
权值均为不超过1000的正整数。
题解：树形dp。（点权）
设dp[i][0]表示不选择i点时，i点及其子树能选出的最大权值。
dp[ i ][1]表示选择i点时，i点及其子树的最大权值。
所以，状态转移方程为：
对于叶子节点 i ：
dp[ i ][0] = 0, dp[ i ][1] = K.(点权)
对于非叶子节点 i ：
dp[ i ][1] = i点权值 + ∑dp[ j ][ 0 ] (j是i的儿子)
dp[ i ][0] = ∑max(dp[ j ][ 0 ], dp[ j ][1]) (j是i的儿子) 最后答案的最大权值即为max(dp[1][0], dp[1][1])。
代码：
#include<bits/stdc++.h> using namespace std; vector<int>G[100010]; int dp[100010][2]; void dfs(int cur,int fa) { for(int i=0;i < G[cur].size();i++){ int v = G[cur][i]; if(v == fa)continue; dfs(v,cur); dp[cur][1] += dp[v][0]; dp[cur][0] += max(dp[v][0],dp[v][1]); } } int main() { //freopen("in.txt","r",stdin); int n; int u,v; cin>>n; for(int i=1;i<=n;i++){ cin>>dp[i][1]; } for(int i=1;i<n;i++){ cin>>u>>v; G[u].push_back(v); G[v].push_back(u); } dfs(1,0); cout<<max(dp[1][0],dp[1][1])<<endl; return 0; }
