lessons/参考实现/06-最小与最大生成树/AtCoder-agc014_e.cpp

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    vector<int> parent;
    explicit DSU(int n) : parent(n) { iota(parent.begin(), parent.end(), 0); }
    int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<unordered_map<int, int>> adjacent(n);
    auto add = [&](int u, int v, int bit) {
        adjacent[u][v] |= bit;
        adjacent[v][u] |= bit;
    };
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        add(--u, --v, 1);
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        add(--u, --v, 2);
    }

    queue<pair<int, int>> ready;
    for (int u = 0; u < n; ++u) {
        for (auto [v, mask] : adjacent[u]) {
            if (u < v && mask == 3) ready.push({u, v});
        }
    }

    DSU dsu(n);
    int components = n;
    while (!ready.empty()) {
        auto [raw_u, raw_v] = ready.front();
        ready.pop();
        int u = dsu.find(raw_u), v = dsu.find(raw_v);
        if (u == v) continue;
        auto it = adjacent[u].find(v);
        if (it == adjacent[u].end() || it->second != 3) continue;
        if (adjacent[u].size() < adjacent[v].size()) swap(u, v);

        adjacent[u].erase(v);
        adjacent[v].erase(u);
        vector<pair<int, int>> moved(adjacent[v].begin(), adjacent[v].end());
        for (auto [raw_to, mask] : moved) {
            int to = dsu.find(raw_to);
            if (to == u || to == v) continue;
            adjacent[to].erase(v);
            int merged_mask = mask;
            auto old = adjacent[u].find(to);
            if (old != adjacent[u].end()) merged_mask |= old->second;
            adjacent[u][to] = merged_mask;
            adjacent[to][u] = merged_mask;
            if (merged_mask == 3) ready.push({u, to});
        }
        adjacent[v].clear();
        dsu.parent[v] = u;
        --components;
    }
    cout << (components == 1 ? "YES\n" : "NO\n");
    return 0;
}