一个公司的职员是分级制度的，所有员工刚好是一个树形结构，现在公司要举办一个聚会，邀请部分职员来参加。
要求：
1.为了聚会有趣，若邀请了一个职员，则该职员的直接上级（即父节点）和直接下级（即儿子节点）都不能被邀请
2.每一个员工都有一个兴奋值，在满足1的条件下，要使得邀请来的员工的兴奋值最高
输出最高的兴奋值。
简单的树形DP
dp[i][1]:表示以i为根的子树，邀请节点i的最大兴奋值
dp[i][0]:表示以i为根的子树，不邀请节点i的最大兴奋值
先根据入度找出整棵树的根节点，
然后一次DFS即可。
poj提交代码：
#include<cstdio>
#include<cstring> using namespace std; const int maxn=;
const int inf=0x3f3f3f3f; inline int max(int x,int y)
{
return x>y?x:y;
} int dp[maxn][];
int in[maxn];
int rate[maxn];
struct Edge
{
int to,next;
};
Edge edge[maxn];
int head[maxn];
int tot; void init()
{
memset(head,-,sizeof head);
tot=;
memset(in,,sizeof in);
} void addedge(int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
} void dfs(int u,int pre); int main()
{
int n;
while(~scanf("%d",&n))
{
init();
scanf("%d",&rate[]);
if(!n&&!rate[])
break;
for(int i=;i<=n;i++)
{
scanf("%d",&rate[i]);
}
for(int i=;i<n;i++)
{
int u,v;
scanf("%d%d",&v,&u);
addedge(u,v);
in[v]++;
}
int root;
for(int i=;i<=n;i++)
{
if(!in[i])
{
root=i;
break;
}
}
dfs(root,-);
printf("%d\n",max(dp[root][],dp[root][]));
}
return ;
} void dfs(int u,int pre)
{
dp[u][]=rate[u];
dp[u][]=;
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre)
continue;
dfs(v,u);
dp[u][]+=dp[v][];
dp[u][]+=max(dp[v][],dp[v][]);
}
}
HDU的1520和POJ的2342是一样的，但是输入有点不同
hdu提交代码：
#include<cstdio>
#include<cstring> using namespace std; const int maxn=;
const int inf=0x3f3f3f3f; inline int max(int x,int y)
{
return x>y?x:y;
} int dp[maxn][];
int in[maxn];
int rate[maxn];
struct Edge
{
int to,next;
};
Edge edge[maxn];
int head[maxn];
int tot; void init()
{
memset(head,-,sizeof head);
tot=;
memset(in,,sizeof in);
} void addedge(int u,int v)
{
edge[tot].to=v;
edge[tot].next=head[u];
head[u]=tot++;
} void dfs(int u,int pre); int main()
{
int n;
while(~scanf("%d",&n))
{
init();
for(int i=;i<=n;i++)
{
scanf("%d",&rate[i]);
}
while(true)
{
int u,v;
scanf("%d%d",&v,&u);
if(!u&&!v)
break;
addedge(u,v);
in[v]++;
}
int root;
for(int i=;i<=n;i++)
{
if(!in[i])
{
root=i;
break;
}
}
dfs(root,-);
printf("%d\n",max(dp[root][],dp[root][]));
}
return ;
} void dfs(int u,int pre)
{
dp[u][]=rate[u];
dp[u][]=;
for(int i=head[u];~i;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre)
continue;
dfs(v,u);
dp[u][]+=dp[v][];
dp[u][]+=max(dp[v][],dp[v][]);
}
}