玄关!!13pts求调 #1 #6 AC
查看原帖
玄关!!13pts求调 #1 #6 AC
684285
Makerlike楼主2024/7/5 00:49
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+10;
#define int long long
int n,k;
struct Edge{
	int v,nxt;
}e[N];
int hd[N],tt=-1;
int lg[N],dep[N],f[N][20];
int p[N],ans=0;
void init(){
	memset(hd,-1,sizeof(hd));
	for(int i=1;i<=n;i++){
		lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	}
}
void add(int x,int y){
	e[++tt].v=y;
	e[tt].nxt=hd[x];
	hd[x]=tt;
}
void dfs(int u,int fa){
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<=lg[dep[u]];i++){
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int i=hd[u];~i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa)
			continue;
		dfs(v,u);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])
		swap(x,y);
	while(dep[x]>dep[y])
		x=f[x][lg[dep[x]-dep[y]]-1];
	if(x==y);
		return x;
	for(int i=lg[dep[x]]-1;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
void getsum(int u,int fa){
	for(int i=hd[u];~i;i=e[i].nxt){
		int v=e[i].v;
		if(v==fa)
			continue;
		getsum(v,u);
		p[u]+=p[v];
	}
	ans=max(ans,p[u]);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k;
	init();
	for(int i=1;i<n;i++){
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	while(k--){
		int x,y;
		cin>>x>>y;
		int t=lca(x,y);
		p[x]++;
		p[y]++;
		p[t]--;
		p[f[t][0]]--;
	}
	getsum(1,0);
	cout<<ans;
	return 0;
}
2024/7/5 00:49
加载中...