求助!
查看原帖
求助!
490223
Tyh_2楼主2021/5/25 20:56
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e4+5;
vector<int>v[N];
int val[N],lg[N],fa[N][50],dep[N];
int n,q,maxi=0;
void dfs(int cur,int f,int d){
	dep[cur]=d;
	fa[cur][0]=f;
	for (int i = 1;i <= 30;i++)fa[cur][i]=fa[fa[cur][i-1]][i-1];
	for(int i=0;i<v[cur].size();i++){
		int son=v[cur][i];
		if(son!=f)dfs(son,cur,d+1);
	}
	return;
}
int lca(int f,int t){
	if (dep[f]<dep[t])swap(f,t); 
	while (dep[f] != dep[t])f=fa[f][lg[dep[f]-dep[t]]];
	if(f==t)return f;
	for(int i=20;i>0;i--){
		if(fa[f][i]!=fa[t][i]){
			f=fa[f][i];
			t=fa[t][i];
		}
	}
	return fa[f][0];
}
void ap(int f,int t){
	val[f]++;val[t]++;
	int L=lca(f,t);
	val[L]--;val[fa[L][0]]--;
	return;
}
void get_max(int cur){
	for(int i=0;i<v[cur].size();i++){
		int son=v[cur][i];
		if(son!=fa[cur][0]){
			get_max(son);
			val[cur]+=val[son];
		}
	}
	maxi=max(maxi,val[cur]);
	return;
}
signed main(){
	cin>>n>>q;
	lg[0]=-1;
	for(int i=1;i<N;i++)lg[i]=lg[i>>1]+1;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	dfs(1,0,1);
	while(q--){
		int a,b;
		cin>>a>>b;
		ap(a,b);
	}
	v[0].push_back(1);
	get_max(0); 
	cout<<maxi;
	return 0;
}


2021/5/25 20:56
加载中...