InputEmployees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go T lines that describe a supervisor relation tree. Each line of the tree specification has the form:
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0OutputOutput should contain the maximal sum of guests‘ ratings.
Sample Input
7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0
Sample Output
5
题解：树形DP。对于每个人，我们储存下比他职位低的下标，并对比他职位低的人打上标记代表这个人有上司。dp[i][1]代表选i这个人，dp[i][0]代表不选这个人，然后从底层开始，对上一层dp[x][1]+=dp[x-1][0];
dp[x][0]+=max(dp[x-1][1],dp[x-1][0]);
然后最大值为： max(dp[root][1],dp[root][0]);root为没有标记的那个人，即没有任何下属的人；
参考代码为：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cstdlib>
#include<set>
using namespace std;
const int maxn=1e4+10;
int N,u,v,w[maxn],vis[maxn],dp[maxn][2];
vector<int> vec[maxn];
void solve(int x)
{
for(int i=0;i<vec[x].size();i++)
{
solve(vec[x][i]);
dp[x][1]+=dp[vec[x][i]][0];
dp[x][0]+=max(dp[vec[x][i]][0],dp[vec[x][i]][1]);
}
}
int main()
{
while(~scanf("%d",&N))
{
for(int i=0;i<=N;i++) vec[i].clear();
memset(vis,0,sizeof vis);
memset(dp,0,sizeof dp);
for(int i=1;i<=N;i++) scanf("%d",w+i);
for(int i=1;i<=N;i++) dp[i][1]=w[i];
while(scanf("%d%d",&u,&v), u+v)
{
vec[v].push_back(u);
vis[u]=1;
}
int flag;
for(int i=1;i<=N;i++)
{
if(!vis[i])
{
solve(i);
flag=i;
break;
}
}
int Max=max(dp[flag][1],dp[flag][0]);
printf("%d\n",Max);
}
return 0;
}
原文：https://www.cnblogs.com/songorz/p/9409726.html