求助,不知道为什么WA了
查看原帖
求助,不知道为什么WA了
438461
liu_chen_hao楼主2022/1/9 16:44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e4+5;

int n,k,x,y,ans,w[N];
int fa[N][20],dep[N];
vector<int> g[N];

void dfs(int u, int fat)
{
	dep[u]=dep[fat]+1;
	fa[u][0]=fat;
	for(int i=1; i<=20; ++i)
		fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=0; i<g[u].size(); ++i)
	{
		int v=g[u][i];
		if(v==fat) continue;
		dfs(v,u);
	}
}
int lca(int x, int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20; i>=0; --i)
		if(dep[fa[x][i]]>=dep[y])
			x=fa[x][i];
	if(x==y) return x;
	for(int i=20; i>=0; --i)
		if(fa[x][i]!=fa[y][i])
			x=fa[x][i],
			y=fa[y][i];
	return fa[x][0];
}
void cal(int u, int fat)
{
	for(int i=0; i<g[u].size(); i++)
	{
		int v=g[u][i];
		if(v==fat) continue;
		if(v==0) break;
		cal(v,u);
		w[u]+=w[v];
	}
	ans=max(ans,w[u]);
}
int main()
{
	scanf("%d%d", &n, &k);
	for(int i=1; i<n; i++)
	{
		scanf("%d%d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1,0);
	while(k--)
	{
		scanf("%d%d", &x, &y);
		int z=lca(x,y);
		++w[x],++w[y];
		--w[z],--w[fa[z][0]];
	}
	cal(1,0);
	printf("%d", ans);

	return 0;
}

2022/1/9 16:44
加载中...