记录编号	559496	评测结果	AAAAAAAAA
题目名称	暗之链锁	最终得分	100
用户昵称	tat	是否通过	通过
代码语言	C++	运行时间	1.669 s
提交时间	2021-03-12 21:00:39	内存使用	46.88 MiB

#include <bits/stdc++.h>
using namespace std;
int d[200001]={0},n,m,t,val[200001]={0},f[200001][50]={0},da[200001]={0},v[200001]={0};
//da[i]是以i为根的节点数的和 
vector<int>ed[200001];
int ans=0;
//进阶指南p380原题，名字好中二wwww
//要用到的知识：树上差分 ，lca
//树上边差分： 对于任何一条非树边x-y val[x]++ val[y]-- val[lca(x,y)]-=2 
int lca(int x, int y){
	if(d[x]<d[y]){
		swap(x,y);//让x做更深的点 
	}
	for(int i=t;i>=0;i--){
		int tmp=f[x][i];
		if(d[tmp]>=d[y]){
			x=tmp;
		} 
	} 
	if(x==y){
		return x; //说明y就是他们的公共祖先
	}
	for(int i=t;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	} 
	return f[x][0];
}
int bfs(int x){
	queue<int> q;
	d[x]=1;
	q.push(x);
	while(!q.empty()){
		int y=q.front();
		q.pop();
		for(int i=0;i<ed[y].size();i++){
			int to=ed[y][i];
			if(!d[to]){
				d[to]=d[y]+1;
				q.push(to);
				f[to][0]=y;
				for(int j=1;j<=t;j++){
					f[to][j]=f[f[to][j-1]][j-1];//dp求to 的2^N的祖先 
				}
			}
		}
	}	
}
void dfs(int x){
	da[x]=val[x];
	for(int i=0;i<ed[x].size();i++){
		int to=ed[x][i];
		if(!v[to]){
			v[to]=1;
			dfs(to);
			da[x]+=da[to];
		}
	}  
	//cout<<da[x]<<' ';
	if(da[x]==1)ans+=1;
	if(da[x]==0)ans+=m;
}
int main(int argc, char** argv) {
	freopen("yam.in","r",stdin);
	freopen("yam.out","w",stdout);
	
	cin>>n>>m;
	t=(int)(log(n)/log(2))+1;
	for(int i=0;i<=t;i++){
		f[1][i]=1;	
	} 
	for(int i=1;i<=n-1;i++){
		int a,b;
		cin>>a>>b;
		if(a==b)continue;
		ed[a].push_back(b);
		ed[b].push_back(a);
	}
	bfs(1);
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		//ed[a].push_back(b);
		//ed[b].push_back(a);
		val[a]++;
		val[b]++;
		int c=lca(a,b);
		//cout<<c<<' ' ; 
		val[c]=val[c]-2;
	}
	v[1]=1;
	dfs(1);
	cout<<ans-m;
	return 0;
}