问题描述

有一棵 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动态规划好像挺强大的，各种算法好像也挺好玩的，但是实力太差，看别人的代码都要一点一点看分析才能看懂，

   什么时候自己才能成为大牛呢（遐想中）

#include
      
       #include
       
        #include
        
         #include 
         
            using namespace std;vector
          
           e[100010];//vector是一种顺序容器，事实上和数组差不多，但它比数组更优越。我个人把它理解为数组队列//vector可以用下标访问 /*    构造一棵树出来，遍历，一开始我用的是链式前向星保存数，    但好像是单向的，没做出来 */int pow[100010];//保存每个节点的权值 int vis[100010];//记录每个节点是否走过，走过置1，没走为0 int dp[100010][2];//每个可以选择的点有两种选择 //d[i][0]是不选第i个点//d[i][1]是选择第i个点 void dfs(int f){    int size=e[f].size();    int next;    dp[f][0]=0;//不选这个点，这个点的就为0     dp[f][1]=pow[f];    for(int i=0;i
           
            >n; memset(vis,0,sizeof(vis));//初始化 for(int i=1;i<=n;i++)//输入每个点权值 { cin>>a; pow[i]=a; } for(int i=0;i
            
             >a>>b; e[a].push_back(b); e[b].push_back(a); /* 把终点存进起点的数组里 把起点存进终点的数组里 */ } vis[1]=1; //从第一个点开始递归 dfs(1); //递归遍历完后，最优解在dp[1][1],dp[1][0]中得出 printf("%d",max(dp[1][1],dp[1][0])); return 0;}