Tree Diameter #1

// Those who cannot remember the past are
// condemned to repeat it (use DP -_-)
// - George Santayana

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ll long long
#define ull unsigned long long
#define MOD 1000000007
#define PI acos(-1)
#define ceil(a, b) (((a) / (b)) + ((a) % (b) ? 1 : 0))
#define imin INT_MIN
#define imax INT_MAX
#define llmax LLONG_MAX
#define llmin LLONG_MIN
#define inf 2000000000
#define nl '\n'
#define ppcnt __builtin_popcount
#define ppcntll __builtin_popcountll
#define clz __builtin_clz
#define clzll __builtin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define modulo(a, b, mod) ((((a) % (mod)) + ((b) % (mod))) % (mod))
#define cnte(v, x) count(all(v), (x))
#define mine(v) min_element(all(v))
#define maxe(v) max_element(all(v))
#define updmin(a, b) a = min(a, b)
#define updmax(a, b) a = max(a, b)
#define findmod(x, m) x = ((x) % (m) + (m)) % m
#define getmod(x, m) ((x) % (m) + (m)) % (m)
#define debug(x) cout << "x: " << (x) << nl;
#define debug2(x, y) cout << "x: " << (x) << " y: " << y << nl;
#define ordered_set tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_map tree<int, int, less<>, rb_tree_tag, tree_order_statistics_node_update>

//vector<int> dx = {0, 0, 1, -1, 1, 1, -1, -1}, dy = {1, -1, 0, 0, 1, -1, 1, -1};
//vector<int> dx = {0, 0, 1, -1}, dy = {1, -1, 0, 0};

template<typename T = int> istream& operator>>(istream& in, vector<pair<int, int>>& v){
    for (auto& [x, y] : v) in >> x >> y;
    return in;
}

template<typename T = int> istream& operator>>(istream& in, vector<T>& v){
    for (T& i : v) in >> i;
    return in;
}

template<typename T = int> ostream& operator<<(ostream& out, const vector<T>& v){
    for (const T& x : v)
        out << x << ' ';
    return out;
}

template<typename T = pair<int, int>> ostream& operator << (ostream& out, const vector<pair<int, int>>& v){
    for(auto& [x, y] : v){
        out << x << ' ' << y << nl;
    }
    return out;
}

void Start_Crushing() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
int n, diameter, node, maxi;
vector<vector<int>> adj;

void bfs(int src, vector<int>& shortest){
    queue<int> q;
    q.push(src);
    shortest[src] = 0;

    while(not q.empty()){
        int curr = q.front();
        q.pop();

        for(auto& nxt : adj[curr]){
            if(shortest[nxt] > shortest[curr] + 1){
                shortest[nxt] = shortest[curr] + 1;
                q.push(nxt);
            }
        }
    }
}

void dfs_for_centers(int src, int par, vector<int>& centers, vector<int>& a, vector<int>& b){
    if(a[src] + b[src] == diameter and (a[src] == diameter / 2 or a[src] == ceil(diameter, 2)))
        centers.emplace_back(src);

    for(auto& nxt : adj[src]){
        if(nxt == par)
            continue;
        dfs_for_centers(nxt, src, centers, a, b);
    }
}

void dfs_for_diameter(int src, int par, int depth){
    if(depth > diameter){
        diameter = depth;
        node = src;
    }
    for(auto& nxt : adj[src]){
        if(par == nxt)
            continue;
        dfs_for_diameter(nxt, src, depth + 1);
    }
}

void dfs_for_worst(int src, int par, int depth, vector<int>& worst){
    if(depth == maxi){
        worst.emplace_back(src);
    }else if(depth > maxi){
        worst.clear();
        worst.emplace_back(src);
        maxi = depth;
    }

    for(auto& nxt : adj[src]){
        if(nxt == par)
            continue;
        dfs_for_worst(nxt, src, depth + 1, worst);
    }
}

void solve(){
    while(cin >> n){
        adj.assign(n + 5, vector<int>());

        vector<int> from_a(n + 5, inf), from_b(n + 5, inf);

        for(int i = 1; i <= n; i++){
            int k; cin >> k;
            while(k--){
                int v; cin >> v;
                adj[i].emplace_back(v);
            }
        }

        diameter = imin;

        int a, b;
        dfs_for_diameter(1, -1, 0);

        diameter = imin;
        a = node;
        dfs_for_diameter(node, -1, 0);
        b = node;

        bfs(a, from_a);
        bfs(b, from_b);

        vector<int> best;
        dfs_for_centers(1, -1, best, from_a, from_b);

        vector<int> worst;
        for(auto& center : best){
            vector<int> tmp;
            maxi = imin;
            dfs_for_worst(center, -1, 0, tmp);

            for(auto& end : tmp){
                worst.emplace_back(end);
            }
        }

        sort(all(best)), sort(all(worst));

        cout << "Best Roots  : ";
        for(int i = 0; i < best.size(); i++){
            if(i)
                cout << ' ';
            cout << best[i];
        }
        cout << nl << "Worst Roots : ";
        for(int i = 0; i < worst.size(); i++){
            if(i)
                cout << ' ';
            cout << worst[i];
        }
        cout << nl;
    }
}

void set_file(string& file_name){
    freopen((file_name + ".in").c_str(), "r", stdin);
    freopen((file_name + ".out").c_str(), "w", stdout);
}

int main(){
    Start_Crushing();

//    string file_name = "family";
//    set_file(file_name);

    int t = 1;
//    /*Multiple test cases?*/ cin >> t;
    while (t--) {
        solve();
        if(!t)
            break;
        cout << nl;
    }

//    for(int tc = 1; tc <= t; tc++){
//        cout << "Case #" << tc << ": ";
//        solve();
//        if(tc != t)
//            cout << nl;
//    }

    return 0;
}