有一棵 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的正整数。
解题思路：
1，树上的dp前向星存图。
2，对于一个结点，有两种选择，选或不选。
3，如果选了该结点，他的子结点都不能选择。
4，如果不选该结点，选择他的所有子节点的max（选，不选） ；
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int maxn = 100005 ; int n,cnt; int pre[maxn]; int dp[maxn][2]; int val[maxn]; int next[maxn*2]; int to[maxn*2]; void add_edge(int u,int v) { next[cnt]=pre[u]; to[cnt]=v; pre[u]=cnt++; } void dfs(int u,int fa) { dp[u][0]=0; dp[u][1]=val[u]; for(int i=pre[u]; i!=-1; i=next[i]) { int v=to[i]; if(v==fa) continue; dfs(v,u); dp[u][1]+=dp[v][0]; // int t=dp[v][0]; // if(dp[v][1]>t) t=dp[v][1]; dp[u][0]+=max(dp[v][0],dp[v][1]); } } //0011 1111 0011 1111 0011 1111 0011 1111 int main() { //Scanner in=new Scanner(System.in); //n=in.nextInt(); cin>>n ; for(int i=1; i<=n; i++) //val[i]=in.nextInt(); cin>>val[i] ; cnt=0; //Arrays.fill(pre, -1); memset(pre,-1,sizeof(pre)); for(int i=0; i<n-1; i++) { //int t1=in.nextInt(); int t1,t2; //int t2=in.nextInt(); cin>>t1>>t2 ; add_edge(t1,t2); add_edge(t2,t1); } dfs(1,0); //int ans=dp[1][0]; //if(dp[1][1]>ans) ans=dp[1][1]; int ans = max(dp[1][0], dp[1][1]) ; //printf("%d\n",ans); cout<<ans<<endl ; }
