FSELECT - LCA

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using tpii = tuple<int, int, int>;

const int maxN = 2e5 + 5;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

int n, k, l;
int root;
vector<int> graph[maxN], meet[maxN / 2];

int height[maxN];
int par[maxN][20];

void DFS(int u, int p) {
    par[u][0] = p;

    for (int v : graph[u]) {
        if (v == p) continue;

        height[v] = height[u] + 1;
        DFS(v, u);
    }
}

void build_LCA() {
    l = log2(n);

    DFS(root, 0);
    for (int i = 1; i <= l; i++)
        for (int u = 1; u <= n; u++)
            par[u][i] = par[par[u][i - 1]][i - 1];
}

int LCA(int u, int v) {
    if (height[u] < height[v]) swap(u, v);

    for (int i = l; i >= 0; i--)
        if (height[u] - (1 << i) >= height[v])
            u = par[u][i];

    if (u == v) return u;

    for (int i = l;  i >= 0; i--)
        if (par[u][i] && par[u][i] != par[v][i])
            u = par[u][i], v = par[v][i];
    return par[u][0];
}

int solve(vector<int> meet) {
    int x = meet[0], u;

    int maxD = 0;
    for (int i = 1; i < meet.size(); i++) {
        int y = meet[i];
        int dx = height[x] + height[y] - 2*height[LCA(x, y)];
        if (dx > maxD) maxD = dx, u = y;
    }

    int ans = 0;
    for (int i = 0; i < meet.size(); i++) {
        int v = meet[i];
        int du = height[u] + height[v] - 2*height[LCA(u, v)];
        ans = max(ans, du);
    }
    return ans;
}

int main() {
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#else
    freopen("FSELECT.inp", "r", stdin);
    freopen("FSELECT.out", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        int x; cin >> x >> par[i][0];
        graph[par[i][0]].push_back(i);
        meet[x].push_back(i);

        if (par[i][0] == 0) root = i;
    }

    l = log2(n);
    build_LCA();
    for (int i = 1; i <= k; i++)
        cout << solve(meet[i]) << '\n';

    return 0;
}