# 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:

• lca1 = LCA(x, y)
• lca2 = LCA(x, currentRoot)
• lca3 = LCA(y, currentRoot)
• lca4 = 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 }
```
Questions?