题目链接
题目描述
某大学有 n 个职员，编号为 1…n。
他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 r[i] ，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。
初步思路
首先这肯定是一棵有根树，然后我们就是要输出根节点去或不去的最大值。
下面我们看看如何求这个最大值。
首先，对于节点x来说，如果x去的话，那他的儿子节点都是不能去的，也就是说以节点x为根的子树的快乐值为节点x快乐值与他所有以儿子节点为根的子树的快乐值之和；如果x不去的话，那他的儿子是都可以去的，也就是说以节点x为根的子树的快乐值为节点x所有以儿子节点为根的子树的快乐值之和，但由于他的儿子是都可以去的，所以我们要取儿子节点去与不去的最大值然后再求和。
那么我们定义dp[x][i]; x代表以节点x为根的子树； i为0时代表节点x不参加party，i为1时代表节点x参加party；
于是初始状态 dp[x][1] = a[i]; //a[i]为第i号职员的快乐值
然后对于dp[x][1]来说，他还要加上所有儿子的权值，即
dp
[x
][1] += dp
[son
[x
][i
]][0];
对于dp[x][0]来说，他还要加上所有儿子去与不去的最大值之和，即
dp
[x
][0] += Max(dp
[son
[x
][i
]][0], dp
[son
[x
][i
]][1]);
最后输出Max(dp[root][0], dp[root][1])就好了。
上代码！！！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<map>
#define ll long long
#define pi acos(-1)
#define inf 0x3f3f3f3f
#define pii pair<int, int>
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define piii pair<pii, int>
#define uf(a, b, i) for (register int i = (a); i <= (b); ++i)
#define df(a, b, i) for (register int i = (a); i >= (b); --i)
using namespace std
;
inline int read() {
int x
= 0, f
= 1;
char ch
= getchar();
while(ch
< '0' || ch
> '9') {
if(ch
== '-') f
= -1;
ch
= getchar();
}
while(ch
>= '0' && ch
<= '9') {
x
= x
* 10 + ch
- '0';
ch
= getchar();
}
return x
* f
;
}
template
<class T
>
inline void print(T x
) {
if(x
> 9) print(x
/10);
putchar(x
%10 + '0');
}
template
<class T
>
T
Max(T a
, T b
) {
return a
> b
? a
: b
;
}
template
<class T
>
T
Min(T a
, T b
) {
return a
< b
? a
: b
;
}
const ll mod
= 1e9 + 7;
int n
, root
;
int a
[6003];
int dp
[6003][2];
bool vis
[6003];
vector
<int> son
[6003];
void dfs(int x
) {
dp
[x
][1] = a
[x
];
for (int i
= 0; i
< son
[x
].size(); ++i
) {
dfs(son
[x
][i
]);
dp
[x
][0] += Max(dp
[son
[x
][i
]][0], dp
[son
[x
][i
]][1]);
dp
[x
][1] += dp
[son
[x
][i
]][0];
}
}
void scan() {
n
= read();
uf
(1, n
, i
) a
[i
] = read();
uf
(1, n
-1, i
) {
int l
, k
;
l
= read(); k
= read();
son
[k
].push_back(l
);
vis
[l
] = 1;
}
}
void work() {
uf
(1, n
, i
) {
if (!vis
[i
]) {
root
= i
;
break;
}
}
dfs(root
);
print(Max(dp
[root
][0], dp
[root
][1]));
putchar('\n');
}
int main() {
scan();
work();
return 0;
}
