随机树生成器

auto rnd=mt19937_64(1127101799);
inline ll randin(ll l,ll r){return l+rnd()%(r-l+1);}
vec<int> gentree(int n,int rt=0,int minh=0,int maxh=0){if(!rt)rt=randin(1,n);if(!minh)minh=1;if(!maxh)maxh=n;vec<int> fa(n+1),dp(n+1),pl;vec<int> id(n);id[0]=rt;repl(i,1,n)id[i]=i+(i>=rt);shuffle(id.begin()+1,id.end(),rnd);dp[rt]=1,pl.pub(rt);int th=randin(minh,maxh);repl(i,1,th)fa[id[i]]=id[i-1],(dp[id[i]]=dp[fa[id[i]]]+1)<maxh&&(pl.pub(id[i]),1);repl(i,th,n)fa[id[i]]=pl[randin(0,pl.size()-1)],(dp[id[i]]=dp[fa[id[i]]]+1)<maxh&&(pl.pub(id[i]),1);return fa;
}

传入点数、根节点编号（传零则随机）、最小高度（传零则为 \(1\)）和最大高度（传零则为 \(n\)），返回每个点的父节点编号（根节点父亲为零）。点标号方式为 1-index。根节点深度为 \(1\)。

没有检验传入参数合法性，需自行确保传参正确。

算法就是先生成一根主干保证高度然后随机选父亲，因此质量什么的听天由命吧。