AcWing P1172 祖孙询问 题解 DFS

发布时间:2024年01月17日

祖孙询问

传送门

题目描述

已知一棵 n n n 个节点的有根树。有 m m m 个询问。每个询问给出了一对节点的编号 x x x y y y,询问 x x x y y y 的祖孙关系。

输入格式

输入第一行包括一个整数 n n n 表示节点个数。
接下来n行每行一对整数对 a a a b b b 表示 a a a b b b 之间有连边。如果 b b b ? 1 ?1 ?1,那么 a a a 就是树的根。
n + 2 n+2 n+2 行是一个整数 m m m 表示询问个数。
接下来 m m m 行,每行两个正整数 x x x y y y

输出格式

对于每一个询问,输出 1 1 1:如果 x x x y y y 的祖先;输出 2 2 2:如果 y y y x x x 的祖先;否则输出 0 0 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 30 30% 的数据, n , m ≤ 1000 n,m\le 1000 n,m1000
对于 100 100 100% 的数据, n , m ≤ 40000 n,m\le 40000 n,m40000,每个节点的编号都不超过 40000 40000 40000

以上来自 A c W i n g 以上来自AcWing 以上来自AcWing

解题思路

显然这题是 L C A LCA LCA 的模版题,但是用 d f s dfs dfs 写更简单。

t i m e 1 , t i m e 2 time1,time2 time1,time2 两个数组分别记录节点被搜索到的时刻与被递归到的时刻。当 t i m e 1 x < t i m e 1 y time1_x<time1_y time1x?<time1y? t i m e 2 x > t i m e 2 y time2_x>time2_y time2x?>time2y? 时, x x x y y y 的祖先节点,输出 1 1 1;反之 t i m e 1 x > t i m e 1 y time1_x>time1_y time1x?>time1y? t i m e 2 x < t i m e 2 y time2_x<time2_y time2x?<time2y? 时, y y y x x x 的祖先节点,输出 2 2 2;若以上条件都不满足,则说明 x x x y y y 位于同一层,输出 0 0 0

然后就写完了,这不比 L C A LCA LCA 好理解。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 4e5 + 5;
int n, m, a, b;
int root, cnt, head[Maxn * 2], time1[Maxn], time2[Maxn], Time;
bool vis[Maxn];
struct project {
	int To, Next;
} e[Maxn * 2];
inline void addedge(int u, int v) {
	e[++cnt].Next = head[u];
	e[cnt].To = v;
	head[u] = cnt;
}
inline void dfs(int now) {
	time1[now] = ++Time;
	vis[now] = 1;
	for (int i = head[now]; i; i = e[i].Next) {
		if (!vis[e[i].To]) {
			dfs(e[i].To);
		}
	}
	time2[now] = ++Time;
}
inline void solve() {
	cin >> a >> b;
	if (time1[a] < time1[b] && time2[a] > time2[b]) {
		cout << 1 << endl;
	} else if (time1[a] > time1[b] && time2[a] < time2[b]) {
		cout << 2 << endl;
	} else {
		cout << 0 << endl;
	}
}
inline void work() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a >> b;
		if (b == -1) {
			root = a;
		} else {
			addedge(a, b);
			addedge(b, a);
		}
	}
	dfs(root);
	cin >> m;
	while (m--) {
		solve();
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}
文章来源:https://blog.csdn.net/BestMonkey/article/details/135647697
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。