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;
}