P2607 [ZJOI2008] 骑士
[P2607 ZJOI2008] 骑士 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
目录题目大意
给你一个 \(n\) 个点，\(n\) 条边的基环树森林。
你可以从中选择若干个点，满足两两之间不存在边相连。
每个点有一个权值，请问最大的权值和是多少。
思路
对于每棵基环树，记录返祖边连接的两个点 \(x , y\)
设 \(dp_{x , 0/1}\) 表示点 \(x\) 选、不选时，以 \(x\) 为根的子树最大权值和是多少。
显然
\[dp_{x , 0} = \sum_{y \in son(x)} \max \{dp_{y , 0} , dp_{y , 1}\} \newline dp_{x , 1} = \sum_{y \in son(x)} dp_{y , 0} \]因为 \(x , y\) 最多只能有一个选，所以没棵基环树的答案为 \(\max \{dp_{x , 0} , dp_{y , 0}\}\)
把全部基环树的答案加起来就好了
不知道为什么 c++17 开了 \(O_2\) 就 T 了。
code
#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 1e6 + 5;
int n , vis[N] , cnt = 1 , hd[N] , pos , to , flgy;
LL a[N] , dp[N][2] , ans;
struct E {
int to , nt;
} e[N << 1];
void add (int x , int y) { e[++cnt].to = y , e[cnt].nt = hd[x] , hd[x] = cnt; }
void dfs1 (int x , int fa) {
int y;
vis[x] = 1;
for (int i = hd[x] ; i ; i = e[i].nt) {
y = e[i].to;
if (y == fa) continue;
if (!vis[y])
dfs1 (y , x);
else
pos = i;
}
}
LL dfs (int x , int fa) {
int y;
dp[x][0] = 0;
dp[x][1] = a[x];
for (int i = hd[x] ; i ; i = e[i].nt) {
y = e[i].to;
if (y == fa || i == pos || i == (pos ^ 1)) continue;
dfs (y , x);
dp[x][0] += max (dp[y][0] , dp[y][1]);
dp[x][1] += dp[y][0];
}
}
int main () {
int x , y;
scanf ("%d" , &n);
fu (i , 1 , n) {
scanf ("%lld%d" , &a[i] , &x);
add (i , x) , add (x , i);
}
LL ans1;
fu (i , 1 , n) {
if (vis[i]) continue;
dfs1 (i , 0);
x = e[pos].to , y = e[pos ^ 1].to;
dfs (x , 0);
ans1 = dp[x][0];
dfs (y , 0);
ans += max (ans1 , dp[y][0]);
}
printf ("%lld" , ans);
return 0;
}