学习笔记_ 基环树DP [DP, 树, 基环树]

等了好久才开始学的…

今天看见有个疑似基环树的题就学习了一个

沙茶的 基环树DP不详解

环基树的DP可以用来解决一类$n$个点$n$条边的”树”上的问题

环基树的基本思想就是找到环, 找环上任意一条边$b_i$, 任何断掉他

假设一个点的状态为$0$的时候, 他周围的点的状态可以是$0$也可以是$1$, 我们就从$b_i.from$和$b_i.to$这两个点分别出发 进行树上的DP(这时候已经断掉了一条边, 所以是树上的DP), 比较这两个点的$0$状态的收益大小, 收益大的加进$ans$中

为什么是$0​$状态? 因为我们从$from​$出发的时候并不知道$to​$会是什么状态, 进行DP的时候也不能固定$to​$的状态(而他们之间又有边相连, 他们之间的状态), 只好定一个无论$to​$是什么状态都可以的状态作为初始状态; 以$to​$为起点进行DP的时候亦然

沙茶水过的 丰年好大水题

[ZJOI2008]骑士

就没有上司的舞会, 套一下找环和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
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (1000000 + 5)
#define LL long long
using namespace std;
struct edg
{
int from, to, next;
}b[MAXN << 1];
int g[MAXN], cntb = -1, cirfrom, cirto, ciredg, n;
bool vis[MAXN];
LL val[MAXN], ans, f[MAXN][2];
void adn(int from, int to)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
g[from] = cntb;
}
void cir(int dq, int fe)
{
vis[dq] = true;
for (int i = g[dq]; ~i; i = b[i].next)
if ((i ^ 1) != fe)
{
if (vis[b[i].to])
{
cirfrom = b[i].from;
cirto = b[i].to;
ciredg = i;
}
else
cir(b[i].to, i);
}
}
void zkj(int dq, int fe)
{
f[dq][0] = 0, f[dq][1] = val[dq];
for (int i = g[dq]; ~i; i = b[i].next)
if ((i ^ 1) != fe && i != ciredg && (i ^ 1) != ciredg)
{
zkj(b[i].to, i);
f[dq][0] += max(f[b[i].to][0], f[b[i].to][1]);
f[dq][1] += f[b[i].to][0];
}
}
int main()
{
// cout << "Hello world!" << endl;
memset(g, -1, sizeof(g));
memset(vis, false, sizeof(vis));
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int srx;
scanf("%lld%d", &val[i], &srx);
adn(srx, i);
adn(i, srx);
}
for (int i = 1; i <= n; i++)
if (!vis[i])
{
cir(i, -1);
zkj(cirfrom, -1);
// LL REfun = max(f[cirfrom][0], f[cirfrom][1]);
LL REfun = f[cirfrom][0];
zkj(cirto, -1);
ans += max(REfun, f[cirto][0]);
// ans += max(max(f[cirto][0], f[cirto][1]), REfun);
}
printf("%lld", ans);
return 0;
}

/*
3
10 2
20 3
30 1
*/

from 大半年前(2017-10-28 20:39)就AC的守望:

所以可能存在环和多个连通块
联想一道题 城市环路
把环分开
因为两个端点矛盾
所以两个端点分别dfs
累加每个连通块的最大值

太强了Orzzzzzzz

[POI2008]枪战Maf

他们好像都写的贪心…

但是为什么我一眼基环树DP? 挖个坑

By 只会丢人的 Cansult