水题笔记_ BZOJ3319 黑白树 [并查集, 清奇脑回路]

把几个错误的想法拼起来就可以AC啦

人生成就达成: hack了学姐的程序 和辣文第二谈笑风生 向BZOJ丢了一组数据

qwq

Info:这道题网上许多题解都是假的, 这道题确实可以只用并查集做到$\mathrm O(n)$

Warning: 写这篇题解的时候宽嫂有点激动…有一些奇怪的吐槽大家可以自动忽略 XD

惊奇的发现舒老师在两天前过了这题 虽然加强数据后被卡到9.5s差点没过 舒老师太强啦Orzzz

懵逼的 题目

qwqwq

扯淡的 题解

混乱的 思路

下面是想题时候的碎碎念…其实就是一堆吐槽 不看也罢

(昊哥给我丢了一道思(维)博(学)题, 昊哥已经确定这个题是并查集并且是要求$\mathrm O(n)$的做法)

树剖是$\mathrm O(n \lg^2 n)$的…被昊哥喷

如果我倒着做…好像没什么用…确定哪些点受影响好像还是$\mathrm O(n \lg^2 n)$的…

如果我把白边缩起来, 这样每一个点的祖先就是离他最近的黑边了吧?

  • 修改就GG了吧…

如果我把黑边缩起来, 这样修改的总复杂度是$\mathrm O(n)$的吧?

  • 查询也GG了啊…不能路径压缩…

然后一晚上就过去了…

第二天…

如果…我 把白边黑边分别缩起来…

然后…缩黑边的时候顺便把白边的fa设成自己…

  • 但是….不能路径压缩??????????

GG

Emmmmmmmmmmmmmmmmmmmmmmmm….

我如果倒过来…先把修改全部修改完, 然后再撤销, 是不是就可以路径压缩了??? (下面把边化成了点)

  • 把黑点的并查集都初始化为自己, 白点的并查集初始化为自己的父亲
  • 修改, 沿着黑边跑到LCA(要路径压缩), 把经过节点对应的白点并查集的fa设成他自己, 记录哪些节点受到了变化(用vector<int>[])
  • 查询, 直接在白点的并查集上查询祖先即可
  • 撤销, 把当前操作的vector<int>中的节点的白点并查集的fa都变成他自己的父亲即可

复杂度$\mathrm O(n\lg n)$然后没过(应该是倍增LCA太慢了)…

昊哥把网上的$n^2$暴力交上去A了, 比$sunshine$学长写的$\mathrm O(n)$正解还快$3s$…

十分愤怒, 遂生成数据卡之

生成完数据, 发现HXY学姐的正解没过

我格式错了???

然后YCR大佬发现…HXY学姐写了个假的正解…是个假的$\mathrm O(n)$…

遂找ZFF学长的代码, 过了, 遂联系辣文第二卡之

中午回家的时候突然想到, 如果我不找LCA, 而是一遍向上跳一边缩点, 然后每次都沿着并查集的边而非原树中的边跳, 就是$\mathrm O(n)$的了…

中午写了一发, 过了 跑的比ZFF学长快2s XD

Emmmmmmmm….

正了八经的 解释

上面那些都是吐槽, 不看也罢

这个题的思路就是:

既然修改的复杂度高, 就给他路径压缩; 既然查询的复杂度高, 那就也给他路径压缩; 白边黑边放在一起不好压缩, 就分别到两个并查集压缩; 每次黑边都可能向下延伸, 查询如果路径压缩可能GG, 那就把查询先做完, 每次撤销, 这样黑边的范围就可以从下到上, 可以路径压缩了

  • 我们发现, 染黑边, 其实就是染黑这条边的儿子, 这样我们就可以用黑点白点来做了
  • 搞两个并查集fb[], fw[], 分别用于 优化修改的复杂度 和 优化查询的复杂度, 初始的时候把他们成他们的父亲节点(即原树的结构)
  • 先把所有的修改都进行一遍, 每次修改的时候, 沿着并查集fb[]一个一个地向上跳, 把每一个跳到的节点的fw都赋成自己(然后记录这次修改有哪些白点发生了变化), 并黑点的并查集fb路径压缩
  • 倒着处理, 撤销修改, 每次撤销修改的时候就是把 那次修改被影响到的白点的并查集fw[x]的值设为他自己x
  • 查询的时候就是普通的并查集找祖先, 并且可以路径压缩

一些解释

  • 为什么要倒着做(正着做为什么不能路径压缩)?

1

如上图, 我要查询红色的点, 查询完毕, 路径压缩后会变成下面的情况

2

然后这时, 我在蓝色的地方加入一条黑边, 你就GG了…

而倒着处理, 黑色的边只会从下退至树根, 路径压缩过的边中肯定不会再有黑边出现了…

  • 为什么要一步步的沿着并查集的边跳?

直接求LCA是$\mathrm O(\lg n)$的…会被毒瘤出题人卡掉…但是沿着并查集的边向上跳并且一路路径压缩的话, 总复杂度是$\mathrm O(n)$的(每条边只会被经过/压缩一次)…这个点子其实来自当年的HardChoise

还是挺妙的 对吧?

沙茶的 代码

这道题其实有一个翻车点, 就是在用LCA的做法做的时候, 会出现LCA已经在当前黑点组成的并查集里了, 再跳的时候会超过LCA…然后就RE了…

所以我们要判断if (deep[dq] <= deep[lca]) return ;而不是if (dq == lca) return ;

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/**************************************************************
Problem: 3319
User: Cansult
Language: C++
Result: Accepted
Time:6404 ms
Memory:96492 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (1000000 + 5)
#define MAXL (20 + 5)
#define rint register int
#define cint const int
using namespace std;
struct edg
{
int from, to, next, bh;
}b[MAXN << 1];
int g[MAXN], fb[MAXN], fw[MAXN], fae[MAXN], n, q, d[MAXN], lgn, cntb, que[MAXN], deep[MAXN];
vector<int> xg[MAXN], ans;
inline void adn(cint from, cint to, cint bh)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].bh = bh;
g[from] = cntb;
}
int lg(cint x)
{
int re = 0;
while ((1 << re) <= x)
++re;
return re;
}
int chan(int x, int y, cint bh)
{
if (x == y)
return x;
if (deep[x] < deep[y])
swap(x, y);
if (fw[x] != x)
xg[bh].push_back(x);
fw[x] = x;
return (fb[x] = chan(fb[x], y, bh));
}
void dfs(int dq, int de)
{
deep[dq] = de;
for (int i = g[dq]; i; i = b[i].next)
if (b[i].to != d[dq])
fae[b[i].to] = b[i].bh, d[b[i].to] = dq, dfs(b[i].to, de + 1);
}
int find(cint x)
{ return (x == fw[x] ? x : (fw[x] = find(fw[x]))); }
inline int read()
{
rint re = 0;
register char x = 0;
while (x < '0' || x > '9')
x = getchar();
while (x <= '9' && x >= '0')
re = (re << 1) + (re << 3) + x - '0', x = getchar();
return re;
}
int main()
{
// scanf("%d%d", &n, &q);
n = read(), q = read();
lgn = lg(n);
for (rint i = 1, srx, sry; i < n; i++)
{
// scanf("%d%d", &srx, &sry);
srx = read(), sry = read();
adn(srx, sry, i);
adn(sry, srx, i);
}
d[1] = 1, fae[1] = 0;
dfs(1, 1);
// puts("ok");
for (rint i = 1; i <= n; i++)
fb[i] = fw[i] = d[i];
for (rint i = 1, sre, srx, sry; i <= q; i++)
{
// scanf("%d", &sre);
sre = read();
if (sre == 1)
// scanf("%d", &que[i]);
que[i] = read();
else
{
// scanf("%d%d", &srx, &sry);
srx = read(), sry = read();
chan(srx, sry, i);
}
// printf("%d\n", i);
}
// puts("ok");
for (rint i = q; i >= 1; i--)
{
for (rint j = 0; j < xg[i].size(); j++)
fw[xg[i][j]] = d[xg[i][j]];
if (que[i])
ans.push_back(fae[find(que[i])]);
}
for (rint i = ans.size() - 1; i >= 0; i--)
printf("%d\n", ans[i]);
return 0;
}

By 不用月考的 Cansult