题解：P10105 [GDKOI2023 提高组] 游戏

Cute_Wazzy · 2026-10-20 08:21:24 · 题解

我智力存在问题。

首先把距离拆成 dep_{u}+dep_{v}-2dep_{lca}，所以 dep_{u}+dep_{v}-2dep_{lca(u,v)}=x，dep_{u}+dep_{w}-2dep_{lca(u,w)}=y，dep_{w}+dep_{v}-2dep_{lca(w,v)}=z。

你注意到 lca 不好处理，所以考虑让他们的两两 lca 都是一个点，你如果手玩了一些例子就可以考虑用两两之间 3 条路径的交点 x 来刻画，那么此时 x 作为根的时候他们的 lca 都是 x，那么此时就可以解出 dep_u,dep_v,dep_w，那么你就关心 x 连出前三长的路径长度，这个随便换根。

然后你考虑怎么求出满足条件的这个交点，你直接发现这就是一个三维偏序，所以直接做就做完了。