zcmimi's blog

arrow_back树链剖分共22篇文章

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

点击跳转

先钦定树的重心处理出答案

若当前点是距离最大点对的lca(即在它们之间的路径上),这个点就是最优的

否则最优答案一定在最大点对的lca的子树中

每次都选树的重心来处理,最多需要处理\log n次,总复杂度\Theta(n \log n)

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

点击跳转

模板

avatar
zc
2020-01-06 01:03:00
查看原题

点击跳转

先考虑没有换根的操作(设根节点为1)

修改点x的权值

被影响的只有1\rightarrow x上的点,设p_1,p_2,...,p_k1\rightarrow x上的点

s_ii子树点权和

将修改看成增加v

修改后贡献为

\sum_{i=1}^k (s_{p_i}+v)^2-\sum_{i=1}^k s_{p_i}^2= k\times v^2+2v\sum_{i=1}^ks_{p_i}

我们需要预处理出s_i^2,维护s_i

考虑换根操作:

x为根,p_1,p_2,...,p_k1\rightarrow x上的点

a_i为在1为根时v_i的点权和,b_i为在x为根时v_i的点权和

可以发现a_{i+1}+b_i=a_1=b_k(因为所有点的点权和总是相同)

ans_x表示x为根时的答案

ans_x=ans_1+\sum_{i=1}^k b_i^2-a_i^2

=ans_1+\sum_{i=1}^k (a_1-a_{i+1})^2-a_i^2

=ans_1+\sum_{i=2}^k (a_1-a_i)^2-a_i^2

=ans_1+ (k-1)a_1^2- 2a_1\sum_{i=2}^k a_i

=ans_1+ s_1[(k+1)s_1-2\sum_{i=1}^k s_{p_i}]

可以使用树链剖分+(树状数组/线段树)或LCT维护

avatar
zc
2020-01-05 18:45:00
查看原题

点击跳转

换根树链剖分

前置知识:树链剖分

题意:树链加,子树加,需要支持换根,查询树链和,子树和

树链加、查询树链和 与普通的树链剖分一样

主要讲:

需要支持换根,子树加,查询子树和

设当前查询的点为x

情况1: x就是根,直接输出整棵树的和

情况2: 根在x子树内:

找到根到x路径上的x的儿子

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

点击跳转

在每条重链上搞一个set

或者用线段树+二分

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

点击跳转

先根据原来的边建树

一条新边(x,y)能影响的边有树上x \rightarrow y路径上的边

那么这道题就转化成了树剖+线段树维护最值

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

点击跳转

直接树剖即可

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

点击跳转

一开始看到题面是懵逼的

突然发现1 \le a \le 10

直接在每个重链顶端和节点上放个vector

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

点击跳转

可以用并查集把环套树上额外的一条边找出来

然后就是树剖了

用树状数组维护前缀和

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

点击跳转

仔细考虑一下,最终能够形成最小权值的生成树的情况一定是把S都用在减小某条边的费用

  1. 如果那条边在最小生成树上,那么直接处理即可

  2. 如果在外面,设这条边为x \rightarrow y,我们求出最小生成树上xy上最大的一条边,删掉这条边

枚举删掉哪条边,然后执行上面的操作就可以了

记得开long\ long,rmq的数组开大点

2/3
Search
search