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

港控/mmm° 2024-03-16 09:29 40阅读 0赞

**省赛的题现在来补**

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

题意：

![1ffcc3d937d549809ffd88f0082c96cc.png][]

思路：

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

有这样的性质：

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

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

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

Code：

#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;
    }

[1ffcc3d937d549809ffd88f0082c96cc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/025d97bad0fd4318a3c25afa18483f95.png