Passable Paths (hard version)

发布时间 2023-11-13 21:53:30作者: Zlc晨鑫

先写正常写法:

我的评价是,后面的分讨我直接树剖拿下。

我觉得这样分讨方便一点。

lca(u,v)=v(或者u,反证就是一条链的形状),那么 lca(u,i)==i,保证i在链上。

然后还有Y字形路径,lca(u,v)=t,则lca(u,i)=id[i]>=d[t]

统一起来就是 \(lca(u,i)==i,d_{lca(u,i)}\le d_i\)


自己的想法很复杂,我的做法是维护整个树的形态,统计它有多少分叉。

首先,这些点集之间的路径一定是一棵子树,我们找它们所有点的LCA,它就是根。

然后我们希望对于一条链,都只在它的最深处被统计一次,显然深度最大优先。

直觉来说,把点按照深度从大到小排序。

证明:然后发现一条链上的点,最深处被统计一次之后,下一次被统计的点也是另外一条链上的最深点,依次类推,这样就成立了(因为统计过的点的链上的点的ask不为0,所以不会被重复统计)。

分叉必须不超过2,才是一条链。