Centroid Decomposition.cpp

/*
    Author: M. A. Rafsan Mazumder
    Algorithm : Centroid Decomposition
    Problem : Codeforces 342E - Xenia and Tree
*/

/*
    Xenia the programmer has a tree consisting of n nodes. We will consider the tree nodes indexed from 1 to n.
    We will also consider the first node to be initially painted red, and the other nodes — to be painted blue.
    The distance between two tree nodes v and u is the number of edges in the shortest path between v and u.
    Xenia needs to learn how to quickly execute queries of two types:

    1. paint a specified blue node in red;
    2. calculate which red node is the closest to the given one and print the shortest distance to the closest red node.
*/

#include <bits/stdc++.h>

using namespace std;

#define MAX 100005
#define MAX_LOG 20
#define INF 1000000
set<int> S[MAX];
int centree[MAX], comp = 0, subSize[MAX];
int level[MAX], par[MAX][MAX_LOG], ans[MAX];

void dfs(int u, int pre, int depth)
{
    level[u] = depth;
    par[u][0] = pre;

    set<int> ::iterator it = S[u].begin();
    for(; it!=S[u].end(); it++){
        int v = *it;
        if(v == pre) continue;
        dfs(v, u, depth+1);
    }
}

void visit(int u, int par)
{
    ++comp;
    subSize[u] = 1;
    set<int> ::iterator it = S[u].begin();
    for(; it!= S[u].end(); it++){
        int v = *it;
        if(v == par) continue;
        visit(v, u);
        subSize[u] += subSize[v];
    }
}

int find_centroid(int u, int par)
{
    set<int> ::iterator it = S[u].begin();
    for(; it!=S[u].end(); it++){
        int v = *it;
        if(v == par) continue;
        if(subSize[v] > comp/2) return find_centroid(v, u);
    }
    return u;
}

void decompose(int u, int par)
{
    comp = 0;
    visit(u, u);
    int centroid = find_centroid(u, u);
    centree[centroid] = par;

    set<int> ::iterator it = S[centroid].begin();
    for(; it!=S[centroid].end(); it++){
        int v = *it;
        S[v].erase(centroid);
        decompose(v, centroid);
    }
    S[centroid].clear();
}

int LCA(int u, int v)
{
    if(level[u] < level[v]) swap(u, v);
    int diff = level[u]-level[v];
    for(int i=0; i<MAX_LOG; i++){
        if((1<<i) & diff) u = par[u][i];
    }
    if(u == v) return u;
    for(int i=MAX_LOG-1; i>=0; i--){
        if(par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    }
    return par[u][0];
}

int dist(int u, int v)
{
    int lca = LCA(u, v);
    return level[u]+level[v]-2*level[lca];
}

void update(int node)
{
    int x = node;
    while(x != -1){
        ans[x] = min(ans[x], dist(x, node));
        x = centree[x];
    }
}

int query(int node)
{
    int mins = INF;
    int x = node;
    while(x != -1){
        mins = min(mins, ans[x] + dist(x, node));
        x = centree[x];
    }
    return mins;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i=0; i<n-1; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        S[u].insert(v);
        S[v].insert(u);
    }
    memset(par, -1, sizeof par);
    dfs(1, -1, 0);
    for(int j=1; j<MAX_LOG; j++){
        for(int i=1; i<=n; i++) par[i][j] = par[par[i][j-1]][j-1];
    }
    decompose(1, -1);
    for(int i=0; i<MAX; i++) ans[i] = INF;
    update(1);
    for(int i=0; i<m; i++){
        int type, node;
        scanf("%d %d", &type, &node);
        if(type == 1) update(node);
        else printf("%d\n", query(node));
    }
}

/*
    5 4
    1 2
    2 3
    2 4
    4 5
    2 1
    2 5
    1 2
    2 5

    0
    3
    2
*/