省赛的题现在来补

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

题意：

思路：

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

有这样的性质：

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

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

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

Code：

#include <bits/stdc++.h>#define int long longusing 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;
}