暴力dfs: ``` #include<bits/stdc++.h> #define int long long using namespace std; const int N=1e5+10; typedef pair<int,int> pii; vector<int> edge[N]; int n,m; int w[N]; map<pii,int> id; bool dfs(int s,int u,int father,int v) { if(u==v) return true; for(int i=0;i<edge[u].size();i++) { int son=edge[u][i]; if(son==father) continue; if(dfs(s,son,u,v)) { int ID=id[{u,son}]; w[ID]++; return true; } } return false; } signed main() { cin>>n>>m; for(int i=1;i<n;i++) { int x,y; cin>>x>>y; edge[x].push_back(y); edge[y].push_back(x); id[{x,y}]=id[{y,x}]=i; } for(int i=0;i<m;i++) { int x,y; cin>>x>>y; dfs(x,x,-1,y); } int ans=-1; for(int i=n-1;i>=1;i--) { if(w[i]==m) { ans=i; break; } } cout<<ans; return 0; } ``` 正解（树上差分+LCA）： ``` #include<bits/stdc++.h> #define int long long using namespace std; typedef pair<int,int>pii; const int N=1e5+10; int n,m; int w[N]; map<pii,int>id; vector<int>edge[N]; int dep[N],fa[N][20]; void dfs(int u,int father) { dep[u]=dep[father]+1; fa[u][0]=father; for(int i=1;i<=19;i++) { fa[u][i]=fa[fa[u][i-1]][i-1]; } for(int v:edge[u]) { if(v!=father) dfs(v,u); } } int lca(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int i=19;i>=0;i--) { if(dep[fa[u][i]]>=dep[v]) u=fa[u][i]; } if(u==v) return v; for(int i=19;i>=0;i--) { if(fa[u][i]!=fa[v][i]) { u=fa[u][i],v=fa[v][i]; } } return fa[u][0]; } void cal_sum(int u,int father) { for(int i=0;i<edge[u].size();i++) { int son=edge[u][i]; if(son==father) continue; cal_sum(son,u); w[u]+=w[son]; } } signed main() { cin>>n>>m; for(int i=1;i<=n-1;i++) { int x,y;cin>>x>>y; edge[x].push_back(y); edge[y].push_back(x); id[{x,y}]=i; id[{y,x}]=i; } dfs(1,0); for(int i=0;i<m;i++) { int a,b;cin>>a>>b; w[a]++,w[b]++; w[lca(a,b)]-=2; } cal_sum(1,0); int ans=-1; for(int i=1;i<=n;i++) { if(w[i]==m) { int ID=id[{i,fa[i][0]}]; ans=max(ans,ID); } } cout<<ans; return 0; } ```

```c++ #include using namespace std; const int N=1e5+100; int tree_size[N];//tree_size[i]表示以i位根的子树中有多少个需要断开的点 vector >edge[N];//edge[i]存储第i个结点的<邻接点,边的编号> int n,m,ans; void dfs(int u,int father)//从第u个结点开始dfs,其父结点是father { for(const auto &v:edge[u]) { int nex=v.first;//取u的邻接点nex int idx=v.second;//取边(u,nex)的编号idx if(nex==father)continue; dfs(nex,u);//继续向下深搜 tree_size[u] += tree_size[nex];//累加需要断开的结点数量 if(tree_size[nex]==m)//以nex为根的子树,需要断开的结点数量达到了m, //说明该结点恰好将m对边分成树内的m个点和树外的m个点,可以在此处断开 { ans=max(ans,idx);//更新最大的边的编号 } } } int main() { scanf("%d%d",&n,&m); for(int i=1;i ```