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