题目

问题描述
有一棵 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的正整数。

题解

相信很多人看到题目和我一样蒙蔽
先读懂样例，5 个点，5 个权值，这没问题
下面的 4 组数据就懵逼了，
1 2
1 3
2 4
2 5
它的意思是第 1 个结点和第 2 个结点相连
第 1 个结点和第 3 个结点相连
第 2 个结点和第 4 个结点相连
第 2 个结点和第 5 个结点相连
所以画出图是这样

再读题，说选出点的最大权值和。要求是如果一个点被选择了，那么在树上和它相邻的点都不能被选择
意思是选了 1 就不能选相邻的 2 3，选了 2 就不能选相邻的 1 4 5，…
所以样例最大的权值和是 12，选了 3 4 5

读懂了题我们来分析解，实质上就是一个树图的遍历问题，选用邻接表存储（其实就是二维数组），dfs 遍历
可以发现肯定是从最深处往上累加，所以用动态规划
对于每个点有两种情况，被选中和不被选中，如果该点被选中，则不能取相邻所有点；不选中该点，则该点权值和与相邻最大和累加。
设点 i 被选中情况为 dp[i][1]，不被选中情况为 dp[i][0]
即对应的状态转移方程为：

  1. dp[i][0] += max(dp[j][0],dp[j][1]) // i 是 j 的邻接点
  2. dp[i][1] += dp[j][0]

累加到最后一步 dp[1][0] 和 dp[1][1] 中的最大值，即为累加和

#include<iostream>
#include<vector>
using namespace std;
int dp[100005][2];
vector<vector<int> > v;

void dfs(int son,int far){
	// 遍历所有邻接点 
	for(int i=0;i<v[son].size();i++){
		int tmp = v[son][i]; // 得到 son 的邻接点 
		if(tmp != far){  // 如果该邻接点不是父结点，所以得到的就是 son 的儿子结点 
			dfs(tmp,son);  
			dp[son][0] +=max(dp[tmp][0],dp[tmp][1]);   // 不选中，从儿子结点中选最大的累加 
			dp[son][1] += dp[tmp][0];   // 选中，儿子结点不选 
		} 
	}
}
int main(){
	int n;
	int a,b;
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>dp[i][1];
	v.resize(n+1);  // 重新调整 v 的大小 
	// 建图 
	for(int i=1;i<=n-1;i++){
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1,0); 
	cout<<max(dp[1][1],dp[1][0]);
	return 0;
}