PWTC day4补题记录

F

题意: 求树链mex, $n,q\leq 100,000$.

树上莫队. 考虑一个棋子在树上从根开始dfs的过程, 棋子每移动一次都停下来记录一次时间, 注意返回父亲时也要停下. 这样, 每两个时刻之间就由一个边连接. 把 (节点, 时刻) 对按时刻排序, 每次询问$(u,v)$即为询问来到$u$的时刻$t_u$$v$的时刻$t_v$之间的序列的一个量: 这个序列中出现过两次的边都不计入, 只计入出现过一次的边, 求mex. 这样就恰好只计入了$u$$v$的链上的所有边. 然后是维护mex. 这个题每次修改都带上$\log$就是$O(n\sqrt{n}\log n)$会T, 所以要线性修改. 由于询问mex只有$q$次, 所以可以容忍$O(\sqrt{n})$的询问. 于是对边权分块, 即用$cnt[i]$记录$i$的出现次数的同时, 用$cnt\_bl[i]$记录$[i * bl, (i + 1) * bl - 1]$中数的个数. 找到第一个数的个数没有填满的块, 再遍历该块找到第一个缺席的数, 即为mex.

AC代码

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
116
117
118
119
120
121
122
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
typedef pair<int, int> pii;
vector<pii> G[maxn];
struct query {
int first, second, id;
};
struct edge {
int w, id;
};
vector<query> qs;
vector<pii> ans;
int n, q, len, t, tt, bl;
int el[maxn], er[maxn];
edge L[2 * maxn], R[2 * maxn];
bool vis[maxn];
int cnt[maxn], cnt_block[maxn];
void dfs(int u, int fa, int id, int ww) {
el[u] = ++t;
for (auto e : G[u]) {
int v = e.first, w = e.second;
if (v == fa) continue;
R[t] = edge{w, ++tt};
L[t + 1] = edge{w, tt};
dfs(v, u, tt, w);
}
R[t] = edge{ww, id};
er[u] = ++t;
L[t] = edge{ww, id};
}
void add(int a) {
cnt[a]++;
if (cnt[a] == 1) cnt_block[a / bl]++;
}
void del(int a) {
cnt[a]--;
if (cnt[a] == 0) cnt_block[a / bl]--;
}
// ql + n^2/l min, q - n^2/l^2=0, l = n / sqrt(q)
inline bool cmp(const query& a, const query& b) {
if (a.first / len != b.first / len) return a.first / len < b.first / len;
return a.second < b.second;
}
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
len = 2 * n / sqrt(q);
bl = sqrt(maxn);
int u, v, w;
for (int i = 1; i < n; i++) {
cin >> u >> v >> w;
w = min(w, n);
G[u].push_back(pii(v, w));
G[v].push_back(pii(u, w));
vis[i] = false;
}
dfs(1, 0, 0, 100005);
for (int i = 1; i <= q; i++) {
cin >> u >> v;
int a = el[u], b = el[v];
if (a > b) {int tmp = a; a = b; b = tmp;}
qs.push_back(query{a, b, i});
}
// 分块
sort(qs.begin(), qs.end(), cmp);
// 莫队
int l = 1, r = 1;
for (auto p : qs) {
int &ql = p.first, &qr = p.second;
while (l > ql) { // 先尽量延长
if (!vis[L[l].id]) {
add(L[l].w);
} else {
del(L[l].w);
}
vis[L[l].id] = !vis[L[l].id];
l--;
}
while (r < qr) { // 先尽量延长
if (!vis[R[r].id]) {
add(R[r].w);
} else {
del(R[r].w);
}
vis[R[r].id] = !vis[R[r].id];
r++;
}
while (l < ql) {
if (!vis[R[l].id]) {
add(R[l].w);
} else {
del(R[l].w);
}
vis[R[l].id] = !vis[R[l].id];
l++;
}
while (r > qr) {
if (!vis[L[r].id]) {
add(L[r].w);
} else {
del(L[r].w);
}
vis[L[r].id] = !vis[L[r].id];
r--;
}
int i, j;
for (i = 0; i <= 100000 / bl; i++) {
if (cnt_block[i] != bl) break;
}
for (j = i * bl; j < (i + 1) * bl; j++) {
if (cnt[j] == 0) break;
}
ans.push_back(pii(p.id, j));
}
sort(ans.begin(), ans.end());
for (auto p : ans) {
cout << p.second << '\n';
}
return 0;
}