涉及子树及换根操作的树上数据结构维护

jys posted @ Nov 29, 2013 11:08:55 PM in 未分类 , 1283 阅读

权值在点上。

                             ①

{包含操作:换根,子树查询/修改}

任选根(假定为1)进行dfs,随时记录哪个点是树根。假设要修改/查询的子树为x,当前树根为root,root和x在以根为1的树中有如下四种关系:

一,x为root的子孙,那么(x在(以root为根的树中)的子树)即为(x在(以1为根的树中)的子树),在dfs序上对应一个区间。

二,lca(x,root)!=x&&lca(x,root)!=root,同情况一。

三,x==root,此时要查询的是整棵树,对应区间[1,n]

四,root为x的子孙,令p为x的某个儿子,使得p为root的祖先。那么此时查询的子树即为整棵树去掉(在以1为根的子树中p的子树)的部分。此时的查询对应整个区间[1,n]去掉p的子树对应的区间。

                            ②

{包含操作:换根,子树查询/修改,链查询/修改}

任选根(假定为1)进行重链剖分(对于每条链,并不维护一个数据结构,只是进行形式上的链剖分),并维护其dfs序列,并且每个点在dfs时先递归处理它的重儿子,然后再处理它的轻儿子。

子树查询/修改和①一样处理。

链修改/查询:一条链会被分成O(lgn)条重链上的部分,而每条重链在dfs序列上都是连续的,所以一条链上查询被分成lgn个区间查询。

                           ③

{②+link/cut}

动态树维护链剖分结构,用splay维护dfs序列,虚实边变化时在splay上即时进行修改,使得每个点在dfs序列上的后继都是它的实儿子。

                          番外:

{包含操作:路径修改,子树修改,单点查询,换根}

假设不存在换根操作。

要求存在操作的逆运算。对路径修改(u,v,delta)变成(root,u,delta)+(root,v,delta)+(root,lca(u,v),-delta)。

此时所有链操作的一段都是根节点。

考虑查询时,对查询点u答案可能产生影响的操作只有u的子树中的到根链操作,以及u的祖先的子树操作。

对dfs序列开两棵线段树。子树操作时直接在1线段树中区间修改。到根链操作时在2线段树中单点修改,记下这个操作。

查询时在线段树1中单点查询,在线段树2中区间查询。

要求支持换根操作时同理。

复杂度比上述其他方法都少了个lgn,还好写很多。真是神奇。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter