CF755C PolandBall and Forest - Solution

strcmp · 2025-10-29 14:14:43 · 题解

现在有一个未知的森林，给 n 个数的序列，p_i 代表离 i 最远的点中编号最小的一个，根据这个信息还原出森林中有多少棵树。

离一个结点最远的点 x 一定是直径端点之一，否则将直径锯断连向 x，一定可以构造出一个更长的直径。

孤立点是平凡的，以下的树默认结点数都大于 1。

结点大于 1 的树一定至少有两个直径端点，而且由于本题目同时限制了另一个直径端点必须是编号最小的，所以一棵树的直径也是唯一确定的。

所以当一个点 i 在树中的时候，p_i 是它所在树的一个直径端点，另一方面，当一棵树存在的时候，其两个直径端点一定都在 p 中出现过（两个端点各自的 p 就是对方）。

于是我们不妨计数不同的 p_i \ne i 的个数 s，树的数量可以被孤立点数加 \dfrac{s}{2} 确定。

一个树不会漏，因为它是非孤立点，一定有两个不同的直径端点；也不会重，因为满足题目限制的直径是唯一的。这样可以就 \Theta(n) 做完。

可以说明本题直接将 i 和 p_i 相连并求连通块数是正确的。因为你注意到这玩意实际上跟上面的东西等价，但是这样转化没有什么必要。

int n, x, a[maxn], ans;
int main() {
    scanf("%d", &n);
    rep(i, 1, n) scanf("%d", &x), ans += (x == i), a[x] |= (x != i); int s = 0;
    rep(i, 1, n) if (a[i]) ++s; ans += s / 2;
    printf("%d\n", ans);
    return 0;
}