80分TLE求助
查看原帖
80分TLE求助
900910
lsrsrl楼主2024/10/9 15:12
#include <bits/stdc++.h>

using namespace std;
int f[500005][21], ed[500005], lst[500005], dep[500005], nxt[500005], cnt = 0;
void add(int x, int y) {
    ed[++cnt] = y;
    nxt[cnt] = lst[x];
    lst[x] = cnt;
}
void dfs(int x) {
    dep[x] = dep[f[x][0]] + 1;
    for (int i = 1; i <= 20; i++)
        f[x][i] = f[f[x][i - 1]][i - 1];
    int y = lst[x];
    while (y) {
        if (ed[y] != f[x][0]) {
            f[ed[y]][0] = x;
            dfs(ed[y]);
        }
        y = nxt[y];
    }
}
int lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    int k = dep[x] - dep[y];
    for (int i = 20; i >= 0; i--)
        if (k & (1 << i)) x = f[x][i];
    if (x == y) return x;
    for (int i = 20; i >= 0; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i],
            y = f[y][i];
    return f[y][0];
}
int main() {
    int n, m, x, y, z;
    cin >> n >> m;
    for (int i = 1; i < n; i++) {
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    dfs(1);
    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> z;
        int t1, t2, t3, ans;
        t1 = lca(x, y);
        t2 = lca(x, z);
        t3 = lca(y, z);
        if (t1 == t2)
            ans = t3;
        else if (t1 == t3)
            ans = t2;
        else if (t2 == t3)
            ans = t1;
        cout << ans << " " << dep[x] + dep[y] + dep[z] - dep[t1] - dep[t2] - dep[t3] << endl;
    }
}
2024/10/9 15:12
加载中...