P15654 题解

· · 题解

首先考虑怎么计算 f(s,t)，首先容易发现只需要对所有 a_{u,v},(u,v)\in E 计算相对排名即可。一个非常简单的事实是我们只需要知道：\{a_{u,v}|v \in son(u)\} 就可以确定 a_u，并且我们也只需要把这个当作 a_u。那么我们可以通过 这个题 的技巧进行动态标号。对于比较两个 a_u，我们只需要写一个字符串哈希即可二分判定。当然字符串总长度非常大有 O(\sum deg_u^2)，所以你需要以若干个指针的形式记录之。

接下来寻找一些 f(s,t) 的性质，容易发现对于一条 s=p_0\to p_1\to p_2\to\dots \to t 的链，一定有 f(p_i,t)\ge f(p_{i+1},t)，更具体地说，存在一个前缀使得 f(p_i,t)=f(p_{i+1},t)+1，而剩余部分满足 f(p_i,t)=f(p_{i+1},t)（注意这里均不考虑 f(t,t)，它是特殊的）。

当然，我们可以发现另一个非常简单的性质，就是 f(s,p_i)< f(s,p_{i+1})。依据这一点我们可以证明上述性质。

仅根据以上性质，结合二分与你喜欢的数据结构即可在 O(n\log^2 n) 的时间复杂度内解决 o_xo_y=0 的问题。

接下来考虑 s\to t 这条链，不妨假设 x 比 y 更靠近 s，我们将 y 分类：f(s,y)\le r,f(pre_y,y)\le r 且 f(s,y)>r 和 f(pre_y,y)>r。这三类是依次排布的，所以可以通过二分快速划分出这三类。第一类和第三类对答案的贡献也容易统计，对于第二类，依据前缀 +1，后缀相等的性质，对答案的贡献为：d(s,y)+k-f(s,y)，所以我们现在需要计算：\sum_{y\in P} f(s,y)。回归它的原始定义：1+\sum [a_{s,x}>a_{s,y}]，我们将 a_{s,y} 拆分为两部分，一部分是 =a_{1,y} 的，另一部分是不相等的，对于 a_{s,x} 同理。容易发现只有 a_{s,x}\neq a_{1,x},a_{s,y}\neq a_{1,y} 的部分是不容易处理的。但是对于这部分容易把其容斥为以下形式：\sum_{x\in P} \sum_{y\in Q} [a_x>b_y]，其中 P,Q 是 1\to u 的路径。类比序列上的做法，分块即可。时空 O(n\sqrt n)。不过块长可能会因为常数问题需要大幅度的改动。

贴以下 码，这也太长了。