例如下图是火车站网络：
最佳投资方案是在1，2，5，6这4个火车站开饭店可以获得利润为90 Input 第一行输入整数N(<=100000)，表示有N个火车站，分别用1，2。。。，N来编号。接下来N行，每行一个整数表示每个站点的利润，接下来N-1行描述火车站网络，每行两个整数，表示相连接的两个站点。 Output 输出一个整数表示可以获得的最大利润。 Sample Input 6 10 20 25 40 30 30 4 5 1 3 3 4 2 3 6 4 Sample Output 90 Data Constraint
N<=100000
题目就是说给你一棵树，每个节点有各自的权值，
假如你选了一个节点，就不能再选它的所有子节点以及父亲节点，
现在让你选一些节点，使得总权值和最大。
这题可以说是树形DP的样板题目了，
设[i,0]表示当前节点选且作为子树的根节点，dp[i,0]表示此情况时子树权值总和的最大值；
设[i,1]表示当前节点不选且作为子树的根节点，dp[i,1]表示此情况时子树权值总和的最大值；
可以用dfs来实现这个树形DP
参考代码：
var n,i,x,y:longint; a:array[1..100000]of longint; f:array[1..100000,0..50]of longint; dp:array[1..100000,1..2]of longint; bz:array[1..100000]of boolean; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; procedure dfs(x:longint); var i:longint; begin bz[x]:=false; dp[x,0]:=a[x]; for i:=1 to f[x,0] do if bz[f[x,i]] then begin dfs(f[x,i]); dp[x,0]:=dp[x,0]+dp[f[x,i],1]; dp[x,1]:=dp[x,1]+max(dp[f[x,i],0],dp[f[x,i],1]); end; end; begin readln(n); for i:=1 to n do readln(a[i]); for i:=1 to n-1 do begin readln(x,y); inc(f[x,0]); f[x,f[x,0]]:=y; inc(f[y,0]); f[y,f[y,0]]:=x; end; fillchar(bz,sizeof(bz),true); dfs(1); writeln(max(dp[1,0],dp[1,1])); end.
