记录编号	352707	评测结果	AAAAAAAAA
题目名称	暗之链锁	最终得分	100
用户昵称	Metatron	是否通过	通过
代码语言	C++	运行时间	1.160 s
提交时间	2016-11-17 15:46:33	内存使用	10.59 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 100005
#define maxm 100005
struct Edge{
	int to,next;
}a[maxm<<1];
int n,m,l,len,head[maxn],de[maxn],dp[maxn],f[maxn][20];
/*void swap(int& x,int& y){
	int& t=x;x=y;y=t;
}*/
void Insert(int x,int y){
	a[++len].next=head[x];a[len].to=y;head[x]=len;
}
void dfs(int x){
	for(int i=head[x];i!=-1;i=a[i].next){
		int k=a[i].to;
		if(f[x][0]==k)	continue;
		de[k]=de[x]+1;
		f[k][0]=x;
		dfs(k);
	}
}
int LCA(int x,int y){
	if(de[x]<de[y])	swap(x,y);
	for(int j=l-1;j>=0;--j)
		if(de[f[x][j]]>=de[y])
			x=f[x][j];
	if(x==y)	return x;
	for(int j=l-1;j>=0;--j)
		if(f[x][j]!=f[y][j])
			x=f[x][j],y=f[y][j];
	return f[x][0];
}
void DP(int x,int rt){
	for(int i=head[x];i!=-1;i=a[i].next){
		int k=a[i].to;
		if(k==rt)	continue;
		DP(k,x);
		dp[x]+=dp[k];
	}
}	
int main(){
	freopen("yam.in","r",stdin);freopen("yam.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(head,-1,sizeof head);
	for(int i=1;i<n;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		Insert(x,y);
		Insert(y,x);
	}
	dfs(1);f[1][0]=1;
	l=(int)(log(n*1.0)/log(2.0))+1;
	for(int j=1;j<l;++j)
		for(int i=1;i<=n;++i)
			f[i][j]=f[f[i][j-1]][j-1];
	for(int i=1;i<=m;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		dp[x]++;dp[y]++;
		dp[LCA(x,y)]-=2;
	}
	DP(1,0);
	int ans=0;
	for(int i=2;i<=n;++i)
		if(dp[i]==1)	ans++;
		else if(!dp[i])	ans+=m;
	printf("%d\n",ans);
	return 0;
}