P2607 [ZJOI2008] 骑士

本文主要是介绍P2607 [ZJOI2008] 骑士，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

P2607 [ZJOI2008] 骑士

[P2607 ZJOI2008] 骑士 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目大意

给你一个 $n$ 个点，$n$ 条边的基环树森林。

你可以从中选择若干个点，满足两两之间不存在边相连。

每个点有一个权值，请问最大的权值和是多少。

思路

对于每棵基环树，记录返祖边连接的两个点 $x,y$

设 $d{p}_{x,0/1}$ 表示点 $x$ 选、不选时，以 $x$ 为根的子树最大权值和是多少。

显然
d p x , 0 = ∑ y ∈ s o n ( x ) max ⁡ { d p y , 0 , d p y , 1 } d p x , 1 = ∑ y ∈ s o n ( x ) d p y , 0 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} dpx,0​=y∈son(x)∑​max{dpy,0​,dpy,1​}dpx,1​=y∈son(x)∑​dpy,0​
因为 $x,y$ 最多只能有一个选，所以没棵基环树的答案为 max ⁡ { d p x , 0 , d p y , 0 } \max \{dp_{x , 0} , dp_{y , 0}\} max{dpx,0​,dpy,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;
}

这篇关于P2607 [ZJOI2008] 骑士的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---