题目传送门(BZOJ)
>原文链接<

题解 :

基环森林DP

状态 :

$F[p]$表示一定选$p$,子树中最多能选出多少

$g[p]$表示一定不选$p$,子树中最多能选出多少

转移 :

直接上一般的基环树DP套路即可, 我没有拆边, 对于环上的, 直接不连这条边就行.

对于每棵树的环, 我们只需要删掉环上的某条边$(u, v)$

然后分别强制$u$不选, 做一次树形DP, 强制$v$不选, 做一次树形DP, $ans += \max(g[u], g[v])$即可

树形DP的过程应该是求一个最大独立集的过程

代码 :

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 1001000;#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 100000, stdin), p1==p2)?EOF:*p1++)char buf[100000],*p1,*p2;int a[N];long long f[N], g[N];int n, m, fa[N], ra[N], rb[N];inline int rd() { int x = 0; char ch = nc(); while(!isdigit(ch)) ch = nc(); while(isdigit(ch)) x = (x<<1) + (x<<3) + (ch^48), ch = nc(); return x;}struct Edge { int to; Edge *next;}*h[N],e[N<<1];inline void Add_Edge(int u, int v) { static int _ = 0; Edge *tmp = &e[++_]; tmp->to = v; tmp->next = h[u]; h[u] = tmp;}int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}void dfs(int p, int fr) { f[p] = a[p], g[p] = 0; for(Edge *i = h[p]; i; i = i->next) { if(i->to != fr) dfs(i->to, p), g[p] += max(g[i->to], f[i->to]), f[p] += g[i->to]; }}int main() { n = rd(); for(int i = 1; i <= n; i ++ ) fa[i] = i; for(int i = 1; i <= n; i ++ ) { a[i] = rd(); int to = rd(); if(find(i) != find(to)) { Add_Edge(i, to); Add_Edge(to, i); fa[fa[i]] = fa[to]; } else { ra[++m] = i, rb[m] = to; } } long long ans = 0; for(int i = 1; i <= m; i ++ ) { long long t = 0; dfs(ra[i], 0), t = g[ra[i]]; dfs(rb[i], 0), t = max(t, g[rb[i]]); ans += t; } printf("%lld\n", ans);}