RE 0pts求调
查看原帖
RE 0pts求调
742017
zhangxiao666楼主2024/7/25 18:25
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int n, k, ans;
vector<int> e[N];
array<int, N> sum, dep;
array<array<int, 25>, N> f;

void Add(int x, int y)
{
	e[x].push_back(y);
	e[y].push_back(x);
}

void Dfs(int u, int fa)
{
	dep[u] = dep[fa] + 1;
	f[u][0] = fa;
	for (int i = 1; i <= 20; i++) 
		f[u][i] = f[f[u][i - 1]][i - 1];
	for (int v : e[u])
	{
		if (v == fa)
			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[f[x][i]] >= dep[y])
			x = f[x][i];
	}
	if (x == y)
		return x;
	for (int i = 20; i >= 0; i--)
	{
		if (f[x][i] != f[y][i])
			x = f[x][i], y = f[y][i];
	}
	return f[x][0];
}

int Add_Tag(int x, int y)
{
	int lca = Lca(x, y);
	sum[x]++, sum[y]++;
	sum[lca]--;
	sum[f[lca][0]]--;
}

void Dfs_Ans(int u, int fa)
{
	for (int v : e[u])
	{
		if (v == fa)
			continue;
		Dfs_Ans(v, u);
		sum[u] += sum[v];
	}
	ans = max(ans, sum[u]);
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i < n; i++)
	{
		int x, y; cin >> x >> y;
		Add(x, y);
	}
	Dfs(1, 0);
	while (k--)
	{
		int s, t; cin >> s >> t;
		Add_Tag(s, t);
	}
	Dfs_Ans(1, 0);
	cout << ans << "\n";
	return 0;
}

2024/7/25 18:25
加载中...