IOI2022 无线电信号塔

发布时间 2023-10-04 21:49:14作者: pidan007

询问实际上是求笛卡尔树上的叶子结点个数,因为非叶子一定无法与子树内通信

发现如果两个叶子 \(u,v\)\(\text{LCA(u,v)}\) 的某一祖先 \(p\) 进行通信,那么 \(p\) 的祖先也一定能通信,保证两两能通信的关键就是一棵对于所有关键点的虚树,由于关键点之间并不存在祖先后代关系,因此笛卡尔树上的虚树大小一定是二倍叶子数 \(-1\)

求虚树大小是不好求的,但可以感受到虚树上的非叶子性质是很好的,记

\[time(u)=H_u-\max(\min\{Subtree(ls_u)\},min\{Subtree(rs_u)\}) \]

也即 \(u\) 的子树内可以选出两个信号塔通信的最小 \(D\),为了最大化答案,一定会贪心地选择所有满足 \(time(u)\ge D\) 的子树根放到虚树上,用一个主席树就可以求出

然而求的答案可能出现选出的信号塔在区间外的情况,但是因为是在笛卡尔树上,所以只会在边界出现,同样可以在主席树上二分实现