悬棺求条
查看原帖
悬棺求条
1067380
juruo_zhuyl楼主2025/2/5 20:58
#include<bits/stdc++.h>
using namespace std;

int n, k, a[50010], ans[50010], dist[50010], fa[50010][14];
vector<int> v[50010];

inline void dfs(int p, int f){
	fa[p][0] = f;
	dist[p] = dist[f] + 1;
	for(int i = 1; i <= 13; i++){
		fa[p][i] = fa[fa[p][i - 1]][i - 1];
	}	
	for(auto i : v[p]){
		if(i != f){
			dfs(i, p);
		}
	}
}

inline void dfs1(int p){
	ans[p] = a[p];
	for(auto i : v[p]){
		if(ans[i] == 0){
			dfs1(i);
			ans[p] += ans[i];
		}
	}
}

int __lca(int a, int b){
	int d = 0;
	if(dist[a] < dist[b]){
		swap(a, b);
	}
	if(dist[a] != dist[b]){
		d = dist[a] - dist[b];
	}
	for(int i = 0; i <= 13; i++){
		if((d >> i) & 1){
			a = fa[a][i];
		}
	}
	if(a == b){
		return a;
	}
	for(int i = 13; i >= 0; i--){
		if(fa[a][i] != fa[b][i]){
			a = fa[a][i];
			b = fa[b][i];
		}
	}
	return fa[a][0];
}

int main(){
	scanf("%d%d", &n, &k);
	for(int i = 1; i < n; i++){
		int x, y;
		scanf("%d%d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dist[1] = 1;
	dfs(1, 0);
	while(k--){
		int u, v;
		scanf("%d%d", &u, &v);
		int o = __lca(u, v);
		a[u]++;
		a[v]++;
		a[o]--;
		a[fa[o][0]]--;
	}
	dfs1(1);
	int ma = 0;
	for(int i = 1; i <= n; i++){
		ma = max(ma, ans[i]);
	}
	printf("%d\n", ma);
}

MLE

2025/2/5 20:58
加载中...