Skip to content

14308: 【原4308】询问LCA

题目

题目描述

author: DS-TA Group2020 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4308

Description

助教有一棵有根树,现在他来考考你关于lca的知识。

助教共有m次询问,每次询问给出k个点,他想问问你这k个节点的最近公共祖先(lca)的节点编号(1 <= k <= n)。

数据范围是:$\Sigma k\leq 1e5$, $n \leq 1e5$

Input Format

第一行两个数n,m,表示节点数和询问次数 接下来n-1行,第i行有一个数字$a_i$,保证 $a_i<i$,是i号节点的父节点 接下来m行,首先一个数k,表示这个询问的节点数。然后输入k个点作为询问节点。

Output Format

对于每个询问输出一行,表示这些节点的lca编号。

Sample Input

10 5
1
1
3
2
1
4
3
2
4
3 4 2 3 
3 5 10 6 
3 1 4 5 
3 7 8 4 
3 6 9 10

Sample Output

1
1
1
3
1

q4x3's solution

/**
 * 我真的很讨厌二进制相关的东西
 * 所以讨厌倍增法
 * 请允许我
 * 转成rmq之后线段树
 * 谢谢
 **/
#include <iostream>
#include <cstdio>
const int MAXN = 1e5 + 233;
int to[MAXN], next[MAXN], head[MAXN], depth[MAXN], first[MAXN], dfscache[10 * MAXN];
int tree[40 * MAXN], treepos[40 * MAXN];
int n, m, tmp, dfscnt, k, mini, maxi;

void link(int u, int v, int num) {
    to[num] = v, next[num] = head[u], head[u] = num;
}

void dfs(int rt) {
    ++ dfscnt;
    dfscache[dfscnt] = rt;
    if(first[rt] == 0) first[rt] = dfscnt;
    for(int i = head[rt];i != 0;i = next[i]) {
        depth[to[i]] = depth[rt] + 1;
        dfs(to[i]);
        ++ dfscnt;
        dfscache[dfscnt] = rt;
    }
}

void build(int rt, int l, int r) {
    if(l == r) {
        tree[rt] = depth[dfscache[l]];
        treepos[rt] = dfscache[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    int tmp1 = tree[rt << 1], tmp2 = tree[rt << 1 | 1];
    tree[rt] = tmp1 < tmp2 ? tmp1 : tmp2;
    treepos[rt] = tmp1 < tmp2 ? treepos[rt << 1] : treepos[rt << 1 | 1];
}

int query(int rt, int l, int r, int s, int t) {
    if(s <= l && r <= t) {
        return treepos[rt];
    }
    int mid = (l + r) >> 1;
    if(t <= mid) return query(rt << 1, l, mid, s, t);
    else if(s > mid) return query(rt << 1 | 1, mid + 1, r, s, t);
    else {
        int tmp1 = query(rt << 1, l, mid, s, t), tmp2 = query(rt << 1 | 1, mid + 1, r, s, t);
        return (depth[tmp1] < depth[tmp2]) ? tmp1 : tmp2;
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1;i < n;++ i) {
        scanf("%d", &tmp);
        link(tmp, i + 1, i);
    }
    depth[1] = 1;
    dfs(1);
    build(1, 1, dfscnt);
    for(int i = 0;i < m;++ i) {
        scanf("%d", &k);
        mini = 1e5 + 233;
        maxi = -1;
        for(int i = 0;i < k;++ i) {
            scanf("%d", &tmp);
            mini = (first[tmp] < mini) ? first[tmp] : mini;
            maxi = (first[tmp] > maxi) ? first[tmp] : maxi;
        }
        printf("%d\n", query(1, 1, dfscnt, mini, maxi));
    }
    return 0;
}

victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;
struct node;
struct son {
    son* next;
    node* value;
    son(son* next = nullptr, node* value = nullptr) : next(next), value(value){};
};
struct node {
    int height;
    son* sons;
    node() : height(0),
             sons(nullptr) {}
};
node tree[100003];
node* oila[200003];
int st[200005][20];
int first[100003] = {0};
inline int lg(int n) { return n ? lg(n / 2) + 1 : -1; }
int dfs(node**& oilaptr, node* root, int height) {
    *oilaptr = root;
    if (!first[root - tree]) {
        first[root - tree] = oilaptr - oila;
    }
    oilaptr++;
    root->height = height;
    son* sss     = root->sons;
    while (sss != nullptr) {
        dfs(oilaptr, sss->value, height + 1);
        *oilaptr = root;
        oilaptr++;
        sss = sss->next;
    }
    return 0;
}

int main() {
    int n, m, g;
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &g);
        tree[g].sons = new son(tree[g].sons, tree + i);
    }
    node* root     = tree + 1;
    node** oilaptr = oila + 1;
    //obey to 1-base
    dfs(oilaptr, root, 1);
    for (int i = 1; i <= oilaptr - oila - 1; i++) {
        st[i][0] = i;
    }
    for (int j = 1; j <= lg(oilaptr - oila - 1); j++) {
        for (int i = 1; i + (1 << j) <= oilaptr - oila; i++) {
            st[i][j] = oila[st[i][j - 1]]->height < oila[st[i + (1 << (j - 1))][j - 1]]->height ? st[i][j - 1] : st[i + (1 << (j - 1))][j - 1];
        }
    }
    int pos, rr, ll, pent;
    while (m--) {
        scanf("%d%d", &pos, &ll);
        ll = first[ll];
        rr = ll;
        pos--;
        while (pos--) {
            scanf("%d", &pent);
            if (first[pent] < ll) {
                ll = first[pent];
            } else if (first[pent] > rr) {
                rr = first[pent];
            }
        }
        if (oila[st[ll][lg(rr - ll + 1)]]->height < oila[st[rr + 1 - (1 << lg(rr - ll + 1))][lg(rr - ll + 1)]]->height) {
            printf("%ld\n", oila[st[ll][lg(rr - ll + 1)]] - tree);
        } else {
            printf("%ld\n", oila[st[rr + 1 - (1 << lg(rr - ll + 1))][lg(rr - ll + 1)]] - tree);
        }
    }
    return 0;
}