| 36 | } |
| 37 | |
| 38 | pair<vi*, int> random_tree(int n) { |
| 39 | vi *adj = new vi[n]; |
| 40 | vi *children = new vi[n]; |
| 41 | union_find uf(n); |
| 42 | |
| 43 | for (int i = 0; uf.size(0) < n; i++) { |
| 44 | int a = rng() % n, |
| 45 | b = rng() % n; |
| 46 | |
| 47 | if (uf.find(a) != uf.find(b)) { |
| 48 | uf.unite(a, b); |
| 49 | adj[a].push_back(b); |
| 50 | adj[b].push_back(a); |
| 51 | } |
| 52 | } |
| 53 | |
| 54 | int root = rng() % n; |
| 55 | stack<int> S; |
| 56 | S.push(root); |
| 57 | bool *visited = new bool[n]; |
| 58 | memset(visited, 0, n); |
| 59 | visited[root] = true; |
| 60 | |
| 61 | while (!S.empty()) { |
| 62 | int cur = S.top(); |
| 63 | S.pop(); |
| 64 | for (int i = 0; i < size(adj[cur]); i++){ |
| 65 | int nxt = adj[cur][i]; |
| 66 | if (visited[nxt]) |
| 67 | continue; |
| 68 | children[cur].push_back(nxt); |
| 69 | S.push(nxt); |
| 70 | visited[nxt] = true; |
| 71 | } |
| 72 | } |
| 73 | |
| 74 | delete[] adj; |
| 75 | delete[] visited; |
| 76 | |
| 77 | return make_pair(children, root); |
| 78 | } |
| 79 | |
| 80 | struct lca_tree { |
| 81 | int *label; |