[loj3031]聚会

对于一棵树（初始仅包含节点0），不断加入一个不在树中的节点$u$（不需要随机），并维护这棵树

具体的，对这棵树点分治，假设当前重心$v$有$d$个子树，假设其中第$i$个子树根为$r_{i}$，子树大小为$s_{i}$，且不妨假设子树大小单调不上升（即$s_{1}\ge s_{2}\ge ...\ge s_{d}$）

初始令$i=1$，并询问$(u,r_{2i-1},r_{2i})$，并分类讨论：

1.若$u$在$r_{2i-1}$或$r_{2i}$的子树中，询问结果为$r_{2i-1}$或$r_{2i}$，递归询问结果的子树即可

2.若$u$在$r_{2i-1}$或$r_{2i}$到$v$的路径即其子树中，询问结果为$\ne u,r_{2i-1},r_{2i}$，再询问一次$(u,v,r_{2i-1})$即可

3.若$u$不为上述两种情况，询问结果为$v$，若$2i\ge d$则$u$为$v$的新儿子，否则令$i$增加1并重复此过程

（特别的，若$d$为奇数，我们认为$r_{d+1}=v$，且若为第二种情况，则一定在$r_{d}$到$v$的路径上）

下面，来考虑操作次数：

令$T(n)$为$n$个节点的子树中最大询问次数，考虑$u$结束的情况，即以下三种——

（为了方便，记$D=\min(n-1,18)$，显然$d\le D$）

1.在第一种情况下结束：假设在$i$时结束，则至多需要$T(s_{2i-1})+i$次（由于$s_{2i-1}\ge s_{2i}$）

显然有$\begin{cases}s_{i}\le \lfloor\frac{n}{2}\rfloor&(i=1)\\s_{i}\le \lfloor\frac{n-1}{i}\rfloor&(2\le i\le d)\end{cases}$，也即$T_{1}(n)=\max(T(\lfloor\frac{n}{2}\rfloor)+1,\max_{2\le i\le \lceil\frac{D}{2}\rceil}T(\lfloor\frac{n-1}{2i-1}\rfloor)+i)$

2.在第二种情况下结束：此时即询问$\lceil\frac{d}{2}\rceil+1$，即$T_{2}(n)=\lceil\frac{D}{2}\rceil+1$

3.在第三种情况下结束，此时即询问$\lceil\frac{d}{2}\rceil$次，同理即$T_{3}(n)=\lceil\frac{D}{2}\rceil$

最终$T(n)=\max(T_{1}(n),T_{2}(n),T_{3}(n))$，初始状态为$T(1)=0$（此时将$u$作为该点的儿子即可），最大询问次数为$\sum_{i=1}^{n-1}T(i)$

经过计算，可得在$n=2\times 10^{3}$时，该值为39371（官方题解给出的值是39632），可以通过