Passable Paths (hard version)

先写正常写法：

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

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

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

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

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

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

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

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

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

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

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