题解：P11624 [迷宫寻路 Round 3] 挂掉的模板

· · 题解

[迷宫寻路 Round 3] 挂掉的模板

题目描述

有一颗 n 个节点的有根树。

定义 FakeLCA 函数代码如下：

int FakeLCA(int u, int v) {
    while (u != v) u = fa[u], v = fa[v];
    return u;
}

其中 fa[i] 表示节点 i 的父节点，特别的，根的父节点是根本身。

现在给定节点数 n 和每个节点的父节点，问有多少个有序数对 (u,v)，满足 1\le u,v\le n 且 FakeLCA(u, v) 的结果是 u 和 v 的真正的最近公共祖先。

Solution

简单题。

题目给出的代码就是两个节点同时往上跳，问相遇那个点是真正 LCA 的有多少个有序整数对。值得注意的一点是，根的父亲是根本身，并且有序整数对中 u,v 可以相等。

分情况讨论即可。

首先，我们找到这棵树的根 rt，那么 rt 与其他 n-1 个点可以互相构成 2n-2 个有序对。因为任何节点往上跳，肯定会到达根，而根只会原地不动。

然后是位于 rt 不同子树上的点 u,v。它们正常的 LCA 是 rt，我们记录 sz_u 表示 u 子树的大小，那么这样的有序整数对一共有

\sum_{u∈son(rt)}\sum_{v∈son(rt),v≠u}sz_u\times sz_v

但是如果给出的图是菊花图，那么我们的时间复杂度会退化为 \mathcal O(n^2)，考虑优化。对于上面那个式子，我们可以化简

\sum_{u∈son(rt)}\sum_{v∈son(rt),v≠u}sz_u\times sz_v =\sum_{u∈son(rt)}sz_u\sum_{v∈son(rt),v≠u)}sz_v =\sum_{u∈son(rt)}sz_u\times (n-sz_u-1)

这样我们就做到了 \mathcal O(n) 的时间复杂度。

接着，我们还需要考虑同一颗子树内的节点。由于节点是同时往上跳，所以 LCA 不是 rt 的节点 u,v 必须保证深度相同。所以我们需要对于 rt 的每一颗子树找出深度相等的节点 u,v，它们可以构成一组，统计答案即可。

最后，由于有序整数对中 u,v 可相等，所以我们的答案还需要加上 n。\ Ac Code