本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-04-21 23:44:22

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} \pprox 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;
}

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