5
17
2016
0

【新姿势】树分治

一直以为树分治是个大块头,今天学习后发现基本的思想还是很好理解的。而做题不容易有思路,也是预料之中的,还需多加练习呐。

基于树链剖分的链分治没有很理解,点分治、边分治还是可以的。我决定暂且只学习点分治。

23:35-1:15


树的重心:

考察别人语文理解没意思。

POJ1655 定义了树的“平衡度”,删去某节点后使得生成的多棵树最“平衡”,该节点即为原树的重心。

树的大小为该树的节点个数。平衡:最大的子树 大小最小。

Define the balance of a node to be the size of the largest tree in the forest T created by deleting that node from T. 
For example, consider the tree: 


Deleting node 4 yields two trees whose member nodes are {5} and {1,2,3,6,7}. The larger of these two trees has five nodes, thus the balance of node 4 is five. Deleting node 1 yields a forest of three trees of equal size: {2,6}, {3,7}, and {4,5}. Each of these trees has two nodes, so the balance of node 1 is two. 

树上dfs 求重心与平衡度 O(n)

int ans[N],siz[N];//ans[i] 切掉i结点后的平衡值 
int mn,mnid;
void dfs(int x,int ff)
{
	siz[x]=1;
	R(i,x){
		int y=e[i].go;
		if(y==ff) continue;
		dfs(y,x);
		siz[x]+=siz[y];
		if(siz[y]>ans[x]) ans[x]=siz[y];
	}
	if(n-siz[x]>ans[x]) ans[x]=n-siz[x];
}
/*****main*****/
	dfs(1,0);
	mn=inf;mnid=0;
	F(i,1,n){
		if(ans[i]<mn) mn=ans[i],mnid=i;
	}
	printf("%d %d\n",mnid,mn);

树的重心的基本性质:

n个节点的树,删去重心后生成的多棵子树中,最大的树的大小<=n/2

==>以重心为根的树,从根开始dfs,每层递归的规模减半

==>树的深度O(logn),避免链造成的极端复杂度


树分治是一种算法。其中点分治更常见。

处理树上点对问题,即点对间的树上路径问题

点分治将其转化为经过根的满足一定条件的点对(路径)问题。

转化的方式是分治:

两点间的路径分为两种:

1、经过根

2、不经过根

对于第二种情况,从根的子节点层层递归找下去,一定存在一棵子树,使得这两点间的路径经过该子树的根。

那么只需递归处理第一种情况就好咯。

从树的根节点向下递归,每层处理出经过当前子树根节点的路径的信息。

每个节点都会被处理到,那么为了保证树的"平衡",每层递归都将当前子树的重心作为当前子树的根。

即每次找到重心,然后把重心去掉,对分成的每两棵树之间分别统计路径信息(以重心的每个相邻点为根,遍历整棵子树即可得到这

个根到每个结点的统计信息),就可以知道包含这个重心的所有路径的信息。对于其他路径,即不经过根节点的路径,则向下递归,

进行同样的操作,直到单个叶节点为止。(Mato:注意这一个点所构成的路径有时也要处理一下)

每层进行什么操作呢?根据具体问题具体处理,反正整体和部分的操作是一致的。具体下文提到。

 

类比:边分治

每次找到一条边,使得删掉这条边后分成的两棵子树大小尽可能平均(保证复杂度),然后以删掉的边的两端点为根,分

别统计根到两棵树中的每个结点的路径信息,最后合并算路径,即可得到包含这条边的所有路径的信息,剩下的路径在两棵树中递归

处理。
 


进一步探讨&&点分治与边分治复杂度比较:(%Mato):

对于不同的操作,每层有不同的处理方式:

1、操作可反(比如计数问题:统计某种路径的条数):

补集转化的思想,由于子树之间互不相交,不需要进行容斥即可计数:

先将所有子树合在一起统计,再减去两端点处在相同子树内的路径信息。

2、操作不可反(比如找“最优路径”):

不能采用上面的方法,只能枚举所有的子树对。

 

如果有S棵子树,则有O(S2)个子树对,最坏情况下(菊花树),S=N-1,

此时一一枚举子树对必然会导致总时间复杂度升到O(N2)以上。

解决办法:从小到大枚举子树,每处理完一棵子树就将其和前面的合并,此时算法效率取决于合并的方法。

如果使用归并法(大小为A的和大小为B的合并次数为A+B),对于星形树的合并总次数仍然为O(N2),

如果能保证大小为A的和大小为B的合并次数为min{A, B},则可以保证合并总次数在O(N)以内,从而可以保证总时间复杂度为O(NlogN)。

类比:边分治

由于分成的永远是两棵子树,所以在处理子树之间的关系上能够保证O(N),

问题是它并不能保证每次分成的两棵子树大小非常平均,

在最坏情况下(菊花树),不管删哪条边分成的两棵子树大小都是一个1一个(N-1),这样就会使总的时间复杂度上升为O(N2)。

——处理菊花树:加虚点,转化为二叉树,会导致常数较大

保证每个点的度数<=3,从而保证递归深度O(logn)


空间复杂度:O(n)

时间复杂度:O(nlog^2n)

具体问题:

给你一棵n 个点的树,树有边权,然后给定一个W,问有多少点对(u, v),使得u,v 的距离大于等于W。(n<=10^5)

每层处理的问题:给定一棵有根树,根为p,问有多少点对(u,v),使得lca(u,v) = p,且u,v 距离大于等于W。

双指针+计数问题补集转化

 

POJ1741 Tree(男人八题之一)

给你一棵n 个点的树,树有边权,然后给定一个W,问有多少点对(u, v),使得u,v 的距离<=W。(n<=10^5)

解法同上,我参考了别人的代码,很棒的算法实现!

有很多细节要注意:

几个重要的函数:

GetRoot(int x,int ff) 找子树x的重心,作为“新根”(概念上的根,分治的分界)

GetDis(int x,int ff,int d)处理子树x中节点的dis:到当前子树"根"的距离

Cal(int x,int d) 处理子树x中所有满足dis[u]+dis[v]<=K的点对(路径)数

Work(int x) 分治处理主过程

1、ba[i]=balance(i)切掉i结点后的"平衡值":生成的子树中结点数最多的子树的结点数

ba[]的初值:

ba[rt]=inf或n;

GetRoot时:ba[x]=0,因为后面要取max,否则会T

if(ba[x]<ba[rt]) rt=x;//ba[rt]=ba[x]; 这句不加,使ba[rt]始终=inf或n,不需要重新赋值

2、补集转化的实现:

ans+=Cal(x,0);

R(i,x) if(!vis[e[i].go]) ans-=Cal(e[i].go,e[i].w);

故计数时,函数必须设置参数d!

3、Cal(int x,int d) 中,子树x中节点用cnt重新计数,因为不需要用到原有编号

双指针法计数,由于只要求<=K,这里只需维护一侧,统计以i为端点的路径条数

	for(int i=1,j=cnt;i<j;i++){
		while(dis[i]+dis[j]>K && i<j) j--;//注意while 及i<j限制
		res+=(j-i); 
	}

i为其中一个端点,显然另一合法端点只能为i+1~j,所以个数不是(j-i+1)

4、递归函数设置了ff参数,但由于每次调用时,将当前子树根节点的ff赋值为0,

仍需加vis判断。

if(y==ff||vis[y]) continue;

 

My Code:

int n,rt,ans,total,cnt,ba[N],siz[N];
LL K,dis[N];
bool vis[N];
void GetRoot(int x,int ff) 
{
	siz[x]=1;ba[x]=0;//!!!
	R(i,x){
		int y=e[i].go;
		if(y==ff||vis[y]) continue;
		GetRoot(y,x);
		siz[x]+=siz[y];
		ba[x]=max(ba[x],siz[y]);
	}
	ba[x]=max(ba[x],total-siz[x]);
	if(ba[x]<ba[rt]) rt=x;
}
void GetDis(int x,int ff,LL d)
{
	dis[++cnt]=d;
	R(i,x){
		int y=e[i].go;
		if(y==ff||vis[y]) continue;
		GetDis(y,x,d+e[i].w);
	}
} 
int Cal(int x,LL d)
{
	int res=0;
	cnt=0;
	GetDis(x,0,d);
	sort(dis+1,dis+cnt+1);
	for(int i=1,j=cnt;i<j;i++){
		while(dis[i]+dis[j]>K && i<j) j--;
		res+=(j-i);
	}
	return res;
}
void Work(int x)//递归处理x为根的子树(上一层递归已确定根!) 
{
	ans+=Cal(x,0);//处理的主体 
	vis[x]=true;
	R(i,x){//向下一层递归转移 
		int y=e[i].go;
		if(vis[y]) continue;//不需判断fa[] 
		ans-=Cal(y,e[i].w);//补集转化 
		rt=0;total=siz[y];
		GetRoot(y,0);//找子树的重心(不是当前树的重心) 
		Work(rt);
	}
}
/*****main*****/
	siz[rt]=n;ba[rt]=n;//只是初值 
	total=n;GetRoot(1,0);
	Work(rt);

 

 

POJ2114

十分蠢萌的题,包括题目描述(ahem>_<)

与上面的问题类似,模板题一个:

给你一棵n 个点的树,树有边权,然后给定一个W,问有多少点对(u, v),使得u,v 的距离恰好等于W。(n<=10^5)

bzoj 2599 【IOI2011】Race

给一棵树,每条边有权.求一条路径,权值和等于K,且边的数量最小.(1 <= N <= 2*10^5,1 <= K <= 10^6)

 

Category: 分治 | Tags: 学习笔记 点分治 | Read Count: 295

登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com