【洛谷】P1352 没有上司的舞会 的题解
题目传送门
题解
经典的树形 DP，典中典qaq
树形 dp，由于一个人去与不去会影响到下一位，所以我们多开一维。
就可以推得两个转移方程：
d p [ r o o t ] [ 0 ] = ∑ s o n ( x ) max ( d p [ r o o t ] [ 0 ] , d p [ r o o t ] [ 1 ] ) dp[root][0] = \sum_{son(x)} \max(dp[root][0], dp[root][1]) dp[root][0]=son(x)∑max(dp[root][0],dp[root][1])
d p [ r o o t ] [ 1 ] = h [ r o o t ] + ∑ s o n ( x ) d p [ r o o t ] [ 0 ] dp[root][1] = h[root] + \sum_{son(x)} dp[root][0] dp[root][1]=h[root]+son(x)∑dp[root][0]
这样的话，我们只需要找到没有上司的节点 r o o t root root 为跟，然后通过 fa() 函数进行 dp 的更新就可以了。时间复杂度 O ( n ) O(n) 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;
}
