记录编号	428580	评测结果	AAAAAAAAA
题目名称	暗之链锁	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	0.427 s
提交时间	2017-07-25 20:50:35	内存使用	4.99 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
inline int read(){
	int sum(0);
	char ch(getchar());
	while(ch<'0'||ch>'9')
		ch=getchar();
	while(ch>='0'&&ch<='9'){
		sum=sum*10+ch-'0';
		ch=getchar();
	}
	return sum;
}
int n,m;
struct edge{
	int s,e,n;
}a[200001];
int pre[100001],tot;
inline void insert(int s,int e){
	a[++tot].s=s;
	a[tot].e=e;
	a[tot].n=pre[s];
	pre[s]=tot;
}
int fa[100001],dep[100001],size[100001],son[100001];
inline void dfs1(int u){
	son[u]=0;
	for(int i=pre[u];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(e!=fa[u]){
			fa[e]=u;
			dep[e]=dep[u]+1;
			dfs1(e);
			size[u]+=size[e];
			if(size[e]>size[son[u]])
				son[u]=0;
		}
	}
}
int cnt;
int r[100001];
int top[100001],id[100001],pos[100001];
inline void dfs2(int u,int rt){
	top[u]=rt;
	id[u]=++cnt;
	pos[cnt]=u;
	if(son[u])
		dfs2(son[u],rt);
	for(int i=pre[u];i!=-1;i=a[i].n){
		int e(a[i].e);
		if(e!=fa[u]&&e!=son[u])
			dfs2(e,e);
	}
	r[u]=cnt;
}
int sum[100001];
inline int lowbit(int x){
	return x&-x;
}
inline void update(int pos,int c){
	while(pos<=n){
		sum[pos]+=c;
		pos+=lowbit(pos);
	}
}
inline int su(int pos){
	int ret(0);
	while(pos){
		ret+=sum[pos];
		pos-=lowbit(pos);
	}
	return ret;
}
inline int query(int l,int r){
	return su(r)-su(l-1);
}
inline void swp(int &a,int &b){
	a^=b;
	b^=a;
	a^=b;
}
inline int LCA(int x,int y){
	while(top[x]^top[y]){
		if(dep[top[x]]<dep[top[y]])
			swp(x,y);
		x=fa[top[x]];
	}
	return dep[x]<dep[y]?x:y;
}
inline void change(int x,int y){
	int lca(LCA(x,y));
	update(id[lca],-2);
	update(id[x],1);
	update(id[y],1);
}
inline int Q(int x){
	return query(id[x],r[x]);
}
typedef long long L;
L ans(0);
inline L get(int x){
	if(x==0)
		return m;
	if(x==1)
		return 1;
	else
		return 0;
}
inline int gg(){
	freopen("yam.in","r",stdin);
	freopen("yam.out","w",stdout);
	memset(pre,-1,sizeof(pre));
	n=read(),m=read();
	for(int i=1;i<n;i++){
		int x(read()),y(read());
		insert(x,y);
		insert(y,x);
	}
	dfs1(1);
	dfs2(1,1);
	for(int i=1;i<=m;i++){
		int x(read()),y(read());
		change(x,y);
	}
	for(int i=2;i<=n;i++){
		int ret(Q(i));
		ans+=get(ret);
	}
	printf("%d",ans);
}
int K(gg());
int main(){;}