构造随机树-JZTXT

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1000001; 		// N = 点数 + 1 

int n, p[N];

struct Edge
{
	int a, b;
}e[N];

int randi(int P)
{
	int res = (((rand() << 15ll) | rand()));
	return res % P + 1;
}

void CreateTree()
{
	n = randi(N - 1);
	for (int i = 1; i <= n; ++ i ) p[i] = i;
	random_shuffle(p + 1, p + n + 1);
	
	for (int i = 2; i <= n; ++ i )
		e[i - 1] = {p[randi(i - 1)], p[i]}; 
	
	random_shuffle(e + 1, e + n);
}

main()
{
	srand(time(0));
	
	CreateTree();
	
	cout << n << '\n';
	
	for (int i = 1; i < n; ++ i ) cout << e[i].a << ' ' << e[i].b << '\n';
	
	return 0;
}