Bzoj 1040(环套树DP)

bzoj 1040
环套树DP相关解法
本题$n$个点$n$条边,显然是基环树DP。
然而没有保证整幅图都是连通的,所以这要处理一个基环树森林,每棵树树形DP后的答案累加即可,dp方程类似于没有丧尸上司的舞会

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 1000000 + 5;
struct edge {
int v;
}ed[MAXN * 2];
int n, en, wi[MAXN], Pu, Pv, PE, vi[MAXN];
LL dp[MAXN][2];
vector<int> G[MAXN];
void ins(int a, int b) {
en++, ed[en].v = b, G[a].push_back(en);
}
void tdp(int u, int fa) {
dp[u][0] = 0, dp[u][1] = wi[u];
for (int i=0;i<G[u].size();i++) {
if (G[u][i] == PE || G[u][i] == (PE ^ 1)) continue;//已经断开,不能通过,否则有后效性
edge p = ed[G[u][i]];
int v = p.v;
if (v != fa) {
tdp(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
}
void dfs(int u, int fa) {
for (int i=0;i<G[u].size();i++) {
edge p = ed[G[u][i]];
int v = p.v;
if (v != fa) {
if (!vi[v]) vi[v] = true, dfs(v, u);
else Pu = u, Pv = v, PE = G[u][i];//找断开不构成环的边
}
}
}
void clean() {
en = -1;//边从0开始,方便找出该边的反边
for (int i=0;i<=n;i++) vi[i] = false, G[i].clear();
}
void solve() {
clean();
for (int i=1;i<=n;i++) {
int x;
scanf("%d%d", &wi[i], &x);
ins(x, i), ins(i, x);//看似有向实质无向
}
LL ans = 0;
for (int i=1;i<=n;i++) {//基环树森林一一处理
if (!vi[i]) {
dfs(i, -1);
tdp(Pu, -1);
LL tmp = dp[Pu][0];
tdp(Pv, -1);
tmp = max(tmp, dp[Pv][0]);
ans += tmp;
}
}
printf("%lld\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d", &n), solve();
return 0;
}

------ 本文结束 ------