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

好方法!

Posted by yc5_yc at 2012-11-08 07:39:38 on Problem 3417
In Reply To:雁过留声——树形dp Posted by:fanhqme at 2009-11-28 11:03:58
> 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