块状树

最近过于颓废一直拖着这篇小论文囧。。今天总算不颓废了。。写下吧。。
称树的一个联通的顶点子集为树块,一个树块的根就是这个树块中深度最小的顶点,那么如果将树划分成一些树块
有如下定理:
对于两个顶点,(1)若他们属于相同的树块,那么Lca肯定在该数块中,(2)如果属于不相同的树块,Lca肯定不在树块的根较浅的那个树块中。。。
证明:(1)废话
(2):否则Lca就会在另一个顶点与其树块的根的路径上,与Lca属于较浅的那个树块矛盾。。
现在以QTREE为考虑的问题。。
考虑QTREE,如果对每个点都维护其到其树块的根的路径上最大边权,那么我们的询问就可以用以下方法完成。。
设当前顶点是u、v
若在同一树块中,直接暴力..
否则可以使用维护的信息跳过一个树块。。
同时修改直接暴力可以解决。。
那么显然要让修改快,当然块越小越好,要让查询快,当然块越大越好。取个综合,就是Sqrt(N)了。。
那么就要搞出一种划分的方法使得,
每个块大小不超过SqrtN。。。
每个点到根最多经过SqrtN个块。。。
划分的方法有很多.。我想出来3个。。就说说最实用的那个吧。。
Dfs一下,对每个结点只要其属于的块大小不超过SqrtN,就把其孩子加入其属于的块。。否则其孩子自立一个块。。
这种数据结构的优点:
代码短,好写,没了。。
缺点:
只能维护单点(边)的修改,不能应付GSS7那样的神题,
速度:
速度还不错。。可以看下我交的那个八中OJ1036的代码。。。最快的那个第16。。。
写的时候的一些技巧:
修改的时候只需要修改该点在块里的后代,可以加快不少。
对每个点另开一个边表维护在块里的后代。
或者用Bfs来修改(快不了多少。。。)
代码:
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define rep(i,n) for(int i=0;i<n;i++)
#define tr(e,x) for(it e=x.begin();e!=x.end();e++)
#define pb push_back
const int maxn=30000,inf=~0U>>1;
using namespace std;
vector<int> E[maxn],Et[maxn];
typedef vector<int>::iterator it;
int n,q,w[maxn],L,D[maxn],F[maxn];
int own[maxn],M[maxn],S[maxn]={};
void Build(int t,int f,int d)
{
D[t]=d;F[t]=f;
int tmp=own[t];
tr(e,E[t])if(*e!=f)
{
if(S[tmp]++<L)Et[t].pb(*e),own[*e]=tmp;
Build(*e,t,d+1);
}
}
void Dfs(int t,int s,int m)
{
S[t]=s+=w[t];M[t]=m>?=w[t];
tr(e,Et[t])Dfs(*e,s,m);
}
void Change(int t,int u)
{
w[t]=u;
if(t==own[t])Dfs(t,0,-inf);
else Dfs(t,S[F[t]],M[F[t]]);
}
void Query(int a,int b,int&s,int&m)
{
s=0;m=-inf;
while(a!=b)
{
if(D[a]<D[b])swap(a,b);
if(own[a]==own[b])
s+=w[a],m>?=w[a],a=F[a];
else
{
if(D[own[a]]<D[own[b]])swap(a,b);
s+=S[a],m>?=M[a],a=F[own[a]];
}
}
m>?=w[a];s+=w[a];
}
int main()
{
scanf("%d",&n);int s,t;L=sqrt(n)+1;
rep(i,n-1)scanf("%d%d",&s,&t),–s,–t,E[s].pb(t),E[t].pb(s);
rep(i,n)scanf("%d",w+i),own[i]=i;
Build(0,-1,0);
rep(i,n)if(own[i]==i)Dfs(i,0,-inf);
scanf("%d",&q);
char cmd[100];int S,M;
rep(i,q)
{
scanf(" ");
scanf("%s%d%d",cmd,&s,&t);
if(cmd[0]==’C’)Change(s-1,t);
else
{
Query(s-1,t-1,S,M);
if(cmd[1]==’S’)printf("%dn",S);
else printf("%dn",M);
}
}
}

25 thoughts on “块状树

  1. 神牛可以继续开发块状树,例如使块状树支持对整个子树的操作。像这种操作树链剖分和link-cut tree都干不了。反证本菜估计现在会写Euler-tour tree的人也不多,到时候神牛再出几道题放在OJ上,块状树就彻底被推广为大众数据结构了……

  2. 对于多点(边)的修改可以对于当前块的根到当前块的每个叶子保存一个值,采用类似线段树的延迟处理方法,可以做到同样的时间复杂度。

  3. 回复WJBZBMR:本菜觉得应该可以吧= =。每次修改的时候树根所在的块暴力一下,子树的话应该是属于整个的块(吧?),只打个标记就行了。因为本菜是沙茶,所以如果说错了请众神牛BS……

  4. 回复中国脑筋:这个方法好像不是很可行。。。除非用线段树来维护每个小块。。不过那样还不如树链剖分囧。。。

  5. 请问“Lca肯定不在树块的根较浅的那个树块中”中的浅是指离树根的距离短吗。。怎么总觉得LCA应该肯定不在树块的根更深的那个树块中。。。或许是我理解能力太渣了

  6. 我觉得建个边表好些,否则有些邪恶的人可以把块状树每次dfs增到O(N)。就是一棵奇丑无比的花+长链                   5                  /1 – 2 – 3 – 4 – 6                                      7把5,6,7…,16全作为4的儿子,那么每次dfs 1 这个块的时间为O(n),因为枚举4的子树大小为O(n – sqrt (n))….不过没谁这么无聊吧?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>