题意简述
交互题。有一棵 $n$ 个点的无根树,你至多询问 $2550$ 次点集 $X$,交互器会告诉你 $X$ 的虚树大小。求这棵树。
$n\le 100$,虚树是也是无根的,没有二度点。
主要思路
询问 $\{[n]\backslash x\}$ 可以知道 $x$ 是不是叶子。
然后随便取一个叶子为根 $rt$。
对每个非叶子 $i$ 和叶子 $j$ 询问 $\{rt, i, j\}$ 可以知道 $i$ 是否是 $j$ 的祖先。不妨设 $S(x)$ 为点 $x$ 子树内的叶子集合。
注意到树上没有二度点,所以对于点 $x$ 与其父亲 $f$ 有 $S(x)\varsubsetneq S(f)$($x,f \neq rt$)。
所以我们可以对于每个任意两点之间找出他们是否有祖先关系了。
然后对于点 $x$,求一个祖先 $p$ 使得 $\operatorname{siz}(p)$ 最小,就是其父亲。
参考代码
这 cf 怎么不支持__uint128_t
啊(半恼)
1 |
|