• 周一. 8月 15th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

树上问题

admin

11月 28, 2021

先发出来,防止后期咕掉

树链剖分

重链剖分

(;)
从每个点到根的路径上至多会有(log(n))条轻边。(每次走轻边子树规模至少除2)
所以对于树上的任意一条路径,从lca处往两边拆分,至多会有(log(n))条重链
每次都要跳所在所在重链顶端较深的那一个

NOI2021 Day1 T1

(;)
现在要维护边的信息,但修改操作并不是一条简单路径,还有与点相邻的一些边。
所以,如果还是在边的角度去思考,就没有什么前途。
考虑点边转化
把一条边的信息用点的信息呈现出来
不妨对于每个点都维护一个颜色。
那么考虑让重边所连接的两个点颜色相同,反之不同。
而在一次修改时,只需将这条路径上的所有点都涂上之前没出现的颜色即可,发现这样恰好满足条件。
问题转化为:求一条路径上,相邻点满足颜色相同有多少个,这个用树剖+线段树维护就可以了
线段树维护:对于每个节点,维护三个信息:答案,左端点的颜色,右端点的颜色。这样就可以实现合并了

经典交互问题

(;)
可以询问点之间的距离,求出二叉树的结构。
(nleq 3000),至多进行(30000)次询问
(;)
先求出深度,按深度从浅到深去确定每一个点的父亲。
对于当前已经确定的树的部分进行重链剖分
假设我们要确定(x)的位置,从根节点(u)开始:
询问(x)(u)所在重链底端(y)的距离,因为深度都是已知的,那么借此可以求出(x)(y)的lca的深度,假设这个点为(p)
如果(p)的儿子的数量(leq 1),说明找到了,否则继续从轻儿子(w)的子树中继续递归寻找
(;)
因为每次找到一个点,都要重新对整颗树进行剖分,时间复杂度:(O(n^2))
而在重链上跳保证了询问次数是(O(n; log(n)))

Codechef GCD

(;)
只需注意:在单点修改,递归更新父节点gcd时,这个过程也是一个log,而不是两个log。因为它相当于对于一个数(v)不断地取gcd,取到1就停了

P5354

(;)
容易想到是对线段树每个节点维护(f,g):代表进来0/1,出去会变成0还是1
暴力合并是(O(64))的,思考如何快速合并。
因为位与位是互不影响的,不妨考虑进来的是”0000…000″,出去的数用二进制表示是什么
这样我们就能知道每一位进来了0,出去是什么
分类讨论,对于左边的(f)是1的,代表变成了1,只需看右边的(g)是否是1就行了。对应着左(f)和右(g)都是1,对这俩数&一下
或左边的(f)是0,看右边的(f)是否是1,我们不妨把左边的(f)取个反,也是左(f)和右(f)做&运算
这样就把合并变成了(O(1))

P4211

(;)
扫描线去掉一维,变成一个前缀与询问(z)的lca深度之和。
考虑加一个点时,把其到根的路径上+1,查询是直接查询点到根路径之和,容易发现这样是对的

CF757G

(;)
与上题一模一样,改成在线了。
在线?那就主席树,主席树维护树上每个点插入一个前缀现在的和。
交换?为啥是(x)(x+1),因为出题人不会做。
发现对于([1,x-1])([x+2,n])都没有影响,因为和插入顺序没有关系。
相当于只改了两颗线段树,一个log修改

P5314

(;)
可以根号分治来做
或对于每个点维护平衡树(只维护连出去轻边的信息)
这样树剖的时候,只有在重链跳到另一个重链时会经过一条轻边,会修改log次,加上平衡树,是两个log
查询时暴力把那最多3个点插入到平衡树中,然后再删除,一个log

长链剖分

(;)
子树深度最大的那个作为重儿子
这样一个点到根节点的路径上轻边最多是(O(sqrt n)级别的)
构造极限数据
一颗二叉树,倾斜看像三角形的形状
从根开始一直往左下走的所有节点,往右伸出一条链,且长度依次减2
这样左边这条链全都是轻边,设其长度为(L),则需要(O(L^2))的节点,那么(L)最坏是(O(sqrt n))级别
(;)

优化树形dp

(;)
dp状态中往往有一维是深度
CF1009F
状态为(f_{i,j}),暴力转移为(O(n^2))
考虑让(i)直接继承重儿子的信息,然后对于轻儿子暴力去合并
会发现,对于每个轻儿子来说,其dp数组的状态,是其所在重链的长度
那么总复杂度就是所有重链长度的和,即(O(n))

求k级祖先

(;)
先预处理(2^i)祖先
然后在每条重链(长度为d)的顶点处(x),预处理出(x)(1,2,…,d)级祖先,和这条链上的所有点
那么询问时找到(2^i<k<2^{i+1})直接(O(1))得出答案

P4292 重建计划

(;)
01分数规划

[c=frac{sum_{i=1}^n x_i a_i}{sum_{i=1}^n x_i b_i}
]

(;)
要让(c)最大化
不妨去二分这个(c),问题就变成了:

[sum_{i=1}^n (a_i-b_ic)x_i geq 0
]

(;)
也就是把每个点的点权看作(a_i-b_ic),然后我们要在其中选出若干个数,使得和为正,这样问题就变得简单了
题目的限制和路径的长度有关。
不妨设计(f_{i,j})表示(i)的子树内长为(j)的路径权值和最大是多少
这个东西就可以用长链剖分来优化。
与重链剖分类似的,在长链上也维护线段树
这样外层01分数规划有一个log,总复杂度:(O(n;log^2 n))

虚树

(;)
只关心关键点的相对位置
建立虚树的过程
将关键点按dfs序排序
维护单调栈(存储当前点到根的路径上的关键点)
若发现仍然在这条链往下的地方(入栈,先不连边)
否则,找出与栈顶的lca,然后依次弹栈,在弹栈的过程中加边,并把lca加入栈中。

NOI2021 Day1 T3

(;)
分析性质的题是我要加强的。。。
首先考虑部分分的情况
28pts
一个点(x)可以被走到,当且仅当它在一条(s->t)的路径上
这等价于,(s)可以走到(x),(x)可以走到(t),那么正反图各跑一遍bfs就可以了
(O(nq))
36pts
容易发现原图长成一颗树的形状(废话),但一个点的入度不可能大于1,即:这是一颗外向树。
预处理到根上有多少个点(深度)
(;)
分析一波性质,乍一看这个东西长的非常奇怪。
先不管那么多,因为一个点可以被重复经过,先缩个点再说,说不定会有一些奇怪的性质。
(A->C,B->C),若(A,B)之间的边是(A->B),那么(A->C)的边也不用连了,因为我们只关心一个点能走到哪里,而并不关心哪些边存不存在,只要不影响点之间的关系就行。
在DAG上,某个点(x)可能有多个入度(r_1,r_2,…r_k),那么其中必定有一个点,使得剩余(k-1)个点向其都有连边。
可以使用反证法,如果每一个点都满足有一个出度,那么就必定构成了一个环,就不满足这是DAG的性质了。
所以把其余(k-1)个点到(x)的边删去。
所以每个点现在最多只有一个入度了,又变成了外向树的形状
(k)条边后,这些端点与(s,t)构成了一些关键点,而我们具体只关心这些关键点,建一颗虚树,而关键点数量很少,大约也就10的级别
(O(10q))

点分治

$;$
模板和原理已在前面写过
下面是几道比较好的例题

NOI2014 购票

(;)
dp的柿子我就不推了,可以表示成一个用斜率优化表示的柿子
但从中我们需要总结出一些东西。
发现对于(ax+by)这样的形式,其中(a,b)是常数,(x,y)只和我们枚举的转移点(j)有关,那么就一定可以用斜率优化。
但这道题不同的一点事,我们是在树上做dp,且有长度的限制((l_v)),而关于路径长度这东西,用点分治就十分套路了
考虑点分治
找到分治中心(W)后,因为这是一颗有根树,先递归带有根的那部分。
然后对于剩下的几颗子树,继续递归即可
可以发现这有些像cdq分治的思路

发表回复

您的电子邮箱地址不会被公开。