我被hack了,救救我
查看原帖
我被hack了,救救我
1125575
lordrigs楼主2025/1/16 16:34
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
int n, q, m, u, v, d[100005], fa[100005], f[20][100005], ans;
vector <int> a[100005];
void dfs(int now, int dep, int _fa)
{
    d[now] = dep;
    for (auto i: a[now])
        if (i != _fa)
            dfs(i, dep + 1, now);
}
int lca(int x, int y)
{
    if (d[x] < d[y]) swap(x, y);
    for (int i = 17; i >= 0; i--)
        if (d[f[i][x]] >= d[y])
            x = f[i][x];
    if (x == y) return x;
    for (int i = 17; i >= 0; i--)
        if (f[i][x] != f[i][y])
            x = f[i][x], y = f[i][y];
    return fa[x];
}
int main()
{
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; i++)
    {
        cin >> fa[i];
        a[fa[i]].push_back(i);
        a[i].push_back(fa[i]);
    }
    dfs(0, 1, -1);
    for (int i = 0; i < n; i++)
    {
        f[1][i] = fa[i];
    }
    for (int i = 2; i <= 17; i++)
        for (int j = 0; j < n; j++)
            if (fa[j] != -1 && fa[f[i - 1][j]] != -1)
                f[i][j] = f[i - 1][f[i - 1][j]];
    cin >> q;
    while (q--)
    {
        cin >> m >> ans;
        for (int i = 2; i <= m; i++)
        {
            cin >> u;
            ans = lca(ans, u);
        }
        cout << ans << endl;
    }
    return 0;
}
2025/1/16 16:34
加载中...