[Codeforces] E. Xenia and Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Xenia and Tree
Source            : Codeforces
Category          : Graph Theory
Algorithm         : Centroid Decomposition
Verdict           : Accepted 

#include "bits/stdc++.h"
 
using namespace std;
 
#define inf                 123456
 
static const int maxn = 1e5 + 5;
static const int logn = 20;
 
vector <int> graph[maxn], centroid_tree[maxn];
 
int depth[maxn], father[maxn][logn], parent[maxn], subtree_size[maxn], nn;
bool is_centroid[maxn];
 
inline void dfs(int u = 1, 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;
        father[v][0] = u;
        depth[v] = depth[u] + 1;
        dfs(v, u);
    }
}
 
inline int findLCA(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];
}
 
inline int dis(int u, int v)
{
    int lca = findLCA(u, v);
    int d = depth[u] + depth[v] - 2 * depth[lca];
    return d;
}
 
inline void dfs2(int u, int p = -1)
{
    subtree_size[u] = 1;
    for (int v : graph[u])
    {
        if (v == p || is_centroid[v]) continue;
        dfs2(v, u);
        subtree_size[u] += subtree_size[v];
    }
}
 
inline int get_centroid(int u, int p = -1)
{
    for (int v : graph[u])
    {
        if (v == p || is_centroid[v]) continue;
        if (subtree_size[v] > (nn / 2)) return get_centroid(v, u);
    }
    return u;
}
 
int root_centroid_tree;
 
inline int decompose(int u)
{
    dfs2(u);
    nn = subtree_size[u];
    int p = get_centroid(u);
    if (!root_centroid_tree) root_centroid_tree = p;
    is_centroid[p] = 1;
    for (int v : graph[p])
    {
        if (is_centroid[v]) continue;
        int q = decompose(v);
        centroid_tree[p].push_back(q);
        centroid_tree[q].push_back(p);
    }
    return p;
}
 
int par[maxn];
 
inline void dfs3(int u, int p = -1)
{
    for (int v : centroid_tree[u])
    {
        if (v == p)
        {
            par[u] = v;
            continue;
        }
        dfs3(v, u);
    }
}
 
int ans[maxn];
 
inline void init()
{
    for (int i = 0; i < maxn; i++) ans[i] = inf;
}
 
inline void update_rec(int x, int u)
{
    if (x == -1) return;
    ans[x] = min(ans[x], dis(x, u));
    update_rec(par[x], u);
}
 
int query_rec(int x, int u)
{
    if (x == -1) return inf;
    int min_dis = ans[x] + dis(x, u);
    return min(min_dis, query_rec(par[x], u));
}
 
int main()
{
    //freopen("in.txt", "r", stdin);
 
    int tNode, tQuery;
    scanf("%d %d", &tNode, &tQuery);
    for (int node = 1; node < tNode; node++)
    {
        int u, v;
        scanf("%d %d", &u, &v);
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    depth[1] = 1;
    dfs();
    decompose(1);
    dfs3(root_centroid_tree);
    par[root_centroid_tree] = -1;
    init();
    update_rec(1, 1);   // initial node red
    while (tQuery--)
    {
        int t, v;
        scanf("%d %d", &t, &v);
        if (t == 1) update_rec(v, v);
        else printf("%d\n", query_rec(v, v));
    }
}