测试地址：Anniversary Party 题目大意：要举办一个派对，有N个候选人，这N个候选人之间有些人有上下级关系，这些关系构成一棵有根树，每个人有一个开心值，求不存在有直接上下级关系的人同时被选中的情况下，选到的人的最大开心值之和是多少。 做法：这一题是用树形DP来求解树的最大权值独立集。 一个人和他的直接上级不能同时被选中，那么就代表着相邻点不能同时被选中，那么这就是一个最大独立集的问题。求解无向图的最大独立集是NP问题，但是求解树的最大独立集是非常简单的，这里使用树形DP的方法来解决。 设f[i][1/0]为选择/不选点i时以i为根的子树的最大答案，那么易得状态转移方程： f[i][1]=val[i]+Σmax(f[j][0],0)(j=son[i]) f[i][0]=Σmax(f[j][1],f[j][0],0)(j=son[i]) 最后问题的答案就是max(f[root][1],f[root][0])，时间复杂度为O(N)。 以下是本人代码：
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n,first[10010]={0},f[10010][2]={0},val[10010],rt,tot=0; bool root[10010]={0}; struct edge {int v,next;} e[10010]; void insert(int a,int b) { e[++tot].v=b,e[tot].next=first[a],first[a]=tot; } void dp(int v) { f[v][1]=f[v][0]=0; for(int i=first[v];i;i=e[i].next) { dp(e[i].v); if (f[e[i].v][0]>0) f[v][1]+=f[e[i].v][0]; if (max(f[e[i].v][1],f[e[i].v][0])>0) f[v][0]+=max(f[e[i].v][1],f[e[i].v][0]); } f[v][1]+=val[v]; } int main() { while(scanf("%d",&n)!=EOF) { tot=0; memset(first,0,sizeof(first)); memset(root,0,sizeof(root)); for(int i=1;i<=n;i++) scanf("%d",&val[i]); for(int i=1,x,y;;i++) { scanf("%d%d",&x,&y); if (!x&&!y) break; root[x]=1; insert(y,x); } for(int i=1;i<=n;i++) if (!root[i]) { rt=i; break; } dp(rt); printf("%d\n",max(f[rt][1],f[rt][0])); } return 0; }