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]);//非递归的简单方案：从后往前沿着先序标号访问

• RDFZ的啊。。。 (2314) iserlohn 2009-11-28 11:09:12
• Re:雁过留声——树形dp (22) prowind 2010-03-04 22:24:00
• 好方法！ (2314) yc5_yc 2012-11-08 07:39:38