Submission #1776558

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <set>
const int maxn=1e5+10;
typedef std::pair<int,int> pii;
typedef std::set<int>::iterator tit;
std::set<int> ed[2][maxn];
std::set<pii> todo;
int fa[maxn];
void addedge(int id,int u,int v)
{
    ed[id][u].insert(v);
    ed[id][v].insert(u);
    if(ed[id^1][u].find(v)!=ed[id^1][u].end()) todo.insert(std::make_pair(u,v));
}
void rename(int u,int v)
{
    fa[u]=v;
    for(tit it=ed[0][u].begin();it!=ed[0][u].end();it++)
    {
        ed[0][*it].erase(u);
        addedge(0,v,*it);
    }
    for(tit it=ed[1][u].begin();it!=ed[1][u].end();it++)
    {
        ed[1][*it].erase(u);
        addedge(1,v,*it);
    }
    ed[0][u].clear();
    ed[1][u].clear();
}
int getf(int x)
{
    return fa[x]==x?x:fa[x]=getf(fa[x]);
}
int n;
int read()
{
    char ch=getchar();
    int x=0,f=1;
    while(!isdigit(ch))
    {
        f=(ch=='-'?-f:f);
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f<0?-x:x;
}
int main()
{
    n=read();
    for(int i=1;i<n;i++)
    {
        int u,v;
        u=read();v=read();
        addedge(0,u,v);
    }
    for(int i=1;i<n;i++)
    {
        int u,v;
        u=read();v=read();
        addedge(1,u,v);
    }
    int cnt=0;
    for(int i=1;i<=n;i++) fa[i]=i;
    while(todo.size()>0)
    {
        pii cur=*todo.begin();
        todo.erase(todo.begin());
        cur.first=getf(cur.first);
        cur.second=getf(cur.second);
        if(cur.first==cur.second)continue;
        ed[0][cur.first].erase(cur.second);
        ed[1][cur.first].erase(cur.second);
        ed[0][cur.second].erase(cur.first);
        ed[1][cur.second].erase(cur.first);
        if(ed[0][cur.first].size()+ed[1][cur.first].size()<ed[0][cur.second].size()+ed[1][cur.second].size()) rename(cur.first,cur.second);
        else rename(cur.second,cur.first);
        cnt++;
    }
    if(cnt==n-1)puts("YES");else puts("NO");
    return 0;
}

Submission Info

Judge Result