蓝桥杯2023年第十四届省赛真题-砍树 LCA+树上差分

解题思路:我们先把 ai 和 bi 之间的路进行差分处理，然后遍历还原，最后对几条边进行遍历，如果它被 m 条路径覆盖了，则统计，没有任何满足的边，就输出 −1。
注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define N 100005
ll n,m;
struct node{
	ll x,y;//y为边的编号 
}; 
vector<node> e[N];
ll fa[N],top[N],son[N],dep[N],sz[N];
ll tp[N]; 
void dfs1(ll u,ll f){
	fa[u]=f,dep[u]=dep[f]+1,sz[u]=1;
	for(node v:e[u]){
		if(v.x==f)continue;
		dfs1(v.x,u);
		sz[u]+=sz[v.x];
		if(sz[son[u]]<sz[v.x])son[u]=v.x;
	}
} 
void dfs2(ll u,ll t){
	top[u]=t;
	if(!son[u])return;
	dfs2(son[u],t);
	for(node v:e[u]){
		if(v.x==fa[u]||v.x==son[u])continue;
		dfs2(v.x,v.x);
	}
}
ll lca(ll u,ll v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]])swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
void dfs(ll u){
	for(node v:e[u]){
		if(v.x==fa[u])continue;
		dfs(v.x);
		tp[u]+=tp[v.x];
	}
}
int main(){
	cin>>n>>m;
	for(ll i=1;i<n;i++){
		ll x,y;cin>>x>>y;
		e[x].push_back({y,i});
		e[y].push_back({x,i});
	}
	dfs1(1,0),dfs2(1,1);
	for(ll i=1;i<=m;i++){
		ll a,b;cin>>a>>b;
		tp[a]++,tp[b]++;//树上边差分
		tp[lca(a,b)]-=2;
	}
	dfs(1);//tp[i]还原后即为记录i与fa[i]相连那条边的权值
	ll ans=-100;
	for(ll i=1;i<=n;i++){
		if(tp[i]==m){//若权值等于m则m组数据都经过这条边 
			for(node v:e[i]){//查找这条边的编号 
				if(v.x==fa[i]){
					ans=max(ans,v.y);
				}
			} 
		} 
	}
	if(ans==-100)cout<<-1<<endl; 
	else cout<<ans<<endl;
	return 0;
}