间隔选点-树上版本

题目(树上dp)

给定一颗n个节点的树，每个顶点有权值。

现在要求选出若干点，这些点不能有边直接相连，使得权值之和最大。

输入

第一行输入一个整数 $6*10^3)n(2≤n≤6∗103)。$

第二行给出n个整数 $a_1, a_2, a_3, ..., a_n(-128 le a_i le 127)a1,a2,a3,...,an(−128≤ai≤127)，表示每个顶点的权值。$

接下来n-1行，每行两个整数 $x_i, y_i (1 le x_i, y_i le n, x_i e y_i)xi,yi(1≤xi,yi≤n,xi�=yi), 表示x_i, y_ixi,yi之间有一边条 $。$

输入保证是一棵树。

输出

输出最大权值之和。

样例

输入

7
1 1 1 1 1 1 1
3 1
3 2
4 6
4 7
4 5
5 3

输出

 1 /*************************************************************************
 2     > Author: Henry Chen
 3     > Mail: 390989083@qq.com 
 4     > Created Time: 二  8/25 23:12:55 2020
 5  ************************************************************************/
 6 
 7 #include<bits/stdc++.h>
 8 using namespace std;
 9 int val[6009];
10 vector<int>vec[6009];
11 int dp[6009][3];
12 void dfs(int u,int fa)
13 {
14     //cout << u << endl;
15     for(int i = 0;i < vec[u].size();i++)
16     {
17         int v = vec[u][i];
18         if(v != fa)
19         {
20             dfs(v,u);
21         }
22     }
23     dp[u][0] = 0;
24     dp[u][1] = val[u];
25     for(int i = 0;i < vec[u].size();i++)
26     {
27         int v = vec[u][i];
28         if(v == fa) continue;
29         dp[u][0] += max(dp[v][0],dp[v][1]);
30         dp[u][1] += dp[v][0];
31     }
32     return;
33 }
34 int main()
35 {
36     int n;
37     cin >> n;
38     for(int i = 1;i <= n;i++)
39     {
40         scanf("%d",&val[i]);
41     }
42     for(int i = 1;i < n;i++)
43     {
44         int u,v;
45         scanf("%d%d",&u,&v);
46         vec[u].push_back(v);
47         vec[v].push_back(u);
48     }
49     dfs(1,1);
50     /*for(int i = 1;i <= n;i++)
51     {
52         printf("* %d %d
",dp[i][0],dp[i][1]);
53     }*/
54     printf("%d
",max(dp[1][1],dp[1][0]));
55     return 0;
56 }