Recently I had to create large Test Cases for trees so I came up with an idea that involved the use of PBDS / Ordered Set.

So I created 2 pbds. One pbds for storing nodes I have included in the tree and the other for storing the remaining nodes. I will take 1 random value u from the first pbds and another random value v from the second pbds and then print u and v (i.e add edge between u and v). Then erase v from second pbds and insert it in first pbds cause now v is also included in the tree. I used pbds as it allows me to take any random value from it and also erasing it in log n time.

#define ll long long int

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
#define pbds tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>

void treeTCgenerator()
{
    ll numberOfNodes = 1e5;

    srand(time(0));

    cout << numberOfNodes << "\n";

    pbds includedInTree;
    pbds notIncludedInTree;

    ll root = 1;//almost centroid

    //uncomment the below line to create random root
    //root = ((ll) rand() * rand()) % n + 1;

    includedInTree.insert(root);

    for (ll i = 1; i <= numberOfNodes; i++)
    {
        if(i != root){
            notIncludedInTree.insert(i);
        }
    }
    
    for (ll i = 0; i < numberOfNodes - 1; i++)
    {
        ll r = rand();
        ll incSize = includedInTree.size();

        r %= incSize;

        auto itU = includedInTree.find_by_order(r);
        ll u = *itU;

        r = rand();
        
        ll notIncSize = notIncludedInTree.size();

        r %= notIncSize;

        auto itV = notIncludedInTree.find_by_order(r);
        ll v = *itV;

        notIncludedInTree.erase(itV);
        includedInTree.insert(v);

        cout << u << " " << v << "\n";
    }
}

Time Complexity: n * log n

The first value you insert in the first pbds will be close to the centroid of the tree.

Using srand(time(0)) is important otherwise it will create the same tree again and again. If you want to create a test case that involves multiple test cases then call srand(time(0)) function in your main function and remove it from treeTCgenerator function. Cause if we don't remove it then it will get called for each test case. And calling srand(time(0)) again and again also causes the problem of getting repeated random values from rand() function.

Here I have used cout for printing values. You can directly print these values in a file also.

If there are better methods for creating TC for trees please let me know.