9056

先考虑一条链的情况。

用 nth-element 的思路，先确定链的两端点 $L,R$，在 $[L,R]$ 范围内随一个点 $u$，显然可以询问 $(L,u,i)$ 知道 $u$ 在 $[L,i]$ 还是在 $[i,R]$。然后根据在 $[L,i]$ 和在 $[i,R]$ 的 $u$ 的数量选择递归到 $[L,i]$ 和 $[i,R]$。这个是 $O(n)$ 的，可以过 A 性质。

对于不在一条链上的情况，还是用刚才的思路，假设我们知道了树上的两个点 $L,R$，并且确定重心在 $L$ 和 $R$ 的路径上，不妨把树上的点分为 $4$ 个集合，$L,R,P,T$，其中 $L/R$ 为在 $L/R$ 外侧的点，$P$ 为在 $L$ 和 $R$ 的路径上的点，$T$ 为不在 $L,R$ 路径上且在 $L$ 和 $R$ 之间的点，如图：

对于 $T$ 中的点 $i$，我们称 $u(u\in P)$ 是 $i$ 的「投影」当且仅当存在简单路径包含 $L,i,u$ 且存在简单路径包含 $u,i,R$。例如上图 $3$ 是 $13$ 的「投影」。显然可以通过两次询问知道 $i$ 的「投影」是否为 $u$。

显然，可以通过一次询问知道一个点处于哪个集合中，具体地：

和前面类似，随机一个 $P$ 上的点 $i$，然后询问，显然有：

这样也可以知道以 $i$ 为根在 $L$ 一侧的子树点集 $v_L=P_L\cup T_L\cup L$ 和在 $R$ 一侧的子树点集 $v_R=P_R\cup T_R\cup R$。

显然若 $v_L\ge\left\lceil\dfrac{n}{2}\right\rceil$ 则重心应在 $L$ 到 $i$ 路径上，若 $v_R\ge\left\lceil\dfrac{n}{2}\right\rceil$ 则重心应在 $i$ 到 $R$ 路径上，若均不超过 $\left\lceil\dfrac{n}{2}\right\rceil$ 则重心只有可能在 $i$。

若重心不在 $i$，递归到 $[L,i]$ 或 $[i,R]$ 即可。假如递归到了 $[L,i]$ 则此时有 $R\gets R\cup P_R\cup T_R\cup T_i,P\gets P_L,T\gets T_L$。

注意到为了确保复杂度，这里的随机 $i$ 应当为带权随机，$i$ 的权值应为满足 $j$ 是 $i$ 的「投影」的 $j$ 的数量 $+1$。

显然没办法快速直接查询出来每个 $i\in P$ 的权值，那么考虑随机随 $P\cup T$ 中的点 $i$，如果 $i\in P$，则不变，反之则令 $i$ 的「投影」为 $u$，让 $i\gets u$，容易发现这样随机的权值和上面所说的是一样的。

此时期望询问次数为 $O(n)$。

现在我们无法确定起始的 $L$ 和 $R$。

我们有结论：随机 $L$ 和 $R$，若重心不在 $L$ 和 $R$ 的路径上则重随，期望重随的次数是 $O(1)$ 的。

那就直接随机 $L,R$，用上面的方法找重心，然后用摩尔投票判定找到的「重心」是否是真的重心即可。

期望询问次数 $O(n)$。