模拟赛考的,因为忘了长剖所以打的暴力 O(n2)
我们尝试利用树形+换根dp维护节点 u 为根时,每种 i 深度有多少个点(后文的 dpi,j )。
随后尝试直接用Cdpi,j3,发现不可行,因为一些点重复计数了lca不为它们的点。
那么钦定点 u 计数lca为 u 的三元组,明显3个点都在不同儿子。
直接在刚才的贡献上减去Cdpv,j−12×(szu−szv)+Cdpv,j−13就做完了。。。
这个方法感觉有点幽默(110行左右,我代码没带回来),不知道这个做法没有拓展(优化等)