std 暂时不放了，毕竟是认认真真出的题（其实就算我不放，去提交记录也能看到）
lca 数组不用开的太大，会跑的比较慢的——来自某 std 快 800ms 的提醒（lca 数组调小后就到了 300ms
update on 2022.5.5
明明是没有人做的题居然被想出了树形dp写法，因为造数据实在太麻烦（随机数生成多少有点耗时），如果有个志愿者帮忙改进下 random 减小下时间复杂度的话，扩大数据范围倒是可以考虑。
结果最后硬是花好长时间等着这玩意跑完
random
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
int fa[100010];
int deg[100010];
int Find(int x)
{
return (fa[x] == x) ? x : Find(fa[x]);
}
int random()
{
return (long long)rand() * rand();
}
int main()
{
freopen(".\\data\\hydrogen10.in", "w", stdout);
srand(time(0));
int n = 5000;
printf("%d %d\n", n, n - 1);
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 1; i < n; i++) {
int x = random() % n + 1;
int y = random() % n + 1;
int px = Find(x), py = Find(y);
while (px == py || deg[x] >= 4 || deg[y] >= 4) {
x = random() % n + 1;
y = random() % n + 1;
px = Find(x), py = Find(y);
}
deg[x]++, deg[y]++;
fa[py] = px;
printf("%d %d\n", x, y);
}
return 0;
}
越往后生成一组合法数据的概率就会越低，所以复杂度会爆炸式增长（是个看脸的东西）。