13pts求调,只过了1和8两个点
查看原帖
13pts求调,只过了1和8两个点
1109444
spdf_楼主2023/11/28 21:21
#include<bits/stdc++.h>
#define maxn 50010
using namespace std;

int n,m,ans=0;
int lg[maxn];

struct edge{
	int to,nxt;
}e[maxn<<2];
int head[maxn<<2];
int tot=0;

void add(int st,int ed)
{
	e[++tot].nxt=head[st];
	e[tot].to=ed;
	head[st]=tot;
}

int dep[maxn],fa[maxn][30];

void dfs(int now,int fat)
{
	dep[now]=dep[fat]+1,fa[now][0]=fat;
	
	for(int i=head[now];i;i=e[i].nxt)
	{	
		for(int i=1;i<=lg[dep[now]];i++)
		{
			fa[now][i]=fa[fa[now][i-1]][i-1];
		}
	}
	
	for(int i=head[now];i;i=e[i].nxt)
	{
		if(e[i].to!=fat)dfs(e[i].to,now);	
	}	
}

int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	while(dep[x]>dep[y])x=fa[x][lg[dep[x]-dep[y]]-1];
	if(x==y)return x;
	
	for(int k=lg[dep[x]]-1;k>=0;k--)
	{
		if(fa[x][0]!=fa[y][0])x=fa[x][k],y=fa[y][k];
	}
	return fa[x][0];
}

int power[maxn<<1];

void get(int now,int fat)
{
	for(int i=head[now];i;i=e[i].nxt)
	{
		if(e[i].to==fat)continue;
		get(e[i].to,now);
		power[now]+=power[e[i].to];
	}
	
	ans=max(power[now],ans);
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	
	for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	
	dfs(1,0);
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		int a=lca(x,y);
		++power[x],++power[y],--power[a],--power[fa[a][0]];	
	} 
	get(1,0);
	cout<<ans;
	return 0;
}
2023/11/28 21:21
加载中...