Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của ladpro98

#include <vector>
#include <iostream>
#include <cstdio>
#include <cmath>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define PB push_back
#define VI vector<int>
const int N = 100005;
using namespace std;
VI a[N];
int p[N][20], d[N];
int n, m, lg;

void DFS(int u) {
    FOR(i, 0, SZ(a[u])) {
        int v = a[u][i];
        if (v != p[u][0]) {
            p[v][0] = u;
            d[v] = d[u] + 1;
            DFS(v);
        }
    }
}

int lca(int u, int v) {
    if (d[u] > d[v]) swap(u, v);
    REPD(i, lg, 0)
        if (d[v] - d[u] >= (1 << i)) v = p[v][i];
    if (u == v) return u;
    REPD(i, lg, 0) if (p[u][i] != p[v][i])
        {u = p[u][i]; v = p[v][i];}
    return p[u][0];
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    while (cin >> n) {
        if (n == 0) break;
        REP(i, 1, n) a[i].clear();
        int u, v, root = 1; char ch;
        FOR(i, 1, n) {
            cin >> u >> v;
            a[u].PB(v); a[v].PB(u);
        }
        DFS(1);
        lg = log2(n) + 1;
        FOR(j, 1, lg) REP(i, 1, n)
            p[i][j] = p[p[i][j - 1]][j - 1];
        cin >> m;
        while (m--) {
            cin >> ch;
            if (ch == '!') cin >> root;
            else {
                cin >> u >> v;
                int ur = lca(u, root);
                int vr = lca(v, root);
                int uv = lca(u, v);
                if (ur == vr) cout << uv << '\n'; else
                if (ur == uv) cout << vr << '\n'; else
                cout << ur << '\n';
            }
        }
    }
    return 0;
}

Code mẫu của hieult

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define Fit(i,c) for (__typeof__((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define inf 1000000005
#define all(a) (a).begin(), (a).end()
#define ms(a,x) memset(a, x, sizeof(a))
#define mod 1000000007
#define sz(a) ((int)(a).size())

template<class T> int getbit(T s, int i) { return (s >> i) & 1; }
template<class T> T onbit(T s, int i) { return s | (T(1) << i); }
template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); }
template<class T> int cntbit(T s) { return __builtin_popcountll(s);}
#define Rep(i,n) for(int i = 0; i < (n); ++i)
#define Repd(i,n) for(int i = (n)-1; i >= 0; --i)
#define For(i,a,b) for(int i = (a); i <= (b); ++i)
#define Ford(i,a,b) for(int i = (a); i >= (b); --i)

typedef unsigned long long ull;
typedef long long ll;
typedef double ld;
#define eps 1e-9
typedef pair<int, int> II;
template<class T> T gcd(T a, T b){ T r; while (b != 0) { r = a % b; a = b; b = r; } return a;}
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define PI 2 * acos(0)

#define maxn 200005

int n, q, deep[maxn], dad[maxn][20];
vector<int> V[maxn];

void go(int par, int u){
    deep[u] = deep[par] + 1;
    dad[u][0] = par;
    Rep(i, sz(V[u])){
        int v = V[u][i];
        if(v == par) continue;
        go(u, v);
    }
}

int lca(int u, int v){
    if(deep[u] > deep[v]) swap(u, v);
    for(int i = 18; i >= 0; i--){
        if(deep[v] - deep[u] >= (1 << i)) v = dad[v][i];
    }
    for(int i = 18; i >= 0; i--){
        if(dad[u][i] != dad[v][i]){
            u = dad[u][i];
            v = dad[v][i];
        }
    }
    if(u != v) u = dad[u][0];
    return u;
}

int main() {

//    freopen("dynamic.in", "r", stdin);
//    freopen("dynamic.out", "w", stdout);
 //   freopen("in.txt", "r", stdin);
//   freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    while(cin >> n){
        if(n == 0) break;
        For(i, 1, n) V[i].clear();
        int u, v;
        Rep(run, n - 1){
            cin >> u >> v;
            V[u].pb(v);
            V[v].pb(u);
        }
        ms(dad, 0); ms(deep, 0);
        go(0, 1);
        for(int i = 1; i <= 18; i++) for(int j = 1; j <= n; j++){
            dad[j][i] = dad[dad[j][i - 1]][i - 1];
        }

        cin >> q;
        int root = 1;
        char ch;
        Rep(iq, q){
            cin >> ch >> u;
            if(ch == '!'){
                root = u;
            } else{
                cin >> v;
                int tu = lca(root, u), tv = lca(root, v);
                int res = (deep[tu] >= deep[tv] ? tu : tv);
                int tuv = lca(u, v);
                res = (deep[res] >= deep[tuv] ? res : tuv);
                cout << res << "\n";
            }
        }
    }

    return 0;
}