Hack 数据 WA 求调(
查看原帖
Hack 数据 WA 求调(
741244
Eason_cyx大愚若智楼主2025/7/31 14:56
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int f[N], mx[N], go[N][25], n, dep[N], pow2[25];
vector<int> e[N];
void dfs(int now) {
    for(int i = 0;i < e[now].size();i++)
        mx[e[now][i]] = max(mx[now], e[now][i]), 
        dep[e[now][i]] = dep[now] + 1, dfs(e[now][i]);
} int lca(int xx, int yy) {
    //假设 y 的深度大于 x 的深度
    int x = xx, y = yy;
    if(dep[y] < dep[x]) swap(x, y);
    for(int i = 17;i >= 0;i--)
        if((dep[y] - dep[x]) >= pow2[i])
            y = go[y][i];
    if(x == y) return x;
    for(int i = 17;i >= 0;i--)
        if(go[x][i] != go[y][i])
            x = go[x][i], y = go[y][i];
    return go[x][0];
} int main() {
    cin >> n; pow2[0] = 1;
    for(int i = 1;i <= 20;i++) pow2[i] = pow2[i-1] * 2;
    for(int i = 1;i < n;i++)
        cin >> f[i], go[i][0] = f[i], e[f[i]].push_back(i);
    for(int i = 1;i < n;i++)
        for(int j = 1;j <= 17;j++)
            go[i][j] = go[go[i][j-1]][j-1];
    mx[0] = dep[0] = 0; dfs(0);
    int q; cin >> q; while(q--) {
        int m; cin >> m;
        int x, y; cin >> x >> y;
        int l = lca(x, y);
        for(int i = 3, z;i <= m;i++)
            cin >> z, l = lca(l, z);
        cout << mx[l] << endl;
    }
    return 0;
}
2025/7/31 14:56
加载中...