WA#8求助
查看原帖
WA#8求助
748859
GeoYZH楼主2025/6/28 10:35

#8怎么也调不过,求帮助

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PLL pair<ll,ll>
const ll N=1e6+10;
ll dep[N];
ll fa[N][30];
vector<ll> g[N];
ll n,a;
ll ans=0;
ll d[N];
void dfs(ll u,ll f){
	for(auto v:g[u]){
		if(v==f){
			continue;
		}
		dep[v]=dep[u]+1;
		fa[v][0]=u;
		for(ll i=1;i<=25;i++){
			fa[v][i]=fa[fa[v][i-1]][i-1];
		}
		dfs(v,u);
	}
}
ll lca(ll u,ll v){
	if(dep[u]<dep[v]){
		swap(u,v);
	}
	for(ll i=25;i>=0;i--){
		if(dep[fa[u][i]]>=dep[v]){
			u=fa[u][i];
		}
	}
	if(u==v){
		return v;
	}
	for(ll i=25;i>=0;i--){
		if(fa[u][i]!=fa[v][i]){
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];
}
void add(ll u,ll v){
	ll root=lca(u,v);
	d[u]++;
	d[v]++;
	d[root]--;
	if(fa[root][0]){
		d[fa[root][0]]--;
	}
}
void s(ll u,ll f){
	for(auto v:g[u]){
		if(v==f){
			continue;
		}
		s(v,u);
		d[u]+=d[v];
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>a;
	for(ll i=1;i<n;i++){
		ll u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	while(a--){
		ll u,v;
		cin>>u>>v;
		add(u,v);
	}
	s(1,0);
	ll u,v;
	cin>>u>>v;
	ll root=lca(u,v);
	while(u!=root){
		if(!d[u]){
			ans++;
			d[u]=1;
		}
		u=fa[u][0];
	}
	while(v!=root){
		if(!d[v]){
			ans++;
			d[v]=1;
		}
		v=fa[v][0];
	}
	if(!d[root]){
		ans++;
	}
	cout<<ans;
	return 0;
}
2025/6/28 10:35
加载中...