有一颗 $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$ 的真正的最近公共祖先。

简单题。

题目给出的代码就是两个节点同时往上跳，问相遇那个点是真正 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