蒟蒻求调
查看原帖
蒟蒻求调
251775
galiyuebing楼主2023/11/5 15:37

rt,样例过了,但是只过了一个点,找半天找不出错误

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#define pii pair<int,int>
using namespace std;
const int N=5e4+10;
int n,k;
struct Node{
	int to,next;
}edge[N*2];
int head[N*2],cnt,ans=-1;
int f[N][30],dep[N],D[N];
bool vis[N];

void ini()
{
	for(int i=1;i<N*2;++i){edge[i].next=-1;head[i]=-1;}
	return;
}

void add_edge(int u,int v)
{
	edge[cnt].to=v;
	edge[cnt].next=head[u];
	head[u]=cnt++;
}

void dfs(int u,int fa)
{
	f[u][0]=fa;
	dep[u]=dep[fa]+1;
	for(int i=0;f[u][i];++i)f[u][i+1]=f[f[u][i]][i];
	for(int i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v!=fa)dfs(v,u);
	}
}

void dfss(int u,int fa)
{
	for(int i=head[u];i!=-1;i=edge[i].next)
	{
		int v=edge[i].to;
		if(v!=fa)
		{
			D[u]+=D[v];
			dfss(v,u);
		}
	}
	ans=max(ans,D[u]);
}

int lca(int u,int v)
{
	if(dep[u]<dep[v])swap(u,v);
	for(int i=25;i>=0;--i)if(dep[u]-(1<<i)>=dep[v])u=f[u][i];
	if(u==v)return u;
	for(int i=25;i>=0;--i)if(f[u][i]!=f[v][i]){u=f[u][i];v=f[v][i];}
	return f[u][0];
}

int main()
{ini();
	cin>>n>>k;
	for(int i=1,u,v;i<n;++i)
	{
		scanf("%d%d",&u,&v);
		add_edge(u,v);add_edge(v,u);
	}
	dfs(1,0);
	for(int i=1,u,v;i<=k;++i)
	{
		scanf("%d%d",&u,&v);
		int L=lca(u,v);
		D[u]++;D[v]++;
		D[L]--;D[f[L][0]]--;
	}
	dfss(1,0);
	printf("%d\n",ans);
	return 0;
}



2023/11/5 15:37
加载中...