http://acm.hdu.edu.cn/showproblem.php?pid=1520
父节点和子节点不能同时选。
http://blog.csdn.net/woshi250hua/article/details/7641589
首先是建树,这个在之前的树形背包里有讲:http://www.cnblogs.com/qlky/p/5650783.html
因为这里没有指定根节点,所以可以建双向边,这样就可以从任一个点出发遍历
接下来是DP,状态转移方程:
dp[fa][0] += max(dp[son][0]+dp[son][1])
dp[fa][1] += dp[son][0]
#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("! ") #define MAXN 20000+5 #define MAX(a,b) a>b?a:b #define blank pf(" ") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f #define ls (rt<<1) #define rs (rt<<1|1) int n,m; int ptr = 1,head[MAXN],a[MAXN],dp[MAXN][2],vis[MAXN]; struct node { int y,val,next; }tree[MAXN]; void add(int fa,int son) { tree[ptr].y = son; tree[ptr].next = head[fa]; head[fa] = ptr++; } void dfs(int root) { vis[root] = 1; dp[root][1] = a[root]; dp[root][0] = 0; for(int i=head[root];i!=-1;i=tree[i].next) { int y = tree[i].y; if(vis[y]) continue; dfs(tree[i].y); dp[root][0] += max(dp[y][0],dp[y][1]); dp[root][1] += dp[y][0]; } } int main() { int i,j,t,kase=1; while(~sf("%d",&n)) { mem(a,0); mem(vis,0); mem(dp,0); mem(head,-1); ptr = 1; for(i=1;i<=n;i++) sf("%d",&a[i]); int x,y; while(sf("%d%d",&x,&y),x+y) { add(y,x); add(x,y); } dfs(1); pf("%d ",max(dp[1][0],dp[1][1])); } return 0; }