ABC350G 题解

· · 题解

LCT 板子，然而我没不会 LCT，然而可以根号分治甚至跑得贼快。

既然已经保证了整个图是森林，我们就好办了，树上可简单得多。

我们先考虑只有操作二的情况：很明显，我们只需要找两个点所连接的点的交集，明显这个交集的模不大于一。这个过程是 O(d(u)) = O(n) 的。可以用一个 bitset 优化，那么就比上一个 \omega 的常数。

再看操作一。我们暴力改的话无非就是 bitset 设位，是 O(1) 的…… 但是

…… 明显这个做法是行不通的，bitset 空间 O(n^2)，爆掉。

考虑根号分治。对于度不大于 \sqrt N 的点，修改无视 O(1)，操作直接暴力 O(\sqrt N)，很优。

大于 \sqrt N 的点，建立 bitset（我们最多只会建立 \sqrt N 个 bitset） 是 O(\sqrt N) 的。查找是最差 O(\dfrac N {2\omega}) 的（因为两个点的度都要大于 \sqrt N，于是比上一个 2）。

看起来很差，但是 N 和 Q 的和是有限制的（设 T = 10^5），解一下得到一个大致最大 Q = \dfrac {T} 2 时候为 \dfrac {T^2} {8\omega} \approx 10^{7.29}，叉不掉。简单写了一个 generator，但是根本叉不掉，只叉到 100ms 左右。

#include <iostream>
using namespace std;
const int N = 5e4, Q = 5e4;

int main (void)
{
    ios::sync_with_stdio (false), cin.tie (0), cout.tie (0);
    cout << N << ' ' << N + Q << '\n';
    for (int i = 4; i <= N / 2 + 1; i++) cout << "1 2 " << i << '\n';
    for (int i = N / 2 + 2; i <= N; i++) cout << "1 3 " << i << '\n';
    cout << "1 1 2\n1 1 3\n";
    for (int i = 0; i < Q + 1; i++) cout << "2 2 3\n";
    return 0;
}

这题到这里就真正做完了。