Solution of Bosses

Bosses can be summarised as follows:

Given a root-adjustable tree, find the Lowest Common Ancestor between pairs of given nodes.

At a closer look, we notice that any LCA can be obtained solely by using the original tree. Regardless of current root, only 4 LCAs are needed:

• lca₁ = LCA(x, y)
• lca₂ = LCA(x, currentRoot)
• lca₃ = LCA(y, currentRoot)
• lca₄ = root

For each query, the solution is the lca that grants the minimum value for the expression:

dist(lcai, x) + dist(lcai, y), 1 ≤ i ≤ 4

C++ solution Cosmin Rusu

    1 #include <vector>
    2 #include <iostream>
    3 
    4 using namespace std;
    5 
    6 const int maxn = 100005;
    7 const int maxlg = 20;
    8 
    9 vector <int> g[maxn];
   10 int n, m, root = 1, rmq[maxlg][maxn << 1], euler[maxn << 1], level[maxn << 1], k, first[maxn], lg[maxn << 1];
   11 
   12 inline void dfs(int node, int father, int actlevel) {
   13     euler[++ k] = node;
   14     level[ k ] = actlevel;
   15     first[node] = k;
   16     for(vector <int> :: iterator it = g[node].begin() ; it != g[node].end() ; ++ it) {
   17         if(*it == father)
   18             continue;
   19         dfs(*it, node, actlevel + 1);
   20         euler[++ k] = node;
   21         level[ k ] = actlevel;
   22     }
   23 }
   24 
   25 inline void preprocess() {
   26     for(int i = 2 ; i <= k ; ++ i)
   27         lg[i] = lg[i >> 1] + 1;
   28     for(int i = 1 ; i <= k ; ++ i)
   29         rmq[0][i] = i;
   30     for(int l = 1 ; (1 << l) <= k ; ++ l) {
   31         int aux = (1 << (l - 1));
   32         for(int i = 1 ; i + (1 << l) - 1 <= k ; ++ i) {
   33             rmq[l][i] = rmq[l - 1][i];
   34             if(level[rmq[l][i]] > level[rmq[l - 1][i + aux]])
   35                 rmq[l][i] = rmq[l - 1][i + aux];
   36         }
   37     }
   38 }
   39 
   40 inline int LCA(int x, int y) {
   41     x = first[x];
   42     y = first[y];
   43     if(x > y)
   44         swap(x, y);
   45     int logaritm = lg[y - x + 1];
   46     int ret = rmq[logaritm][x];
   47     if(level[ret] > level[rmq[logaritm][y - (1 << logaritm) + 1]])
   48         ret = rmq[logaritm][y - (1 << logaritm) + 1];
   49     return euler[ret];
   50 }
   51 
   52 inline int dist(int x, int y) {
   53     int lca = LCA(x, y);
   54     return level[first[x]] + level[first[y]] - 2 * level[first[lca]];
   55 }
   56 
   57 inline int check(int x, int y, int lca) {
   58     return dist(x, lca) + dist(y, lca) + 2 * dist(lca, root);
   59 }
   60 
   61 inline int query(int x, int y) {
   62     int lca = LCA(x, y);
   63     int auxlca = LCA(x, root);
   64     if(check(x, y, lca) > check(x, y, auxlca))
   65         lca = auxlca;
   66     auxlca = LCA(y, root);
   67     if(check(x, y, lca) > check(x, y, auxlca))
   68         lca = auxlca;
   69     auxlca = root;
   70     if(check(x, y, lca) > check(x, y, auxlca))
   71         lca = auxlca;
   72     return lca;
   73 }
   74 
   75 int main() {
   76     cin >> n >> m;
   77     for(int i = 1 ; i < n ; ++ i) {
   78         int x, y;
   79         cin >> x >> y;
   80         g[x].push_back(y);
   81         g[y].push_back(x);
   82     }
   83     dfs(1, 0, 1);
   84     preprocess();
   85     for(int i = 1 ; i <= m ; ++ i) {
   86         int type, x, y;
   87         cin >> type;
   88         if(type == 1) {
   89             cin >> x;
   90             root = x;
   91         }
   92         else {
   93             cin >> x >> y;
   94             int lca = query(x, y);
   95             if(lca == x || lca == y)
   96                 cout << "-1\n";
   97             else
   98                 cout << lca << '\n';
   99         }
  100     }
  101 }