出题人题解。

下文记 $Q(u,v)$ 为询问 $u$ 和 $v$ 得到的可重集。下文中两棵树代指存在蛋糕、布丁的道路构成的树，第一棵树由红色边构成，第二棵树由蓝色边构成。定义 $f(S,x)$ 为可重集 $S$ 中 $x$ 的出现次数，则对于任意 $x$，满足 $f(S+T,x)=f(S,x)+f(T,x)$，$f(S-T,x)=\max(f(S,x)-f(T,x),0)$。

特殊性质 B

首先，特殊性质 $\text{B}$ 是 trivial 的。注意到可能的答案唯一等价于两棵树中城市 $1$ 有共同唯一连接的城市 $u$，于是 $Q(1,u)=\{1,1,u,u\}$，而且 $\forall v, \{u,u\}\subseteq Q(1,v)$。这启发我们随便找一个城市 $x$，并在均匀随机找到一个城市 $y$，满足 $\{y,y\}\subseteq Q(1,x)$，再令 $x\gets y$，不断收缩下去。

一个显然的证明是，我们考虑出现 $2$ 次的所有节点在第一棵树 $1$ 到 $x$ 的路径上的相对位置，即删去无关元素得到的子序列。我们记这个子序列为 $p_1,p_2,\ldots p_m$，若 $p_i=y$，则 $p_{i+1},p_{i+2}\ldots p_m$ 已经不在第一棵树 $1$ 到 $y$ 的路径上，即不可能在后续可重集中出现 $2$ 次。因此单次期望至少收缩一半，期望询问次数为 $\log n$ 次。

$p_1,p_2,\ldots p_i$ 不一定会全部出现，原因是出现 $2$ 次的城市不一定按照线性排列，例如图中，记红色树为第一棵树，则有 $p=1,2,3,4,5$ 且 $Q(1,5)={1,1,2,2,3,3,4,4,5,5}$，然而 $Q(1,4)={1,1,2,2,3,4,4}$，城市 $3$ 仅出现了 $1$ 次。

特殊性质 $\text{B}$ 这启发我们，对于任意两棵树，我们都能在 $\log n$ 次查询内，找到一个节点 $u$，使得两棵树上 $1$ 到 $u$ 的路径除了端点无交。

特殊性质 C

特殊性质 $\text{C}$ 也可以尝试使用类似的方法去做。首先必然存在城市 $u$，满足 $Q(1,u)=\{1,1,u,u\}$，我们试图找到这个城市。考虑仍然随便找一个城市 $x$，并在 $Q(1,x)$ 中均匀随机找到一个城市 $y$，再令 $x\gets y$，不断收缩下去。但这会产生一些问题，城市 $y$ 不一定同时存在于两棵树 $1$ 到 $x$ 的路径上，只有存在 $1$ 到 $x$ 的路径上存在 $y$ 的树的路径会被收缩，另外一棵树上的路径可能甚至被加长。例如图中，假定我们初始时选定了城市 $x=3$，$Q(1,3)=\{1,1,2,3,3\}$，因为 $y\ne 1,3$，所以 $y=2$，然而 $Q(1,2)={1,1,2,2,4,5,6}$，集合大小反而变大了。还有一个类似的伪证是，集合中拓扑序的最大值会快速下降，但是事实上这组数据中，如果每个点向自己的儿子连有向边，唯一的拓扑序为 $1,6,5,4,2,3$，拓扑序的最大值仅减少了 $1$，这是因为一次收缩后拓扑序的拓扑序的最大值期望仅仅能达到原始集合的拓扑序的中位数，当原始集合大小较小时，收缩速度极慢，最劣时询问次数达到 $O(n)$ 级别。

我们注意到一开始随便找一个城市 $x$，必然满足 $Q(1,x)$ 中存在一个答案。于是我们考虑集合 $S$ 表示可能为一种答案的集合，$S=Q(1,x)-\{1,1,x,x\}$，每次在 $S$ 中中均匀随机找到一个城市 $y$，再令 $S=S\cap Q(1,y)$，不断收缩下去。一次收缩后拓扑序的拓扑序的最大值期望为原始集合的拓扑序的中位数，因此期望询问 $\log n$ 次，证明类似特殊性质 $\text{B}$。

至此，特殊性质 $\text{B},\text{C}$ 已经完成，我们发现除了这 $2$ 个特殊性质之外，其他特殊性质似乎与城市 $1$ 无关。实际上，总是询问 $Q(1,x)$ 一定是不行的。图中，$\forall x\ne 1, Q(1,x)=\{1,2\ldots n\}+\{1,x\}$，我们无法从询问中得出任何信息，因为将 $2\sim n$ 城市重新随机编号后，所有此类询问结果全部相同。这启发我们，在未来的思考中，一定不能只询问 $Q(1,x)$。当然，询问 $Q(1,x)$ 也同理是必要的。

正解

直接考虑正解怎么做。

我们同理随便找一个城市 $x$，初始时 $S=Q(1,x)-\{1,1,x,x\}$，每次在 $S$ 中中均匀随机找到一个城市 $y$，然后问 $Q(1,y)$。直接分析有些抽象，于是我们试图把 $Q(1,y)$ 的路径表示出来。

以上是询问 $Q(1,x)$ 得到的 $2$ 条路径（节点省略），即集合 $S$，如图，记红色路径经过的城市为红色，蓝色路径经过的城市为蓝色，城市 $1$ 和城市 $x$ 同时为红色和蓝色。我们考虑均匀随机找到一个城市 $y$，不妨设城市 $y$ 为红色。

现在第一棵树上 $1$ 到 $y$ 的路径已经被表示，考虑表示第二棵树上 $1$ 到 $y$ 的路径。我们注意到必然存在蓝色城市处于第二棵树上 $1$ 到 $y$ 的路径上。我们不妨设 $z$ 为第二棵树上 $1$ 到 $x$ 的路径上第一个蓝色城市。于是除了第二棵树上 $1$ 到 $z$ 的路径部分，第二棵树上 $1$ 到 $y$ 的路径再也没有蓝色城市，这是因为蓝色边构成一棵树。任意绘制一个节点 $z$。

$Q(1,y)$ 已经可以被表示为第一棵树上 $1$ 到 $y$ 的路径，第二棵树上 $1$ 到 $z$ 的路径，以及第二棵树上 $y$ 到 $z$ 的路径。尝试表示第二棵树上 $y$ 到 $z$ 的路径。这里我没有直接用蓝色边连接城市 $y$ 和城市 $z$，假定直接连接。

此时特殊性质 $\text{C}$ 的算法就是正确的。当询问 $Q(1,y)$ 时，集合 $S$ 会第一棵树上 $1$ 到 $y$ 的路径和第二棵树上 $1$ 到 $z$ 的路径更新，这是因为第二棵树上 $y$ 到 $z$ 的路径与原来的 $S$ 无交，集合 $S$ 可以永远保持两条链的形态。此时 $1$ 到 $y$ 期望能使得红色路径长度变为原来的一半，但蓝色路径的收缩没有保证，因此期望需要 $2\log n$ 次询问。

但是显然特殊性质 $\text{C}$ 的算法不能在所有情况下成立，例如如下的情况。

此时我们发现第二棵树上 $y$ 到 $z$ 的路径可能会大量经过红色城市，会与原来的 $S$ 产生大量交集，导致 $S$ 不仅收缩速度没法保证，还不符合两条链的良好结构，会导致收缩过慢甚至无法收缩或者答案错误。这是一个瓶颈。

既然第二棵树上 $y$ 到 $z$ 的路径非常复杂，我们尝试把它容斥掉。注意力惊人的选手可能会发现我们意外地表示了 $Q(x,y)$。此时 $Q(x,y)$ 已经可以被表示为第一棵树上 $x$ 到 $y$ 的路径，第二棵树上 $x$ 到 $z$ 的路径，以及第二棵树上 $y$ 到 $z$ 的路径。我们发现前 $2$ 个部分我们都不想要，最后的部分我们希望容斥掉，于是 $Q(1,y)-Q(x,y)+\{y\}$ 就可以表示第一棵树上 $1$ 到 $y$ 的路径和第二棵树上 $1$ 到 $z$ 的路径（不含城市 $z$）。每次收缩需要花费 $2$ 次询问，是原来的 $2$ 倍，于是最劣询问 $4\log n$ 次。

但是这真的对吗？

注意到我们还没有保证过两棵树上 $1$ 到 $x$ 的路径完全无交，我们不想要的第一棵树上 $x$ 到 $y$ 的路径和第二棵树上 $x$ 到 $z$ 的路径中，也可能包含第一棵树上 $1$ 到 $y$ 的路径和第二棵树上 $1$ 到 $z$ 的路径上存在的城市，会导致需要的城市被意外删除，破坏两条链的结构，反例可以回顾特殊性质 $\text{B}$ 说明出现 $2$ 次的城市不一定按照线性排列的部分。

回顾特殊性质 $\text{B}$ 的部分，我们发现可以通过 $\log n$ 次询问，使得使得两棵树上 $1$ 到 $x$ 的路径无交。直接任意找到这样的一个节点即可。

总询问次数为 $5\log n$ 次。

关于正解收缩部分为什么是 $Q(1,y)-Q(x,y)+\{y\}$。如果直接用 $Q(1,y)-Q(x,y)$ 收缩，当城市 $y,z$ 同时与城市 $1$ 有边连接时，会得到空集。我们尝试保留其中一个，注意到我们并不知道 $z$ 的位置是什么，因此只能增加城市 $y$。

注意特判初始操作结束后 $S=\emptyset$，答案为 $x$。

至此，本题结束。

实际上，我们有一个更紧的期望上界，考虑到初始的 $\log n$ 次跳跃和 $2\log n$ 次收缩的两条链，包含的城市总数不超过 $n$，因此这 $3$ 个 $\log n$ 绝对无法同时取满的，考虑对着这个东西计算最大值，得到最劣次数为 $75$ 次。然而，初始的 $\log n$ 次跳跃初始节点可以均匀随机生成，目前我能构造跑出来的最劣 $50\sim 60$ 次，可以随便过。