AcWing 392. 会合

一个思路不难，但是实现起来有点毒瘤的题。

显然题目给出的是基环树（内向树）森林。

把每一个基环抠出来。

大力分类讨论：

若 \(a, b\) 不在一个联通量里，显然是 \(-1, -1\)
若 \(a, b\) 在同一颗子树内，他们聚合的点显然是最近公共祖先，因为如果再往上走，2的条件就不满足。
若 \(a, b\) 在同一联通量（同一颗基环树），两颗不同的子树内。显然他们必须走到树根，然后这时有两个选择：从 \(root[a]\) 走到 \(root[b]\)，或反之。我们求出两种走的步数，按照题意进行比较即可。

第一次遇到内向树，找基环的时候不知道该如何搞。（偷瞄了一眼别人的代码）发现他是自底向上进行递归，跟往常我们写的树的自顶向下相反，学习了一下。

相比来说自底向上貌似对内向树代码简化很多（只需一次dfs），原因在于：

若自顶向下遍历，我们找到一个环的时候，可能他的子树中的某些点已经遍历过了，也就是说 \(dep\)、\(root\) 等数组都算的不对，可能需要二次 \(dfs\)。
若自底向上遍历，只有当找到环之后，一个点才会确保更新。

#include <cstdio>

#include <iostream>

#include <vector>

using namespace std;

const int N = 500005, L = 19;

int n, Q, fa[N][L], f[N], root[N], dep[N], sum[N], ult[N];

bool vis[N], ins[N];

int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); }

void dfs(int u) {

	vis[u] = ins[u] = true;

	int v = fa[u][0];

	if (ins[v]) {

		// 此时从 v -> fa[v][0], ->..., -> u -> v... 构成一个环

		int cnt = 0, y = v;

		while (1) {

			root[y] = y, dep[y] = 0, ult[y] = u;

			sum[y] = ++cnt, ins[y] = false;

			if (y == u) break;

			y = fa[y][0];

		}

		return;

	}

	if (!vis[v]) dfs(v);

	if (!root[u]) root[u] = root[v], dep[u] = dep[v] + 1, ins[u] = false;

	for (int i = 1; i < L && fa[u][i - 1]; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];

}

int lca(int x, int y) {

    if (dep[x] < dep[y]) swap(x, y);

    for (int i = L - 1; ~i; i--)

        if (dep[x] - (1 << i) >= dep[y]) x = fa[x][i];

    if (x == y) return x;

    for (int i = L - 1; ~i; i--)

        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];

    return fa[x][0];

}

int main() {

	scanf("%d%d", &n, &Q);

	for (int i = 1; i <= n; i++) f[i] = i;

	for (int i = 1; i <= n; i++) scanf("%d", &fa[i][0]), f[find(i)] = find(fa[i][0]);

	for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i);

	while(Q--) {

		int a, b; scanf("%d%d", &a, &b);

		if (find(a) != find(b)) puts("-1 -1");

		else if(root[a] == root[b]) {

		    int p = lca(a, b);

		    printf("%d %d\n", dep[a] - dep[p], dep[b] - dep[p]);

		} else {

		    int x = dep[a], y = dep[b], cx, cy;

		    if (sum[root[a]] < sum[root[b]]) cx = sum[root[b]] - sum[root[a]], cy = sum[ult[root[a]]] - cx;

		    else cy = sum[root[a]] - sum[root[b]], cx = sum[ult[root[a]]] - cy;

		    if (max(x + cx, y) < max(x, y + cy) || (max(x + cx, y) == max(x, y + cy) && (min(x + cx, y) < min(x, y + cy) || (min(x + cx, y) == min(x, y + cy) && x + cx >= y))))

		        printf("%d %d\n", x + cx, y);

		    else printf("%d %d\n", x, y + cy);

		}

	}

	return 0;

}

巴特西

AcWing 392. 会合

最新文章

热门文章