感觉已经不是第一次碰到并查集没有反应过来了！
已将并查集应用范围总结（当然肯定会很长）加入 to-do list。
A. Boss 树
http://222.180.160.110:61235/contest/6248/problem/1
以 \(1\) 为树根，初始被染色；定义一次操作为：对于父亲已染色的白点，同时选取它们中的至多 \(m\) 个，并染色。问最少操作次数。
一种策略是按 size 从大到小排序选取当前可选点。证明可能有点感性：
如果现在有两个可染色点，一个是大小为 \(n\) 的菊花，一个是长度为 \(n\) 的链；每次可以染色 \(2\) 个点，我们一定会留一个位置给链上的点。
我们把一次选择分配给一个点，无非是希望：
- 它能够供给这个位置尽可能多轮（也就是说它的高度比较高）。
- 它能够带来尽可能多的新点。
那么选 size 最大的就是一种好的手段。当然也可以得到按高度排序的结论，这其实也是对的。
#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("boss.in", "r", stdin);
std::freopen("boss.out", "w", stdout);
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int> > g(n + 1);
for (int i = 2, fa; i <= n; ++i) {
std::cin >> fa;
g[fa].push_back(i);
}
std::vector<int> siz(n + 1);
std::function<void(int)> DFS = [&](int x) {
siz[x] = 1;
for (auto i : g[x])
DFS(i), siz[x] += siz[i];
return;
};
DFS(1);
std::priority_queue<std::pair<int, int> > q, q1;
q.emplace(siz[1], 1);
std::vector<std::vector<int> > res(1);
for (int k = m; !q.empty(); ) {
int u = q.top().second;
res.back().push_back(u), q.pop();
for (auto i : g[u])
q1.emplace(siz[i], i);
if (!--k || q.empty()) {
res.emplace_back(), k = m;
for (; !q1.empty(); q1.pop())
q.push(q1.top());
}
}
if (res.back().empty())
res.pop_back();
std::cout << (int)res.size() << '\n';
for (auto &i : res) {
std::cout << (int)i.size();
for (auto j : i)
std::cout << ' ' << j;
std::cout << '\n';
}
return 0;
}B. 喝醉的兔子
http://222.180.160.110:61235/contest/6248/problem/2
给定 \(q\) 次询问，每次给定 \(f(0)\)，求最小的 \(t\)，使得 \(n | f(t)\)，其中 \(f(t)=d\cdot f(t-1) + \Delta_t\)，\(n,d,l,r\) 为常数，\(\Delta_t\) 为你自选的 \([l,r]\) 间的整数，每次询问独立。
\(q, n\le 10^7\)。
如果这是数论题，\(n\) 就不会和 \(q\) 同阶了，所以这可能是一道偏模拟的题目。
很容易想到建同余图（这里说的是从 \([0-r,0-l]\) 出发；这样每个点第一次被 BFS 到的时候就能确定答案了）。但如果直接把图建出来，大小就是 \(O(n^2)\) 级别的了。这个时候就有两条路径：
优化建图
每次连的点都是连续的一段，容易想到线段树优化建图。这样就能 \(O(n\log n)\) 解决问题了。但是题目要求线性。
在实现的时候一定会注意到我们会连到一些已经被访问过的点。这样的边是『无效』的——我们不能将访问过的点再次加入队列。能不能规避掉这些点呢？
每次被访问过的点一定是连续的、长度为 \(r - l + 1\) 的一段——有没有联想到什么？类似地，给 \(0\sim n-1\) 每隔 \(r-l+1\) 打一个标记——或者说 分一段，那么每次试图访问 \([l_0, r_0]\) 时：
- \([l_0,r_0]\) 为两个相邻段的前后缀。
- \([l_0,r_0]\) 恰好为一段。
这时我们就发现了，每次访问的是完整的前后缀，利用前后缀和优化建图，由于边数是 \(O(n)\) 的，且边权只有 \(0\) 和 \(1\)，就可以做到 \(O(n)\) 01BFS 解决问题。
但是似乎常数太大了，神威必可之光都跑不过去……
#include <bits/stdc++.h>
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
std::freopen("calculate.in", "r", stdin);
std::freopen("calculate.out", "w", stdout);
#else
std::freopen("ex_calculator3.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int T;
for (std::cin >> T; T--; ) {
int n, l, r, m, to;
long long d, len;
std::cin >> n >> d >> l >> r >> m, len = r - l + 1, to = (n - 1) / len + 1;
std::vector<std::vector<int> > t(n), lid(to), rid(to);
for (int i = 0; i < n; ++i)
t[i * d % n].push_back(i);
std::vector<std::vector<int> > g(3 * n);
for (int i = 0, id = n - 1; i < to; ++i) {
int at = ((i != to - 1 || !(n % len)) ? len : (n % len));
lid[i].resize(at), rid[i].resize(at);
for (int j = 0; j < at; ++j) {
lid[i][j] = ++id;
g[id].push_back(i * len + j);
if (j != 0)
g[id].push_back(id - 1);
}
for (int j = at - 1; ~j; --j) {
rid[i][j] = ++id;
g[id].push_back(i * len + j);
if (j != at - 1)
g[id].push_back(id - 1);
}
}
auto add = [&](int p, int l0, int r0) {
int p1 = l0 / len, p2 = r0 / len;
if (p1 == p2)
g[p].push_back(lid[p1].back());
else {
g[p].push_back(rid[p1][l0 % len]);
if ((p1 + 1) % to != p2) {
// fprintf(stderr, "p1 = %d, p2 = %d, to = %d, get %d(%d)\n", p1, p2, to, (p1 + 1) % to, (int)lid[(p1 + 1) % to].size());
g[p].push_back(lid[(p1 + 1) % to].back());
}
g[p].push_back(lid[p2][r0 % len]);
}
return;
};
for (int i = 0; i < n; ++i)
for (auto j : t[i]) {
// printf("%d -> %d[%d, %d]\n", i, j, (j + n - r) % n, (j + n - l) % n);
add(i, (j + n - r) % n, (j + n - l) % n);
}
std::deque<std::pair<int, int> > q;
std::vector<int> f(n + 1, -1), tag(3 * n + 1);
for (int i = l, p = (n - r) % n; i <= r; ++i, (++p) %= n)
f[p] = 0, q.emplace_back(p, 0), tag[p] = 2;
for (; !q.empty(); ) {
auto [u, d] = q.front();
q.pop_front();
if (u < n && f[u] == -1)
f[u] = d;
// printf("u = %d, d = %d\n", u, d);
for (auto i : g[u]) {
// printf(" i = %d\n", i);
if (i >= n && tag[i] <= 1)
q.emplace_front(i, d), tag[i] = 2;
if (i < n && !tag[i])
q.emplace_back(i, d + 1), tag[i] = 1;
}
}
for (int x; m--; )
std::cin >> x, std::cout << f[x] << '\n';
}
return 0;
}或者，发现每次任意标记前后缀，则一段内未访问的一定是中间的一整截。根据这一点可维护每一段内可访问元素，就能 \(O(n)\) BFS；
如果把图建出来了，还可以解决扩展问题：
假如 \(\Delta_i\) 在 \([l,r]\) 间的整数中等概率取值，则最优解出现的概率？
为什么 BFS 不能解决该问题呢？因为同层同代价的点对共同能访问到的点的贡献不会被 BFS 记入（注意到一个点只会被一个点访问到），所以只有建图出来才能解决问题。
这也侧面反映该图在忽略环后所对应的就是最优解，这其实是有点 BFS 扩展出来的意味在的。