不断删除重边，然后将两个点的边集启发式合并（要考虑到两棵树），合并时发现重边就加入队列，最后判断是否全部删完即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 100005 4 set<int>s[N]; 5 map<int,int>mat[N]; 6 queue<pair<int,int> >q; 7 int n,x,y,ans,f[N]; 8 int find(int k){ 9 if (k==f[k])return k; 10 return f[k]=find(f[k]); 11 } 12 void add(int x,int y){ 13 s[x].insert(y); 14 s[y].insert(x); 15 if (x>y)swap(x,y); 16 if (++mat[x][y]==2){ 17 q.push(make_pair(x,y)); 18 mat[x][y]=0; 19 } 20 } 21 void merge(int x,int y){ 22 if (s[x].size()>s[y].size())swap(x,y); 23 f[x]=y; 24 for(set<int>::iterator it=s[x].begin();it!=s[x].end();it++){ 25 int z=find(*it); 26 if (y==z)continue; 27 add(y,z); 28 s[z].erase(x); 29 } 30 s[x].clear(); 31 } 32 int main(){ 33 scanf("%d",&n); 34 for(int i=1;i<=n;i++)f[i]=i; 35 for(int i=1;i<2*n-1;i++){ 36 scanf("%d%d",&x,&y); 37 add(x,y); 38 } 39 while (!q.empty()){ 40 ans++; 41 merge(find(q.front().first),find(q.front().second)); 42 q.pop(); 43 } 44 if (ans==n-1)printf("YES"); 45 else printf("NO"); 46 }