lca.cpp

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
using ll = long long;
const int MOD = 998244353;
const int MAXN = 1e6 + 10;

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[a] >= tout[b]);
}
int timer = 0;

void dfs(int v, int pr = 0){
    was[v] = 1;
    tin[v] = ++timer;
    up[v][0] = pr;
    for (int i = 1; i <= l; i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for (int to : g[v]){
        if (!was[to]){
            dfs(to, v);
        }
    }

    tout[v] = ++timer;
}

int lca(int a, int b){
    if (upper(a, b)){
        return a;
    }
    if (upper(b, a)){
        return b;
    }
    for (int i = l; i >= 0; i--){
        if (!upper(up[a][i], b)){
            a = up[a][i];
        }
    }
    return up[a][0];
}

void solve() {

    cin >> n;
    int x = n;
    while (x){
        l++;
        x >>= 1;
    }
    tout[0] = INF;
    for (int i = 1; i < n; i++){
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }


}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr); std::cout.tie(nullptr);
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}