P3233 [HNOI2014] 世界树

发布时间 2023-11-01 09:02:02作者: 御坂夏铃

将关键点以深度为第一关键字,编号为第二关键字从小到大排序。

建完虚树后依次考虑这些关键点可能的管辖的结点。每次在虚树上向上跳,当遇到某个已经被访问过的结点时,根据我们的排序条件,显然再往上的结点就一定不是当前关键点管辖的了。但是在向上跳的这条链上的子树内的结点不一定由当前关键点管辖,也有可能由管辖上面那个访问过的结点的关键点管辖,具体分界点可以用两个关键点的距离计算出来。

确定当前关键点可能的管辖的结点后,容易发现它们一定是某棵子树内的所有结点。其中在向上跳的那条链上也就是访问过的那些结点一定不会变了,但它们子树内的结点可能由后面的关键点管辖。我们不妨先将当前关键点的答案置为子树大小,然后在后面遇到新的在子树内的关键点时,减去它们的子树大小即可。

这个方法非常简洁好写,让这题成为了一道有趣的题!