【树上差分+LCA】篮球杯砍树-Toy模板网

这篇具有很好参考价值的文章主要介绍了【树上差分+LCA】篮球杯砍树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

省赛的题现在来补

感觉什么都不会，已经要没了

题意：

【树上差分+LCA】篮球杯砍树

思路：

考虑一条边，两端有两棵子树

有这样的性质：

这条边两端的结点的经过次数==M

因此每加一个点对，都对其路径+1

s[u]==M时，与该点连着的边就是合法边了，统计合法边的最大id就行

Code：文章来源地址https://www.toymoban.com/news/detail-461187.html

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int mxn=3e5+10;
const int mxe=3e5+10;

struct ty{
	int to,next;
}edge[mxe<<2];

struct ty2{
	int u,v,id;
}e[mxe<<2];

int N,M,u,v,tot=0,ans=0;
int head[mxn],F[mxn][33],dep[mxn];
int a[mxn],b[mxn],s[mxn];

void add(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
void G_init(){
	tot=0;
	for(int i=0;i<=N;i++){
		head[i]=-1;
	}
}
void dfs1(int u,int fa){
	dep[u]=dep[fa]+1;
	F[u][0]=fa;
	for(int j=1;j<=30;j++) F[u][j]=F[F[u][j-1]][j-1];
	for(int i=head[u];~i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		dfs1(edge[i].to,u);
	}
}
int lca(int u,int v){
	if(dep[u]<dep[v]) swap(u,v);
	for(int j=30;j>=0;j--){
		if(dep[F[u][j]]>=dep[v]){
			u=F[u][j];
		}
	}
	if(u==v) return u;
	for(int j=30;j>=0;j--){
		if(F[u][j]!=F[v][j]){
			u=F[u][j];
			v=F[v][j];
		}
	}
	return F[u][0];
}
void dfs2(int u,int fa,int id){
	for(int i=head[u];~i;i=edge[i].next){
		if(edge[i].to==fa) continue;
		dfs2(edge[i].to,u,i);
		s[u]+=s[edge[i].to];
	}
	if(s[u]==M) ans=max(ans,id/2+1);
}
void solve(){
	cin>>N>>M;
	G_init();
	for(int i=1;i<=N-1;i++){
		cin>>u>>v;
		add(u,v);
		add(v,u);
		e[i]={u,v,i};
	}
	dfs1(1,0);
	for(int i=1;i<=M;i++){
		cin>>a[i]>>b[i];
		s[a[i]]++;
		s[b[i]]++;
		s[lca(a[i],b[i])]-=2;
	}
	dfs2(1,0,1);
	cout<<ans<<'\n';

}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int __=1;//cin>>__;
	while(__--)solve();return 0;
}

到了这里，关于【树上差分+LCA】篮球杯砍树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！