CF755C PolandBall and Forest - Solution

现在有一个未知的森林，给

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

相连并求连通块数是正确的。因为你注意到这玩意实际上跟上面的东西等价，但是这样转化没有什么必要。

CPP

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;
}

CF755C PolandBall and Forest - Solution

文章操作

相关推荐

评论

CF755C PolandBall and Forest - Solution