6分求助
查看原帖
6分求助
445650
I_never_left楼主2023/3/11 11:48
#include<bits/stdc++.h>
using namespace std;
const int N = 800000 + 5, M = 30 + 5;
int n, K, ans, cnt, p[N], d[N], fa[N][M];
struct Node {
	int head, nxt, to;
}e[N];
void add(int u, int v) {
	e[++ cnt].to = v;
	e[cnt].nxt = e[u].head;
	e[u].head = cnt;
}
void build(int u, int f) {
	d[u] = d[f] + 1;
	fa[u][0] = f;
	for(int i = e[u].head; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == f) continue;
		build(v, u);
	}
}
void Init() {
	for(int j = 1; j <= 30; ++ j)
		for(int i = 1; i <= n; ++ i)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int LCA(int u, int v) {
	if(d[u] < d[v]) swap(u, v);
	for(int i = 30; i >= 0; -- i)
		if(d[fa[u][i]] >= d[v])
			u = fa[u][i];
	if(u == v) return u;
	for(int i = 30; i >= 0; -- i)
		if(fa[u][i] != fa[v][i]) {
			u = fa[u][i];
			v = fa[v][i];
		}
	return fa[u][0];
}
void dfs(int u, int f) {
	for(int i = e[u].head; i ; i = e[i].nxt) {
		int v = e[i].to;
		if(v == f) continue;
		dfs(v, u);
		p[u] += p[v];
	}
	ans = max(ans, p[u]);
}
int main() {
	scanf("%d%d", &n, &K);
	for(int i = 1; i < n; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		add(u, v);
		add(v, u);
	}
	build(1, 0);
	while(K --) {
		int u, v;
		scanf("%d%d", &u, &v);
		int z = LCA(u, v);
		-- p[fa[z][0]];
		-- p[z];
		++ p[u];
		++ p[v];
	}
	dfs(1, 0);
	printf("%d\n", ans);
	return 0;
}
2023/3/11 11:48
加载中...