90pts倍增LCA玄关求调有注释
查看原帖
90pts倍增LCA玄关求调有注释
592133
Mr_Potato楼主2024/10/31 14:13
#include <bits/stdc++.h>
using namespace std;

int n,m,q,fa[100010][20],dep[100010],lca,maxn;
int premax[100010];  // premax[i]表示顶点到i结点的链的最大值

struct Star {  // 链式前向星存图
    int head[100010],ntx[100010],vtx[100010],idx;
    Star() {  // 构造函数
        memset(head,-1,sizeof(head));
    }
    void add(int a,int b) {
        ntx[idx] = head[a];
        head[a] = idx;
        vtx[idx] = b;
        ++idx;
    }
} g;

void DFS(int u,int faNode,int maxn) {
    maxn = max(maxn,u), premax[u] = maxn;
    // 计算根到该点的链上编号最大值
    fa[u][0] = faNode, dep[u] = dep[faNode] + 1;
    for (int i=1; i<=(int)log2(dep[u]); ++i) {
        fa[u][i] = fa[fa[u][i-1]][i-1];
    }
    for (int i=g.head[u]; i!=-1; i=g.ntx[i]) {
        int v = g.vtx[i];
        if (v != faNode) {
            DFS(v,u,maxn);
        }
    }
}

int LCA(int u,int v) {  // LCA板子
    if (dep[u] < dep[v]) {
        swap(u,v);
    }
    while (dep[u] > dep[v]) {
        u = fa[u][(int)log2(dep[u]-dep[v])];
    }
    if (u == v) {
        return v;
    }
    for (int i=(int)log2(dep[u]); i>=0; --i) {
        if (fa[u][i] != fa[v][i]) {
            u = fa[u][i], v = fa[u][i];
        }
    }
    return fa[u][0];
}

int main() {
    scanf("%d",&n);
    for (int i=1; i<=n-1; ++i) {
        int f;
        scanf("%d",&f);
        if (f != i) {
            g.add(f,i);
        }
    }
    DFS(0,0,0);
    scanf("%d",&q);
    while (q--) {
        scanf("%d",&m);
        scanf("%d",&lca);
        for (int i=2; i<=m; ++i) {
            int a;
            scanf("%d",&a);
            lca = LCA(lca,a);  // lca是可重复贡献问题
        }
        printf("%d\n",premax[lca]);
    }
    return 0;
}
2024/10/31 14:13
加载中...