题解：P12403 [COI 2025] 象掌兽 / Lirili Larila

· · 题解

[COI 2025] 象掌兽 / Lirili Larila

前言

本题解仅说明思路，代码之后补上。

正文

树

考虑树怎么做。

先考虑距离为奇数的两个点。例如 (7,2) 这一组，然后整理一下图。

如上图，红线左边的点离 7 更近，右边的离 2 更近，且没有相等距离的点，所以满足 a+b=n 时（没蓝点）一定满足 dis(s,t) 为奇数，否则一定不满足。而红线的位置就是 (7,2) 这条链中间的边。

经过观察可以发现其实 (5,3) 这一组的答案与 (7,2) 一样，因为红线的位置是一样的。因此只要保证红线的位置不变，答案都是一样的。所以若一定有解，那么一定存在一组邻的点满足题目条件。

再考虑距离为偶数的两个点。例如 (7,4) 这一组，然后整理一下图。

如上图，红点左边的点离 7 更近，右边的离 4 更近，与 3 相连且不在链 (7,4) 上的点（图上未标注，但是可以易推）。而红点的位置就是 (7,4) 这条链中间的点。

与奇数的情况类似，可以得出若一定有解，那么一定存在一距离为 2 的点对（中间是红点）满足题目条件。