zcmimi's blog

arrow_back长链剖分共2篇文章

avatar
zc
2020-01-18 22:40:00
查看原题

点击跳转

长链剖分模板

长链剖分优化dp

f_{x,i}表示x子树内与x距离为i的点的个数

f_{x,i}= \sum f_{to,i-1} \\\\ (f_{x,0}=1)

可以发现x从它的儿子继承答案

这时就可以用长链剖分优化dp了(一种类似\text{dsu on tree}的方法)

len_xx到叶节点的最长距离

我们将\max len_{to}设为x的重儿子

x直接继承重儿子的答案,而不用重新再算一次

其他的儿子再按普通方式计算

因为每条链只会被合并一次,因此总复杂度就是\Theta(n)

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

树形dp 长链剖分

加强版

先来考虑1 \le n \le 5000

f[i][j]表示在i的子树中与i距离为j的点数

显然f[i][j] = \sum f[to][j-1](f[i][0] = 1)

g[i][j]表示以i为根的子树中,点对(x,y)满足x,ylca(x,y)距离都是d,并且lca(x,y)i的距离为d-j的点对数

g[i][j] = \sum g[to][j+1]

ans = \sum_{i=1}^n (g[i][0]+g[i][j] \times f[to][j-1])

我们来考虑加强版

n \le 100000

有点像静态链分治和树链剖分

我们计算长链的时候结果不需要清空,其他儿子节点重新计算

这样可以省下长链的时间

长链剖分真是个毒瘤(指针毒瘤)

1/1
Search
search