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;
}