Exeabow_sky
点分治
树上路径统计或最优化。(无根树)
找重心,分别考虑子树,标 vis。复杂度 O(nlogn)
路径合并信息。
对于较多次的查询可以用点分树;或离线,一次点分治处理完。
[CSP-S2022 T4]
也可点分治。
对于 k=2,对链在点分治中维护信息,离线;对分治中心 h,对两子树中点 a,b,做 like-DP,在一次 DFS 中算出,再算出答案。
但对于 k=3 呢?稍微预处理一下,做细节上的处理。
边分治
同样是找重心。但要做一些特殊处理,加入一些 0 权边与虚点(转二叉树)。
感觉不如点分治
长链剖分
x 的子树中距离 x 距离为 d 的个数。长剖优化 DP。
标签:20,分治,离线,学长,2023.8,DP From: https://www.cnblogs.com/Zaunese/p/17643584.html