【洛谷】P1352 没有上司的舞会 的题解

【洛谷】P1352 没有上司的舞会 的题解

题目传送门

题解

经典的树形 DP，典中典qaq

树形 dp，由于一个人去与不去会影响到下一位，所以我们多开一维。

就可以推得两个转移方程：

$$dp[root][0]=\sum _{son(x)}\max (dp[root][0],dp[root][1])$$

$$dp[root][1]=h[root]+\sum _{son(x)}dp[root][0]$$

这样的话，我们只需要找到没有上司的节点 $root$ 为跟，然后通过 fa() 函数进行 dp 的更新就可以了。时间复杂度 $O(n)$。

代码

#include <bits/stdc++.h>
#define lowbit(x) x & (-x)
#define endl "\n"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
namespace fastIO {inline int read() {register int x = 0, f = 1;register char c = getchar();while (c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f;}inline void write(int x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');return;}
}
using namespace fastIO;
vector <int> son[10005];
int dp[10005][2], vis[10005], h[10005], n;
void fa(int x) {dp[x][0] = 0;dp[x][1] = h[x];for(int i = 0; i < son[x].size(); i ++) {int y = son[x][i];fa(y);dp[x][0] += max(dp[y][0], dp[y][1]);dp[x][1] += dp[y][0]; }
}
int main() {//freopen(".in","r",stdin);//freopen(".out","w",stdout);ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);n = read();for(int i = 1; i <= n; i ++) {h[i] = read();}for(int i = 1; i < n; i ++) {int x, y;x = read(), y = read();vis[x] = 1;son[y].push_back(x);}int root;for(int i = 1; i <= n; i ++) {if(!vis[i]) {root = i;break;}}fa(root);cout << max(dp[root][0], dp[root][1]);return 0;
}