树分治

发表于 更新于 分类于

$\ \ \ \ \ \ \ \,$关于树分治的复习笔记：

树链剖分

$\ \ \ \ \ \ \ \,$树链剖分也叫轻重链剖分，一般会套一个线段树，相当于一个优化过的DFS序，用每次优先遍历重儿子达到优化目的，常用于处理：

  1. 关于两点间路径的询问和修改（$O(n\log^2n)$）

  2. 关于某点子树的询问和修改（$O(n\log n)$），这里只用到了DFS序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
int w[N],v[N];
vector<int> G[N];
struct Tree_Chain_Dissection{
	int idx[N],w[N];
	int deep[N],fa[N],son[N],tot[N];
	int cnt,top[N];
	int dfs1(int a,int f,int dep){
	  deep[a]=deep[fa[a]=f]+1;tot[a]=1;
	  int maxson=-1;
	  for(auto v:G[a])
	  if(v!=f){
	    tot[a]+=dfs1(v,a,dep+1);
	    if(tot[v]>maxson) 
	    maxson=tot[v],son[a]=v;
	  }
	  return tot[a];
	}
	void dfs2(int a,int topf){
	  v[idx[a]=++cnt]=w[a];top[a]=topf;
	  if(!son[a])return;
	  dfs2(son[a],topf);
	  for(auto v:G[a])
	  if(!idx[v])dfs2(v,v);
	}
	void Init(){
	 	dfs1(rt,0,1);dfs2(rt,rt);
	  Seg.build(1,n,1);
	}
	int Query_Chain(int x,int y){//满足交换律
	  int ans=0;
	  while(top[x]!=top[y]){
	    if(deep[top[x]]<deep[top[y]])swap(x,y);
	    ans=(ans+Seg.query(idx[top[x]],idx[x],1,n,1))%mod;
	    x=fa[top[x]];
	  }
	  if(deep[x]>deep[y])swap(x,y);
	  ans=(ans+Seg.query(idx[x],idx[y],1,n,1))%mod;
	  return ans;
	}
	void Updata_Chain(int x,int y,int val){
	  while(top[x]!=top[y]){
	    if(deep[top[x]]<deep[top[y]]) swap(x,y);
	    Seg.updata(idx[top[x]],idx[x],val,1,n,1);
	    x=fa[top[x]];
	  }
	  if(deep[x]>deep[y]) swap(x,y);
	  Seg.updata(idx[x],idx[y],val,1,n,1);
	}
	int Query_Tree(int x)
	{return Seg.query(idx[x],idx[x]+tot[x]-1,1,n,1);}
	void Updata_Tree(int x,int val)
	{Seg.updata(idx[x],idx[x]+tot[x]-1,val,1,n,1);}
}TCD;

点分治

$\ \ \ \ \ \ \ \,$点分治是一种分治策略，其核心在于寻找树的重心，从重心分治解决，从而优化复杂度，实现的$O(n\log n)$分治复杂度，算上分治的操作可能复杂度会更高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int K,root,sum;
int f[N],size[N];
vector<int> G[N];
bool used[N];
void getroot(int u,int fa){
  size[u]=1;f[u]=0;
  for(auto v:G[u]){
    if(used[v]||v==fa) continue;
    getroot(v,u);
    size[u]+=size[v];
    f[u]=max(f[u],size[v]);
  }
  f[u]=max(f[u],sum-size[u]);
  if(f[u]<f[root]) root=u;
}
void getans(int u){
  //something
  used[u]=1;
  for(auto v:G[u])
  if(!used[v]){
    root=0;sum=size[v];
    getroot(v,0);
    getans(root);
  }
}

$\ \ \ \ \ \ \ \,$顺带一提动态点分治（点分树），只需要把重儿子重新连在一个图里，这样子我们会得到一个类似于二叉树的新树，每次修改操作的影响我们可以暴力上传，复杂度为$O(n\log n)$，算上细节的操作可能复杂度会更高。

边分治

$\ \ \ \ \ \ \ \,$边分治的思想是把一棵树每次找到一个边，使得去掉这个边后，留下的两棵树尽量一样大（重边），分治下去，使得复杂度降至$O(n\log n)$分治复杂度，算上分治的操作可能复杂度会更高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int size[N],ctedge,sum;
void getctedge(int u,int fa){
  size[u]=1;f[u]=0;
  for(int i=head[u];i;i=G[i].last){
    if(used[G[i].v]||G[i].v==fa) continue;
    getctedge(G[i].v,u);
    size[u]+=size[G[i].v];
  	int siz=max(size[G[i].v],sum-size[G[i].v]);
    if(siz<ctsiz)ctsiz=siz,ctedge=i;
  }
}
void getans(int u){
  //something
  used[u]=1;
  for(int i=head[u];i;i=G[i].last)
  if(!used[G[i].v]){
    ctedge=0;sum=size[G[i].v];
    getroot(G[i].v,0);
  }
	getans(G[ctedge].v);
	getans(G[ctedge].from);
}