写的大多只是思路，比较简单的细节和证明过程就不放了，有需者自取。
基环树简介
简单说一说基环树吧。由名字扩展可得这是一类以环为基础的树（当然显然它不是树。
通常的表现形式是一棵树再加一条非树边，把图画出来是一种向外发散的有趣图案。
体现在【题目条件】上就是一个 (n) 个点 (n) 条边的连通图或保证每一个点的入度 / 出度为 (1) （有向图：前者称为外向树，后者称为内向树）。
常常会把一些在树上做的 dp 放在基环树上以提高题目难度。
惯用思路是先把以环上的点为根的子树内的信息跑完，再整合环的信息。或者直接拆掉环上的边跑树 dp，当然也有其他的各种神魔做法。
好像后续还有仙人掌、仙人球之类的复杂结构。
「ZJOI2008」骑士
题目大意和树形 dp 板子没有上司的舞会类似，只不过树改为了基环树。
考虑环上任意两点不可能都取到，所以可以断掉环上任意一边，以该边两端点 (a, b) 分开跑舞会的 dp 即可。
记 (dp(u, 0)) 表示 (u) 节点不取能得到的最大值，则该基环树的答案为 (max(dp(a, 0), dp(b, 0)))。
基环树题目多半都是基环树森林，并且常常有子环。（（
#include <cstdio>
#include <vector>
using namespace std;
typedef long long LL;
LL Max(LL x, LL y) { return x > y ? x : y; }
LL Min(LL x, LL y) { return x < y ? x : y; }
LL Abs(LL x) { return x < 0 ? -x : x; }
int read() {
int k = 1, x = 0;
char s = getchar();
while (s < '0' || s > '9') {
if (s == '-')
k = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * k;
}
void write(LL x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void print(LL x, char s) {
write(x);
putchar(s);
}
const int MAXN = 1e6 + 5;
LL dp[MAXN][2];
bool flag[MAXN], vis[MAXN];
int val[MAXN], to[MAXN], s, t, p;
struct edge {
int v, pos;
edge() {}
edge(int V, int Pos) {
v = V;
pos = Pos;
}
};
vector<edge> mp[MAXN];
void Add_Edge(int u, int v, int p) {
mp[u].push_back(edge(v, p));
mp[v].push_back(edge(u, p));
}
void Circle(int u, int fa) {
vis[u] = true;
for(size_t i = 0; i < mp[u].size(); i++) {
int v = mp[u][i].v;
if(v == fa)
continue;
if(vis[v]) {
s = u;
t = v;
p = mp[u][i].pos;
continue;
}
Circle(v, u);
}
}
void Tree_Dp(int u, int fa) {
dp[u][0] = 0;
dp[u][1] = val[u];
for(size_t i = 0; i < mp[u].size(); i++) {
int v = mp[u][i].v;
if(v == fa || flag[mp[u][i].pos])
continue;
Tree_Dp(v, u);
dp[u][1] += dp[v][0];
dp[u][0] += Max(dp[v][0], dp[v][1]);
}
}
int main() {
int n = read();
for(int i = 1; i <= n; i++) {
val[i] = read(), to[i] = read();
Add_Edge(i, to[i], i);
}
LL ans = 0;
for(int i = 1; i <= n; i++) {
if(vis[i])
continue;
Circle(i, -1);
LL tmp = -1;
flag[p] = true;
Tree_Dp(s, -1);
tmp = dp[s][0];
Tree_Dp(t, -1);
tmp = Max(tmp, dp[t][0]);
flag[p] = false;
ans += tmp;
}
print(ans, '
');
return 0;
}
「BZOJ1791」「IOI2008」Island 岛屿
求基环树森林中基环树们的直径和。
有题可知每一颗基环树都是一颗内向树。记一颗基环树环上节点的点集为 (V)。
对于每一颗根在环上的子树我们定义 (g(u)) 表示以 (u) 为根的子树的直径，(f(u)) 表示以 (u) 为起点在该子树中的最长链。
则可知整棵基环树的直径为 (max(g(u))) 和 (max(f(a) + (a o b) + f(b))) 的较大值，其中 (u, a, b in V)。
前一个东西简单，可以直接拓扑排序。后一个东西借鉴单调队列的思想，拆开算贡献就好了，最后扫一遍。
注意后面的那个东西需要区分 ((a o b)) 和 ((b o a))。
#include <cstdio>
typedef long long LL;
LL Max(LL x, LL y) { return x > y ? x : y; }
LL Min(LL x, LL y) { return x < y ? x : y; }
LL Abs(LL x) { return x < 0 ? -x : x; }
int read() {
int k = 1, x = 0;
char s = getchar();
while (s < '0' || s > '9') {
if (s == '-')
k = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * k;
}
void write(LL x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void print(LL x, char s) {
write(x);
putchar(s);
}
const LL INF = 1e18;
const int MAXN = 1e6 + 5;
struct node {
int v, w;
node() {}
node(int V, int W) {
v = V;
w = W;
}
} q[MAXN];
LL f[MAXN], g[MAXN];
int que[MAXN], in[MAXN], n;
int main() {
n = read();
for(int i = 1; i <= n; i++) {
q[i].v = read(), q[i].w = read();
in[q[i].v]++;
}
int head = 1, tail = 0;
for(int i = 1; i <= n; i++)
if(!in[i])
que[++tail] = i;
while(head <= tail) {
int u = que[head++], v = q[u].v;
LL val = f[u] + q[u].w;
g[v] = Max(g[v], f[v] + val);
g[v] = Max(g[v], g[u]);
f[v] = Max(f[v], val);
in[v]--;
if(!in[v])
que[++tail] = v;
}
LL ans = 0;
for(int i = 1, u, End; i <= n; i++)
if(in[i]) {
u = i, End = u;
LL m1 = f[u], m2 = f[u], pre = q[u].w, res1 = g[u], res2 = -INF;
u = q[u].v;
while(u != End) {
in[u] = 0;
res1 = Max(res1, g[u]);
res1 = Max(res1, f[u] + m1 + pre);
res2 = Max(res2, f[u] + m2 - pre);
m1 = Max(m1, f[u] - pre);
m2 = Max(m2, f[u] + pre);
pre += q[u].w;
u = q[u].v;
}
ans += Max(res1, res2 + pre);
}
print(ans, '
');
return 0;
}
「BZOJ2791」「Poi2012」Rendezvous
码农屑题。就不说题目描述了，分类讨论。
若 (a) 和 (b) 不在一颗基环树上，肯定无解。
否则，若 (a) 和 (b) 在同一颗基环树的同一个子树下，由第二个限定条件可知一定是到 lca 最优。
记 (dep(u)) 为 (u) 节点在该子树下的深度，(lca(u, v)) 为节点 (u) 和 (v) 在该子树上的最近公共祖先，答案即为：
[x = dep(a) - dep(lca(a, b)), y = dep(b) - dep(lca(a, b))
]
若 (a) 和 (b) 不在同一颗基环树的同一个子树下。
则考虑拆分整个过程。不难发现可以等价于 (a) 先走到其子树在环上的根，(b) 同理，再考虑环上这两点的答案。
分别考虑 (a o b) 的 (x, y) 和 (b o a) 的 (x, y) ，再按限定条件输出。
更改了基环树找环的方法，统一使用拓扑霍霍。
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
int Max(int x, int y) { return x > y ? x : y; }
int Min(int x, int y) { return x < y ? x : y; }
int Abs(int x) { return x < 0 ? -x : x; }
int read() {
int k = 1, x = 0;
char s = getchar();
while (s < '0' || s > '9') {
if (s == '-')
k = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * k;
}
void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void print(int x, char s) {
write(x);
putchar(s);
}
const int MAXN = 5e5 + 5;
queue<int> q;
bool vis[MAXN];
// vis 工具
vector<int> in[MAXN], out[MAXN];
int key[MAXN], flag[MAXN], f[MAXN][25], dep[MAXN], Group[MAXN], pos[MAXN], size[MAXN], tot = 0, len = 0;
// flag 是否在环上
// key 该子树在环上的根
// Group 属于那一个连通块
void dfs(int u, int fa) {
key[u] = tot;
for(size_t i = 0; i < out[u].size(); i++) {
int v = out[u][i];
if(v == fa || flag[v])
continue;
dep[v] = dep[u] + 1;
f[v][0] = u;
for(int i = 1; i < 25; i++)
f[v][i] = f[f[v][i - 1]][i - 1];
dfs(v, u);
}
}
int lca(int u, int v) {
if(dep[u] < dep[v])
u ^= v ^= u ^= v;
for(int i = 24; i >= 0; i--)
if(dep[f[u][i]] >= dep[v])
u = f[u][i];
if(u == v)
return u;
for(int i = 24; i >= 0; i--)
if(f[u][i] != f[v][i]) {
u = f[u][i];
v = f[v][i];
}
return f[u][0];
}
void Color(int u, int fa) {
Group[u] = tot;
for(size_t i = 0; i < out[u].size(); i++) {
int v = out[u][i];
if(Group[v])
continue;
Color(v, u);
}
}
void Get_Circle(int u, int fa) {
if(vis[u])
return ;
pos[u] = ++tot;
// printf("pos[%d] = %d
", u, pos[u]);
vis[u] = true;
for(size_t i = 0; i < in[u].size(); i++) {
int v = in[u][i];
if(v == fa)
continue;
if(flag[v])
Get_Circle(v, u);
}
}
int main() {
// freopen("13.in", "r", stdin);
int n = read(), m = read();
for(int i = 1, v; i <= n; i++) {
v = read();
in[i].push_back(v);
flag[v]++;
out[v].push_back(i);
}
// 是否在环上
for(int i = 1; i <= n; i++)
if(!flag[i])
q.push(i);
while(!q.empty()) {
int u = q.front();
q.pop();
for(size_t i = 0; i < in[u].size(); i++) {
int v = in[u][i];
flag[v]--;
if(!flag[v])
q.push(v);
}
}
// LCA 初始化
for(int i = 1; i <= n; i++)
if(flag[i]) {
dep[i] = 1;
tot = i;
dfs(i, -1);
}
tot = 0;
// 在哪一个连通块中
for(int i = 1; i <= n; i++)
if(flag[i] && !Group[i]) {
tot++;
Color(i, -1);
}
// 判断环间两点距离
for(int i = 1; i <= n; i++)
if(flag[i] && !vis[i]) {
tot = 0;
Get_Circle(i, -1);
size[Group[i]] = tot;
}
// for(int i = 1; i <= n; i++)
// printf("flag[%d] = %d, pos[%d] = %d
", i, flag[i], i, pos[i]);
for(int i = 1, a, b; i <= m; i++) {
a = read(), b = read();
if(Group[a] != Group[b])
print(-1, ' '), print(-1, '
');
else if(key[a] == key[b]) {
// printf("Asoul %d %d %d
", key[a], key[b], lca(a, b));
int Lca = lca(a, b), x = dep[a] - dep[Lca], y = dep[b] - dep[Lca];
print(x, ' '), print(y, '
');
}
else {
// puts("Asoul");
int root_a = key[a], root_b = key[b], dist;
dist = (pos[root_b] - pos[root_a] + size[Group[a]]) % size[Group[a]];
int x_1 = dep[a] - 1 + dist, y_1 = dep[b] - 1;
dist = (pos[root_a] - pos[root_b] + size[Group[a]]) % size[Group[a]];
int x_2 = dep[a] - 1, y_2 = dep[b] - 1 + dist;
// printf("%d %d %d %d
", x_1, y_1, x_2, y_2);
if(Max(x_1, y_1) < Max(x_2, y_2))
print(x_1, ' '), print(y_1, '
');
else if(Max(x_1, y_1) > Max(x_2, y_2))
print(x_2, ' '), print(y_2, '
');
else {
if(Min(x_1, y_1) < Min(x_2, y_2))
print(x_1, ' '), print(y_1, '
');
else if(Min(x_1, y_1) > Min(x_2, y_2))
print(x_2, ' '), print(y_2, '
');
else {
if(x_1 >= y_1)
print(x_1, ' '), print(y_1, '
');
else
print(x_2, ' '), print(y_2, '
');
}
}
}
}
return 0;
}
「CF1027F」 Session in BSU
码量小清新！
有 (n) 门考试，对于第 (i) 门可以在 (a_i)，(b_i) 两个时间去考，一个时间只能考一门，求考完所有考试的情况下，整个考试周期最早到多久结束（即使得最后一门考试的时间最早）。如果不能考完所有考试，输出 (-1)。
考虑 (a_i) 和 (b_i) 连边，每一条边即表示一个我们需要处理的分配时间需求。这样就能形成一个懒得定性的图。
考虑每一个连通块。
若该连通块点数小于边数，则会出现需求量大于时间点数的情况，无解，结束整个程序。
若该连通块点数等于边数，则该连通块内的所有时间点都会分配考试，故答案即为该连通块内的时间最大值。
若该连通块点数大于边数，其实只能是边数比点数少一的情况，所以这是一颗树。即需求量比时间点少一，那就说明该连通块有一个点可以不取，此时答案即为该连通块内的时间最小值。
最后答案即为所以连通块答案的最大值。
统计边数啦点数啦之类的都应该是 dfs 的基本功了嘛。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int Max(int x, int y) { return x > y ? x : y; }
int Min(int x, int y) { return x < y ? x : y; }
int Abs(int x) { return x < 0 ? -x : x; }
int read() {
int k = 1, x = 0;
char s = getchar();
while (s < '0' || s > '9') {
if (s == '-')
k = -1;
s = getchar();
}
while (s >= '0' && s <= '9') {
x = (x << 3) + (x << 1) + s - '0';
s = getchar();
}
return x * k;
}
void write(int x) {
if (x < 0) {
putchar('-');
x = -x;
}
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
void print(int x, char s) {
write(x);
putchar(s);
}
const int MAXN = 1e6 + 5;
struct edge {
int u, v;
edge() {}
edge(int U, int V) {
u = U;
v = V;
}
} q[MAXN];
bool vis[MAXN << 1];
vector<int> mp[MAXN << 1];
int ma1, ma2, cnt, tot, num[MAXN << 1];
void Add_Edge(int u, int v) {
mp[u].push_back(v);
mp[v].push_back(u);
}
void dfs(int u, int fa) {
vis[u] = true;
tot++;
if(u > ma1) {
ma2 = ma1;
ma1 = u;
}
else if(u > ma2)
ma2 = u;
for(size_t i = 0; i < mp[u].size(); i++) {
int v = mp[u][i];
cnt++;
if(v == fa || vis[v])
continue;
dfs(v, u);
}
}
int main() {
int n = read();
for(int i = 1; i <= n; i++) {
q[i].u = read(), q[i].v = read();
num[i] = q[i].u, num[i + n] = q[i].v;
}
sort(num + 1, num + (n << 1) + 1);
int len = unique(num + 1, num + (n << 1) + 1) - num - 1;
for(int i = 1; i <= n; i++) {
q[i].u = lower_bound(num + 1, num + len + 1, q[i].u) - num, q[i].v = lower_bound(num + 1, num + len + 1, q[i].v) - num;
Add_Edge(q[i].u, q[i].v);
}
int ans = 0;
for(int i = 1; i <= len; i++)
if(!vis[i]) {
ma1 = 0, ma2 = 0, cnt = 0, tot = 0;
dfs(i, -1);
cnt /= 2;
if(cnt < tot)
ans = Max(ans, ma2);
else if(cnt == tot)
ans = Max(ans, ma1);
else {
print(-1, '
');
return 0;
}
}
print(num[ans], '
');
return 0;
}
「BZOJ3037」创世纪
基环森林上贪心题目。
根据题目要求，对于每一颗基环树，叶子一定不能取，且环上最多取一半。
那么就直接从叶子开始，如果可行就取，一直取到环上。
实现方式多种多样，可以采用拓扑的先跑基环树，单跑环（单环拓扑进不去）的短码写法。
证明在补了在补了 /fad。