讲个本题的幽默n^2做法
查看原帖
讲个本题的幽默n^2做法
788951
TLE_AK楼主2024/11/23 21:28

模拟赛考的,因为忘了长剖所以打的暴力 O(n2)O(n^2)

我们尝试利用树形+换根dp维护节点 uu 为根时,每种 ii 深度有多少个点(后文的 dpi,jdp_{i,j} )。

随后尝试直接用Cdpi,j3C^3_{dp_{i,j}},发现不可行,因为一些点重复计数了lca不为它们的点。
那么钦定点 uu 计数lca为 uu 的三元组,明显3个点都在不同儿子。
直接在刚才的贡献上减去Cdpv,j12×(szuszv)+Cdpv,j13C^2_{dp_{v,j-1}} \times (sz_u-sz_v)+C^3_{dp_{v,j-1}}就做完了。。。

这个方法感觉有点幽默(110行左右,我代码没带回来),不知道这个做法没有拓展(优化等)

2024/11/23 21:28
加载中...