虚树已经降8级了，为啥不写写虚树呢|[AGC047D] Twin Binary Trees

forest114514 · 2025-04-30 09:07:43 · 题解

为啥一定要线段树合并？

枚举环上两个在第一个树的叶子 i,j，考虑他们的 LCA k，注意是满二叉树可以每个 k 的子树都做一遍，复杂度是 \sum dep=O(n\log n) 的。

每次枚举一个非叶子 k 的子树内的叶子，在第二颗树上建虚树，我们把 k 两边的子树分别染上不同颜色看做在不同集合 S_1,S_2 中，我们对每个叶子的权值是在第二个树中到根的点权积乘上第一个树中到枚举点 k 的点权积，对第二个树中作为 LCA 的非叶子节点权值就是到根的点权积的平方除去自己的点权，这样方便容斥计算一条链的点权积因为 LCA 也算了一次，发现我们此时需要求的大概是 \sum\limits_{i\in S_1}\sum\limits_{j\in S_2}val_i\times val_j\times val2_{LCA(i,j)}，可以在虚树上 dfs 的时候枚举一个点，统计子树内两个不同集合的点权和就可以合并贡献了。因为是枚举子树，所以可以归并两个子树按 dfs 序排序的顺序+线性建虚树做到 O(n\log n)。

注意不一定是枚举 LCA，可以变成路径上任意一个点，对于任意树可以直接边分治，类似暴力写挂，对分治的点集的叶子对应的在第二颗树叶子建虚树，然后 dfs 统计贡献，因为点分树是树高不超过 O(\log n) 的二叉树所以复杂度同样是单 \log 的。

时间复杂度 O(n\log n)，只是常数确实有点大就是了。