蓝桥杯-算法训练--ALGO-4 结点选择

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;    
 5 #define max(a,b) a>b?a:b
 6 const int MAXN = 100001;
 7 int M; //表示边的索引号，初始为0
 8 int head[MAXN]; //表示某个结点所连接的边
 9 int dp[MAXN][2]; //dp[x][0]表示第x个结点不选择时最大权值，dp[x][1]表示第x个结点选择时最大权值
10 struct Edge{
11 int toNode; //表示这条边到达的结点
12 int nextEdge; //表示这条边的出发结点连接的下一条边
13 }edge[2*MAXN]; //一共有n个结点，有n-1条边，但是不同的出发结点算作不同的边，所以有2n-2条边
14 
15 //把新边加入边集,构造树
16 void add(int from, int to){
17 edge[M].toNode = to;
18 edge[M].nextEdge = head[from];
19 head[from] = M++; //head[x]的值可能会被二次赋值
20 }
21 
22 //类似dfs遍历
23 void dfs(int node, int preNode){
24 for (int i = head[node]; i != -1; i = edge[i].nextEdge){
25 if (edge[i].toNode == preNode) //说明这条边已经搜索过
26 continue;
27 int toNode = edge[i].toNode; //表示边i到达的结点
28 dfs(toNode, node);
29 dp[node][0] += max(dp[toNode][0], dp[toNode][1]); //该结点不算，则该边上的另一结点可选也可不选
30 dp[node][1] += dp[toNode][0]; //改结点选了，该边上另一结点就不能选了
31 }
32 }
33 int main(){
34 int n;
35 memset(head, -1, sizeof(head)); //所有边置为-1，表示不存在该边
36 memset(dp, 0, sizeof(dp));
37 cin >> n;
38 for (int i = 1; i <= n; i++){
39 cin >> dp[i][1]; //每一个结点的权值
40 }
41 for (int j = 1; j <= n - 1; j++){
42 int from, to;
43 cin >> from >> to;
44 add(from, to); 
45 add(to, from);
46 }
47 dfs(1, 0); //从1号结点开始向后动态规划
48 int result = max(dp[1][0], dp[1][1]); //因为不确定根结点，所以从几号开始动态规划就找几号的状态
49 //同样这里也可以写成 dfs(2, 0); int result = max(dp[2][0], dp[2][1]);不过当只有一个结点的时候就不对了
50 cout << result << endl;
51 return 0;
52 }