洛谷4565 [CTSC2018]暴力写挂
Luogu LOJ 分析 题目中的式子等价于 我们把一边的点染成黑色，另一边的点染成白色，然后对第二棵树上的这些点建虚树，则一个点在第二棵树上成为 LCA 当且仅当在它不同的两棵子树中选择了两个颜色不同的点。于是树形 DP 一下即可。 虽然是 $\mathcal{O}(n\log^2 n)$ 的但是跑得挺快的，不需要卡常就可以过。 代码 // =======================...
Luogu LOJ 分析 题目中的式子等价于 我们把一边的点染成黑色，另一边的点染成白色，然后对第二棵树上的这些点建虚树，则一个点在第二棵树上成为 LCA 当且仅当在它不同的两棵子树中选择了两个颜色不同的点。于是树形 DP 一下即可。 虽然是 $\mathcal{O}(n\log^2 n)$ 的但是跑得挺快的，不需要卡常就可以过。 代码 // =======================...