AcWing P1172 祖孙询问 题解 DFS

祖孙询问

传送门

题目描述

已知一棵 $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\le 1000$。
对于 $100$% 的数据，$n,m\le 40000$，每个节点的编号都不超过 $40000$。

$以上来自AcWing$

解题思路

显然这题是 $LCA$ 的模版题，但是用 $dfs$ 写更简单。

用 $time1,time2$ 两个数组分别记录节点被搜索到的时刻与被递归到的时刻。当 $time{1}_x<time{1}_y$ 且 $time{2}_x>time{2}_y$ 时，$x$ 是 $y$ 的祖先节点，输出 $1$；反之 $time{1}_x>time{1}_y$ 且 $time{2}_x<time{2}_y$ 时，$y$ 为 $x$ 的祖先节点，输出 $2$；若以上条件都不满足，则说明 $x$ 与 $y$ 位于同一层，输出 $0$。

然后就写完了，这不比 $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;
}