【XR-2】永恒

【XR-2】永恒

给定大小为 (n) 的两棵树 (T_1,T_2)，以及 (T_1 o T_2) 的一个映射，求：

[sum_{xin T_1}sum_{yin T_1}sum_{uin T_1}sum_{vin T_1} [u<v][x<y][[u,v]in [x,y]] extrm{dep}_2( extrm{LCA}_2(x,y)) ]

( m Sol:)

先枚举 ((u,v)) 变成：

[sum_{uin T_1}sum_{vin T_1} [u<v] extrm{dep}_2( extrm{LCA}_2(x,y))sum_{xin T_1}sum_{yin T_1}[x<y][[u,v]in [x,y]] ]

对于前者考虑点分治加容斥，我们选一个点 (x) 并统计以其为根的答案，那么此时我们只需要统计跨越子树的答案，此时两条不在同一子树内的点对答案可以产生贡献 ( extrm{size}(x) imes extrm{size}(y))

由于使用点分治+容斥，那么此时我们只需要统计全集的答案，那么将所有点建立虚树，然后在树上差分，使用 LNOI2014 LCA 的技巧，那么我们只需要统计子树权值平方和。复杂度为 (mathcal O(nlog^2 n))

当然，我们计算的答案是无视了 ((x,y)) 的顺序性的，所以答案需要乘以 (frac{1}{2})

代码把人写枯了。注意一个细节，我们的贡献是真实树上的 ( m size)，不是点分治时的 ( m size...)