E - Xenia and Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E - Xenia and Tree
Source            : Codeforces
Category          : Data Structure
Algorithm         : Square Root Decomposition on Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
static const int maxn = 1e5 + 6;  
static const int logn = 19;  
static const int maxb = 320;  
  
vector < vector <int> > graph;  
int depth[maxn];  
int father[maxn][logn];  
  
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;  
            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[maxn];  
  
void bfs(vector <int> &block_reds)  
{  
      queue <int> pq;  
      for (int x : block_reds)  
      {  
            pq.push(x);  
            dist[x] = 0;  
      }  
      while (pq.size())  
      {  
            int u = pq.front();  
            pq.pop();  
            for (int v : graph[u])  
            {  
                  if (dist[v] > dist[u] + 1)  
                  {  
                        dist[v] = dist[u] + 1;  
                        pq.push(v);  
                  }  
            }  
      }  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int n, m;  
      cin >> n >> m;  
      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);  
      }  
      vector < pair <int, int> > queries(m);  
      for (int i = 0; i < m; i++) cin >> queries[i].first >> queries[i].second;  
      depth[1] = 1;  
      dfs();  
      for (int i = 1; i <= n; i++) dist[i] = 1e9 + 9;  
      vector <int> block_reds;  
      block_reds.push_back(1);  
      bfs(block_reds);  
      for (int i = 0; i < m; i += maxb)  
      {  
            block_reds.clear();  
            for (int j = 0; j < maxb; j++)  
            {  
                  int k = i + j;  
                  if (k >= m) break;  
                  if (queries[k].first == 1)  
                  {  
                        block_reds.push_back(queries[k].second);  
                  }  
                  else  
                  {  
                        int v = queries[k].second;  
                        int min_dist = dist[v];  
                        for (int u : block_reds)  
                        {  
                              int lca = find_lca(u, v);  
                              int d = depth[u] + depth[v] - 2 * depth[lca];  
                              min_dist = min(min_dist, d);  
                        }  
                        cout << min_dist << endl;  
                  }  
            }  
            bfs(block_reds);  
      }  
}