11375: 【原1375】祖孙询问
题目
题目描述
author: yuan 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1375
题目描述
已知一棵n个节点的有根树。有m个询问。每个询问给出了一对节点的编号x和y，询问x与y的祖孙关系。
输入说明
输入第一行包括一个整数n表示节点个数。
接下来n行每行一对整数对a和b表示a和b之间有连边。如果b是-1，那么a就是树的根。
第n+2行是一个整数m表示询问个数。
接下来m行，每行两个正整数x和y。
输出说明
对于每一个询问，输出1如果x是y的祖先，输出2如果y是x的祖先，否则输出0。
样例输入
10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19
样例输出
1
0
0
0
2
数据范围
对于30%的数据，n,m<=1000。
对于100%的数据，n,m<=40000，每个节点的编号都不超过40000。
q4x3's solution
/**
* 我真的很讨厌二进制相关的东西
* 所以讨厌倍增法
* 请允许我
* 转成rmq之后线段树
* 谢谢
* 一开始忘了双向建边要开两倍空间了，憨憨QAQ
**/
#include <iostream>
#include <cstdio>
const int MAXN = 8e4 + 233;
bool vis[MAXN];
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, tmpp, dfscnt, k, mini, maxi, root, cnt;
inline void read(int &x) {
x = 0;
char ch;
bool f = 0;
while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
if (ch == '-') f = 1;
else x = ch - '0';
while(ch = getchar(), ch >= '0' && ch <= '9') x = 10 * x + ch - '0';
x = f ? -x : x;
}
void link(int u, int v, int num) {
to[num] = v, next[num] = head[u], head[u] = num;
}
void dfs(int rt) {
vis[rt] = 1;
++ dfscnt;
dfscache[dfscnt] = rt;
if(first[rt] == 0) first[rt] = dfscnt;
for(int i = head[rt];i != 0;i = next[i]) {
if(vis[to[i]]) continue;
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];
if(tmp1 < tmp2) {
tree[rt] = tmp1;
treepos[rt] = treepos[rt << 1];
} else {
tree[rt] = tmp2;
treepos[rt] = 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() {
read(n);
for(int i = 1;i <= n;++ i) {
read(tmp); read(tmpp);
if(tmpp == -1) {
root = tmp;
continue;
}
link(tmp, tmpp, ++ cnt);
link(tmpp, tmp, ++ cnt);
}
depth[root] = 1;
dfs(root);
build(1, 1, dfscnt);
read(m);
for(int i = 0;i < m;++ i) {
read(tmp); read(tmpp);
mini = first[tmp];
maxi = first[tmpp];
if(mini < maxi) {
int tmp0 = query(1, 1, dfscnt, mini, maxi);
if(tmp0 == tmp) printf("1\n");
else if(tmp0 == tmpp) printf("2\n");
else printf("0\n");
} else {
int tmp0 = query(1, 1, dfscnt, maxi, mini);
if(tmp0 == tmp) printf("1\n");
else if(tmp0 == tmpp) printf("2\n");
else printf("0\n");
}
}
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) {}
};
//size!
node tree[50000];
node* oila[100000];
int st[100000][30];
int first[50000] = {0};
inline int lg(int n) { return n ? lg(n / 2) + 1 : -1; }
int dfs(node**& oilaptr, node* root, int height) {
if (first[root - tree])
return 0;
first[root - tree] = oilaptr - oila;
*oilaptr = root;
oilaptr++;
root->height = height;
son* sss = root->sons;
while (sss != nullptr) {
if (dfs(oilaptr, sss->value, height + 1)) {
*oilaptr = root;
oilaptr++;
}
sss = sss->next;
}
return 1;
}
int main() {
int n, m, g, r;
scanf("%d", &n);
node* root;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &g, &r);
if (r == -1 || g == -1) {
root = r == -1 ? tree + g : tree + r;
continue;
}
tree[g].sons = new son(tree[g].sons, tree + r);
tree[r].sons = new son(tree[r].sons, tree + g);
}
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];
}
}
scanf("%d", &m);
int pos, rr, ll, pent;
while (m--) {
scanf("%d%d", &ll, &rr);
ll = first[ll];
rr = first[rr];
bool swapf = false;
if (ll > rr) {
ll ^= rr;
rr ^= ll;
ll ^= rr;
swapf = true;
}
if (oila[st[ll][lg(rr - ll + 1)]]->height < oila[st[rr + 1 - (1 << lg(rr - ll + 1))][lg(rr - ll + 1)]]->height) {
if (first[oila[st[ll][lg(rr - ll + 1)]] - tree] == ll)
printf(swapf ? "2\n" : "1\n");
else if (first[oila[st[ll][lg(rr - ll + 1)]] - tree] == rr)
printf(swapf ? "1\n" : "2\n");
else
printf("0\n");
} else {
if (first[oila[st[rr + 1 - (1 << lg(rr - ll + 1))][lg(rr - ll + 1)]] - tree] == ll)
printf(swapf ? "2\n" : "1\n");
else if (first[oila[st[rr + 1 - (1 << lg(rr - ll + 1))][lg(rr - ll + 1)]] - tree] == rr)
printf(swapf ? "1\n" : "2\n");
else
printf("0\n");
}
}
return 0;
}
yyong119's solution
#include <cstdio>
#include <cstring>
#include <vector>
#define MAX_N 40005
using namespace std;
struct Node {
int x, y;
Node(int p = 0, int q = 0): x(p), y(q) {}
} query_seq[MAX_N];
int N, Q, root;
vector<int> link[MAX_N], query[MAX_N];
int ans[MAX_N], father[MAX_N];
bool vis[MAX_N], par[MAX_N];
inline int read() {
char ch = getchar(); int flag = 1, res = 0;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') flag = -1, ch = getchar();
while (ch >= '0' && ch <= '9')
res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return res * flag;
}
int Find(int x) {
if (father[x] != x)
father[x] = Find(father[x]);
return father[x];
}
void Union(int x, int y) {
int p = Find(x), q = Find(y);
father[p] = q;
}
void tarjan(int x) {
par[x] = true;
for (register int i = 0; i < link[x].size(); ++i) {
int next = link[x][i];
// not the parent node
if (!par[next]) {
tarjan(next);
Union(next, x);
}
}
vis[x] = true;
// solve the queries
for (register int i = 0; i < query[x].size(); ++i) {
int query_id = query[x][i], node_1 = query_seq[query_id].x, node_2 = query_seq[query_id].y;
if (vis[node_1] && vis[node_2]) {
int LCA = Find(x == node_1 ? node_2 : node_1);
if (LCA == node_1) ans[query_id] = 1;
else if (LCA == node_2) ans[query_id] = 2;
}
}
}
int main() {
// init tree
N = read();
for (register int i = 1; i <= MAX_N; ++i) father[i] = i;
for (register int i = 0; i < N; ++i) {
int x = read(), y = read();
if (x != -1 && y != -1) {
link[x].push_back(y);
link[y].push_back(x);
}
else if (x == -1) root = y;
else root = x;
}
// input queries
Q = read();
for (register int i = 0; i < Q; ++i) {
int x = read(), y = read();
query_seq[i].x = x;
query_seq[i].y = y;
// record the query_id related to the two node
query[x].push_back(i);
query[y].push_back(i);
}
// find LCA of each query
tarjan(root);
// output the answers
for (register int i = 0; i < Q; ++i)
printf("%d\n", ans[i]);
return 0;
}