Squirrel Structures

    1#include <bits/stdc++.h>
    2using namespace std;
    3#define endl '\n'
    4void dfs(int src, vector<vector<int>>& adj, vector<vector<pair<int, int>>>& trees, unordered_map<int, int>& mp, int prev){
    5    if(src == 0){
    6        for(int nxt : adj[src]){
    7            if(nxt == prev) continue;
    8            dfs(nxt, adj, trees, mp, src);
    9        }
    10    } else { 
    11        for(int nxt : adj[src]){
    12            if(nxt == prev) continue;
    13            int tree = mp[prev];
    14            trees[tree].push_back({prev, nxt});
    15            mp[nxt] = tree;
    16            dfs(nxt, adj, trees, mp, src);
    17        }
    18    }
    19}
    20int main(){
    21    ios::sync_with_stdio(0); cin.tie(0);
    22    int n; cin >> n;
    23    vector<vector<int>> adj(n);
    24    int k = 0;
    25    unordered_map<int, int> mp;
    26    mp[0] = 0;
    27    for(int i = 0; i < n - 1; i++){
    28        int u, v; cin >> u >> v; 
    29        if(u == 1 || v == 1){
    30            k++;
    31            u == 1 ? mp[v - 1] = v - 1 : mp[u - 1] = u - 1;
    32        }
    33        u--; v--;
    34        adj[u].push_back(v); adj[v].push_back(u);
    35    }
    36    vector<vector<pair<int, int>>> trees(2 * 1e5 + 1);
    37    dfs(0, adj, trees, mp, -1);
    38    cout << k + 1 << endl;
    39    vector<vector<int>> nodes(2 * 100000 + 1);
    40    for (int i = 0; i < n; i++) {
    41        int t = mp[i];
    42        nodes[t].push_back(i);
    43    }
    44    for(int i = 0; i < nodes.size(); i++){
    45        if(nodes[i].empty()) continue;
    46        cout << nodes[i].size() << endl;
    47        for(auto[u, v] : trees[i]){
    48            cout << u + 1 << " " << v + 1 << endl;
    49        }
    50    }
    51}