Submission #1755035

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define fi first
#define se second
#define MP make_pair

int read()
{
    int v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}

const int N = 1e5 + 10;

struct Edge
{
    int nxt, to;
} eg[N << 1];
int head[N], en, n, vis[N];

set<int> E[N];
queue<PII> Q;
map<PII, int> mp;

void setEdge(int u, int v)
{
    eg[++en] = (Edge) {head[u], v};
    head[u] = en;
}

void modify(int u, int v, int p)
{
    if (u > v) swap(u, v);
    mp[MP(u, v)] += p;
}

int query(int u, int v)
{
    if (u > v) swap(u, v);
    return mp[MP(u, v)];
}

int main()
{
    n = read();
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        if (u > v) swap(u, v);
        mp[MP(u, v)]++;
        E[u].insert(v);
        E[v].insert(u);
    }
    for (int i = 1; i < n; i++)
    {
        int u = read(), v = read();
        if (u > v) swap(u, v);
        modify(u, v, 1);
        E[u].insert(v);
        E[v].insert(u);
    }
    for (map<PII, int> :: iterator i = mp.begin(); i != mp.end(); i++)
        if ((*i).se == 2)
            Q.push((*i).fi);
    int cnt = 0;
    while (!Q.empty())
    {
        PII t = Q.front();
        cnt++;
        Q.pop();
        int u = t.fi, v = t.se;
        if (vis[u] || vis[v]) continue;
        vis[v] = 1;
        if (E[u].size() < E[v].size()) swap(u, v);
        E[u].erase(v);
        modify(u, v, -2);
        for (set<int> :: iterator i = E[v].begin(); i != E[v].end(); i++)
        {
            int p = *i;
            if (p == u) continue;
            E[p].erase(v);
            modify(p, u, query(p, v));
            if (query(p, u) == 2) Q.push(MP(p, u));
            modify(p, v, -query(p, v));
            E[p].insert(u);
            E[u].insert(p);
        }
    }
    if (cnt == n - 1) puts("YES"); else puts("NO");
}

Submission Info

Judge Result