大概是这几天要出题造数据，于是写了个生成随机树的 generator。

然后现在只支持造菊花图、链和带有度数限制的一般树…主要是标号随机，然后让别人看数据的时候觉得是在随机造树）

难肯定是不难，但感觉经常懒得写 233。分享出来或许可以方便一下各位 :)

欢迎捉虫.jpg

#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 ; 
}