求助,20分,真不知道哪里问题
查看原帖
求助,20分,真不知道哪里问题
175045
ywjzxx楼主2024/3/9 12:20
#include<iostream>
using namespace std;
const int N = 5e5+5;
int n,k;
struct tnode{
	int v,next;
}edge[N*2];
int head[N*2];
int fa[N][21];
int depth[N];
int point[N];
int cnt;
int ans;
void add(int u,int v){
	edge[++cnt].v = v;
	edge[cnt].next = head[u];
	head[u] = cnt;
}
void dfs(int u,int father){
	depth[u] = depth[father] + 1;
	fa[u][0] = father;
	for(int i = 1 ; i <= 20 ; i ++)
		fa[u][i] = fa[fa[u][i-1]][i-1];
	for(int i = head[u];i;i=edge[i].next){
		int y = edge[i].v;
		if(y != father)
			dfs(y,u);
	}
}
void dfs2(int u,int father){
	for(int i = head[u];i;i=edge[i].next){
		int y = edge[i].v;
		if(y == father) continue;
		dfs2(y,u);
		point[u] += point[y]; 
	}
	ans = max(ans,point[u]);
}
int find(int x,int y){
	if(depth[x] < depth[y]) swap(x,y);
	for(int i = 20 ; i >= 0 ; i --)
		if(depth[fa[x][i]] >= depth[y]){
			x = fa[x][i];
		}
	if(x == y) return x;
	for(int i = 20 ; i >= 0 ; i --){
		if(depth[fa[x][i]] != depth[fa[y][i]]){
			x = fa[x][i];
			y = fa[y][i];
		}
	}
	return fa[x][0];
}
int main(){
	cin >> n >> k;
	for(int i = 1 ; i <= n -1  ; i ++){
		int a,b;
		cin >> a >> b;
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	for(int i = 1 ; i <= k ; i++){
		int a,b;
		cin >> a >> b;
		int father = find(a,b);
		point[a] ++;point[b] ++;
		point[father] -- ; point[fa[father][0]] --;
	}
	dfs2(1,0);
	cout << ans << endl;
	return 0;
}
2024/3/9 12:20
加载中...