[CS Academy] Root Change

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Root Change
Source            : CS Academy 
Category          : Graph Theory, Tree
Algorithm         : Re-Rooting Technique
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll           long long int   
#define endl         '\n'  
  
static const int maxn = 2e5 + 5;  
static const int logn = 19;  
  
vector < vector <int> > graph;  
int depth[maxn];  
int father[maxn][logn];  
  
void dfs(int u, int p = -1) {  
    for (int i = 1; i < logn; i++) {  
        father[u][i] = father[ father[u][i - 1] ][i - 1];  
    }  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        depth[v] = depth[u] + 1;  
        father[v][0] = u;  
        dfs(v, u);  
    }  
}  
  
int find_lca(int u, int v) {  
    if (depth[u] < depth[v]) {  
        swap(u, v);  
    }  
    for (int i = logn - 1; i >= 0; i--) {  
        if (depth[ father[u][i] ] >= depth[v]) {  
            u = father[u][i];  
        }  
    }  
    if (u == v) {  
        return u;  
    }  
    for (int i = logn - 1; i >= 0; i--) {  
        if (father[u][i] != father[v][i]) {  
            u = father[u][i];  
            v = father[v][i];  
        }  
    }  
    return father[u][0];  
}  
  
int dist(int u, int v) {  
    int lca = find_lca(u, v);  
    return depth[u] + depth[v] - 2 * depth[lca];  
}  
  
#define pii           pair <int, int>  
#define mk            make_pair  
#define ff            first  
#define ss            second  
  
pii dp[maxn];  
  
void solve(int u, int p = -1) {  
    dp[u] = mk(0, u);  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        solve(v, u);  
        if (1 + dp[v].ff > dp[u].ff) {  
            dp[u].ff = 1 + dp[v].ff;  
            dp[u].ss = dp[v].ss;  
        }  
    }  
    int cnt = 0;  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        if (1 + dp[v].ff == dp[u].ff) {  
            cnt++;  
        }  
    }  
    if (cnt > 1) {  
        dp[u].ss = u;  
    }  
}  
  
int n;  
int ans[maxn];  
pii dp2[maxn];  
  
void solution(int u, int p = 0) {  
    ans[u] = n - 1 - dist(u, dp[u].ss);  
    set <pii> st;  
    int maxi = 0;  
    if (p) {  
        maxi = dp[p].ff;  
        st.insert(dp[p]);  
    }  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        if (dp[v].ff > maxi) {  
            maxi = dp[v].ff;  
        }   
        st.insert(dp[v]);  
    }  
    for (int v : graph[u]) {  
        if (v == p) continue;  
        pii tempu = dp[u];  
        pii tempv = dp[v];  
        st.erase(dp[v]);  
        if (st.size() == 0) {  
            dp[u].ff = 0;  
            dp[u].ss = u;  
        } else {  
            pii beg = *st.rbegin();  
            dp[u].ff = 1 + beg.ff;  
            dp[u].ss = beg.ss;  
            st.erase(beg);  
            if (st.size()) {  
                pii chk = *st.rbegin();  
                if (chk.ff == beg.ff) {  
                    dp[u].ss = u;  
                }  
            }  
            st.insert(beg);  
        }  
        if (1 + dp[u].ff > dp[v].ff) {  
            dp[v].ff = 1 + dp[u].ff;  
            dp[v].ss = dp[u].ss;  
        } else if (1 + dp[u].ff == dp[v].ff) {  
            dp[v].ss = v;  
        }  
        st.insert(tempv);  
        solution(v, u);  
        dp[u] = tempu;  
        dp[v] = tempv;  
    }  
}  
  
signed main()  
{  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
      
    cin >> n;  
    graph.resize(n + 1);  
    for (int e = 1; e < n; e++) {  
        int u, v;  
        cin >> u >> v;  
        graph[u].push_back(v);  
        graph[v].push_back(u);  
    }  
    int root = 1;  
    for (int i = 1; i <= n; i++) {  
        if (graph[i].size() == 1) {  
            root = i;  
            break;  
        }   
    }  
    depth[root] = 1;  
    dfs(root);  
    solve(root);  
    solution(root);  
    for (int i = 1; i <= n; i++) cout << ans[i] << endl;  
}