记录编号	322159	评测结果	AAAAAAAAA
题目名称	暗之链锁	最终得分	100
用户昵称	求魔	是否通过	通过
代码语言	C++	运行时间	0.585 s
提交时间	2016-10-14 19:19:22	内存使用	47.75 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#define pa system("pause")
using namespace std;
const int maxn=1000010;
int n,m,head[maxn],len,cha[maxn],ans,cnt,a[maxn];
int size[maxn],id[maxn],pos[maxn],son[maxn],top[maxn],deep[maxn],fa[maxn]; 
void read(int &x)
{
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
}
struct edge{
    int to,next;
}e[maxn<<1];
void insert(int x,int y)
{
    e[++len].to=y;e[len].next=head[x];head[x]=len;
}
void dfs1(int x)
{
	size[x]=1;son[x]=0;
	for(int i=head[x];i;i=e[i].next)
	{
		int k=e[i].to;
		if(!size[k])
		{
			deep[k]=deep[x]+1;fa[k]=x;
			dfs1(k);
			size[x]+=size[k];
			if(size[k]>size[son[x]])son[x]=k;
		}
	}
}
void dfs2(int x,int tp)
{
	id[x]=++cnt;pos[cnt]=x;top[x]=tp;
	if(son[x])dfs2(son[x],tp);
	for(int i=head[x];i;i=e[i].next)
	{
		int k=e[i].to;
		if(k!=fa[x]&&k!=son[x])dfs2(k,k);
	}
}
void add(int x,int y)
{
	int fx=top[x],fy=top[y];
	while(fx!=fy)
	{
		if(deep[fx]<deep[fy]){swap(x,y);swap(fx,fy);}
		 cha[id[fx]]++;cha[id[x]+1]--;
		 x=fa[fx];fx=top[x];
	}
	if(deep[x]>deep[y])swap(x,y);
	if(id[x]+1<=id[y])cha[id[x]+1]++,cha[id[y]+1]--;
}
int main()
{
	freopen("yam.in","r",stdin);
	freopen("yam.out","w",stdout);
    read(n);read(m);
    for(int i=1,x,y;i<n;++i)
    {
        read(x);read(y);
        insert(x,y);insert(y,x);
    }
    dfs1(1);dfs2(1,1);
    for(int i=1,x,y;i<=m;++i)
    {
       read(x);read(y);
        add(x,y);
    }
    for(int i=1;i<=n;++i)a[i]=cha[i]+a[i-1];
    for(int i=2;i<=n;++i)
    {
        if(a[i]==0)ans+=m;
        if(a[i]==1)ans++;
       // cout<<a[i]<<endl;
    }
    printf("%d\n",ans);
}