6pts + WA 求调
查看原帖
6pts + WA 求调
561313
orange_dusk楼主2024/9/17 22:31
#include<bits/stdc++.h>
using namespace std;
int n,m,ans; 
vector<int> V[100001];
int v[100001],d[100001];
int fa[100001];
int F[100001][30];
void dfs1(int u,int f)
{
	fa[u]=f;
	d[u]=d[f]+1;
	F[u][0]=f;
	for(int i=0;i<V[u].size();i++)
	{
		int v=V[u][i];
		if(v==f)
			continue;
		dfs1(v,u);
	}
}
void dfs(int u,int f)
{
	for(int i=0;i<V[u].size();i++)
	{
		int v1=V[u][i];
		if(v1==f)
			continue;
		dfs(v1,u);
		v[u]+=v[v1];
	}
}
void work()
{
	for(int i=1;i<=20;i++)
		for(int j=1;j<=n;j++)
			if(F[i][j-1])
				F[i][j]=F[F[i][j-1]][j-1];
}
int lca(int u,int v)
{
	if(d[u]>d[v])
		swap(u,v);
	for(int i=20;i>=0;i--)
		if(d[v]-(1<<i)>=d[u])
			v=F[v][i];
	if(u==v)
		return u;
	for(int i=20;i>=0;i--)
		if(F[v][i]!=F[u][i])
			v=F[v][i],u=F[u][i];
	return fa[v];
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		V[u].push_back(v);
		V[v].push_back(u);
	}
	dfs1(1,0);
	work();
	for(int i=1;i<=m;i++)
	{
		int u,v1;
		cin>>u>>v1;
		int L=lca(u,v1);
		v[L]--,v[fa[L]]--;
		v[u]++,v[v1]++;
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
		ans=max(ans,v[i]);
	cout<<ans<<endl;
 	return 0;
}
2024/9/17 22:31
加载中...