Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

雁过留声——树形dp

Posted by fanhqme at 2009-11-28 11:03:58 on Problem 3417
discuss区说有一篇解题报告挺难看懂的...我就贡献一个比较容易理解的吧。
传说这题和rmq之类的有关...?...我没有用它。

首先,一个很淳朴的思想:枚举断开哪条原边,然后统计有多少新边横跨在了
被分开的那个子树和其余部分之间。怎么统计呢?
使用一个判断一个点是否在一个子树中的常用工具:先序遍历标号。
先序遍历标号的一个性质:一个子树的所有节点的标号必组成一个连续区间。
例,
1
|\
| \
|\ \
| \ \
2 *3 6
   |\
  *4*5
则带*号的子树的节点的标号集合就是[3,5],
设在dfs的时候,每个点入栈的顺序是who[i],每个点是第id[i]个入栈的。
这样,一个以x为根的子树的所有的节点的标号必然都在区间[id[x],right[x]]中,其中,
right[x]=
x|x is a leaf
min(right[a son of x])|x isn't a leaf

下面,就是统计一个子树中,由内部连向外部的边的数量。
一个显而易见的方法:用平衡树维护每个子树连边的集合。
对边<a,b>,实际上由于限定a在子树中,我们只关心b的值。

基本算法出炉了:
先序遍历并标号
令set[x]={id[y]|<x,y> is a new edge}
从根递归向下访问每个节点x:
计算以x为根的子树的节点的标号范围:right[x]=min{right[a son of x]};
计算由内部连出的边的集合:set[x]=set[x]∪set[a son of x];
统计set[x]中不在[id[x],right[x]]中的数的个数cnt[x],
即由内部连到外部的边数;
如果边数=1,答案+1,如果边数=0,答案+M

一个痛苦的技术问题:如何快速维护可并的能够统计某一区间内个数的集合?
我的解决方案:
其实这题没有必要真正知道cnt[x]的具体大小,只要知道cnt[x]是否为0,或1
就行了!于是,每个set[x]只记录4个数,分别是集合中最大的两个数,和集合
中最小的两个数。

问题至此解决。

关键代码:
struct record{//用于维护集合
	int d[4],c;//只记录4个数!
	record(){d[0]=d[1]=d[2]=d[3]=-1;c=0;}
	void ins(int x){if (x==-1)return;
		if (c<4){
			for (int i=c;i>=0;i--)
				if (i && d[i-1]>x)d[i]=d[i-1];
				else{
					d[i]=x;break;
				}
			c++;
		}else{
			if (x<=d[0]){
				d[1]=d[0];d[0]=x;
			}else if (x<d[1]){
				d[1]=x;
			}else if (x>=d[3]){
				d[2]=d[3];d[3]=x;
			}else if (x>d[2]){
				d[2]=x;
			}
		}
	}
	void add(record x){
		for (int i=0;i<x.c;i++)ins(x.d[i]);
	}
};
struct edge{
	int e;
	edge *next;
}epool[NMax<<3],*etop;//用链表保存边
void dfs0(int x){//先序遍历并标号
	who[id[x]=cnt++]=x;//很有趣的写法:)
	for (edge *p=E[x];p;p=p->next)if (id[p->e]==-1)
		dfs0(p->e);
}
void dfs1(int x){
	right[x]=id[x];
	for (edge *p=E2[x];p;p=p->next)set[x].ins(id[p->e]);
	for (edge *p=E[x];p;p=p->next){
		if (right[x]<right[p->e])right[x]=right[p->e];
		set[x].add(set[p->e]);
	}
        //以上代码计算set[x]和right[x],即从内部连出的边的集合和以x为根的子树的节点的标号范围
	int cnt;
	cnt=0;
	for (int i=0;i<set[x].c;i++){
		if (set[x].d[i]<id[x] || set[x].d[i]>right[x])cnt++;
	}
	if (cnt==0)ret+=M;
	if (cnt==1)ret++;
}
for (int i=N-1;i>0;i--)dfs1(who[i]);//非递归的简单方案:从后往前沿着先序标号访问

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator