# 笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”

### 【水】科学造树

posted on 2022-09-16 19:08:08 | under 日常工具 |


#include <bits/stdc++.h>

typedef long long LL ;

const int N = 2000100 ;
const LL Mx = (((1LL << 62) - 1) << 1) + 1 ;

using namespace std ;

LL get_LL(LL l, LL r){
__int128 x = Mx, t = 1 ;
while (t <= x)
t *= (rand() + 1) ;
t %= (r - l) ; t += l ;
return (long long)t ;
}
int t[N] ;
vector < pair<int, int> > tr ;
vector < pair<int, int> > get_Tree(int n, int type){
// type = 0, chain; type = 1, flower ; type = 2, normal ;
srand(time(NULL)) ;
vector < pair<int, int> > ret ;
if (type == 0){
for (int i = 1 ; i <= n ; ++ i) t[i] = i ;
random_shuffle(t + 1, t + n + 1) ;
for (int i = 1 ; i < n ; ++ i)
ret.push_back(make_pair(t[i], t[i + 1])) ;
random_shuffle(ret.begin(), ret.end()) ;
return ret ;
}
if (type == 1){
for (int i = 1 ; i <= n ; ++ i) t[i] = i ;
random_shuffle(t + 1, t + n + 1) ;
for (int i = 2 ; i <= n ; ++ i){
if (rand() & 1)
ret.push_back(make_pair(t[1], t[i])) ;
else ret.push_back(make_pair(t[i], t[1])) ;
}
random_shuffle(ret.begin(), ret.end()) ;
return ret ;
}
if (type == 2){
const int D = 4 ; //度数因子，树上所有点度数的最大值
for (int i = 1 ; i <= n ; ++ i) t[i] = i ;
random_shuffle(t + 1, t + n + 1) ; int p = 1 ;
queue <int> q ; q.push(t[1]) ;
while (!q.empty()){
int x = q.front() ; q.pop() ;
int d = rand() % D + 1 ;
while (p < n && d){
d -- ; p ++ ;
if (rand() & 1)
ret.push_back(make_pair(x, t[p])) ;
else ret.push_back(make_pair(t[p], x)) ;
q.push(t[p]) ;
}
}
random_shuffle(ret.begin(), ret.end()) ;
return ret ;
}
}
int n, m, q ;

int main(){
n = 15 ;
tr = get_Tree(n, 0) ;
cout << n << endl ;
for (auto x : tr)
cout << x.first << " " << x.second << '\n' ;
return 0 ;
}