2022-9-26 做题记录

UOJ748

UOJ751

找出所有二进制有 log2n2\frac{\log_2 n}{2}(因为要求是偶数,所以取 142\frac{14}{2},202{\frac{20}{2}}) 个 1 的数,把每条边依次用这些数分配一个编号,数量一定是够的。

之后二进制分组询问,这样对于每个叶子一定正好有一半的询问它是一个孤立的点,之后我们考虑一定有些点在删除所有叶子之后成为叶子,这些点一定有一半的询问中它只和我们已经删掉的点在同一连通块中,这样一直操作我们就能求出树的拓扑序。

接下来我们考虑从根到叶子依次确定它的父亲。

树上若干的点集的交一定包含每个点集最高点中最低的那一个,对于一个点,我们取出它到父亲的那条边存在的那些点集,它们的交集一定是它的父亲(如果不考虑它自己的话)(因为对于两条边都一定存在一个询问使得第一条边出现第二条边不出现),于是我们记录每个集合中已确定深度的点中的深度最大值,之后就可以求出它的父亲。

https://uoj.ac/submission/585132