Изоморфизм корневых деревьев

n = int(input())
r1, r2 = map(int, input().split())
r1 -= 1
r2 -= 1
G1 = [[] for _ in range(n)]
G2 = [[] for _ in range(n)]

for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G1[a].append(b)
    G1[b].append(a)

for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G2[a].append(b)
    G2[b].append(a)

def build(G, r):
    R = [[] for _ in range(n)]
    used = [0] * n
    Q = [r]
    used[r] = 1
    while Q:
        h = Q.pop()
        for a in G[h]:
            if not used[a]:
                used[a] = 1
                R[h].append(a)
                Q.append(a)
    return R

G1 = build(G1, r1)
G2 = build(G2, r2)

def f(G, r):
    def dfs(h):
        if not G[h]:
            return 1
        D = []
        for a in G[h]:
            D.append(dfs(a))
        D.sort()
        z = 1
        for a in D:
            z = (z * (a + 1)) % (10**9 + 7)
        return z
    return dfs(r)

h1 = f(G1, r1)
h2 = f(G2, r2)

if h1 == h2:
    print("YES")
else:
    print("NO")

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

const int MOD = 1000000007;

vector<vector<int>> build(vector<vector<int>>& G, int r, int n) {
    vector<vector<int>> R(n);
    vector<bool> used(n, false);
    stack<int> Q;
    Q.push(r);
    used[r] = true;
    
    while (!Q.empty()) {
        int h = Q.top();
        Q.pop();
        for (int a : G[h]) {
            if (!used[a]) {
                used[a] = true;
                R[h].push_back(a);
                Q.push(a);
            }
        }
    }
    return R;
}

long long dfs(vector<vector<int>>& G, int h) {
    if (G[h].empty()) {
        return 1;
    }
    vector<long long> D;
    for (int a : G[h]) {
        D.push_back(dfs(G, a));
    }
    sort(D.begin(), D.end());
    long long z = 1;
    for (long long a : D) {
        z = (z * (a + 1)) % MOD;
    }
    return z;
}

long long f(vector<vector<int>>& G, int r) {
    return dfs(G, r);
}

int main() {
    int n;
    cin >> n;
    int r1, r2;
    cin >> r1 >> r2;
    r1--; r2--;
    
    vector<vector<int>> G1(n), G2(n);
    
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G1[a].push_back(b);
        G1[b].push_back(a);
    }
    
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        G2[a].push_back(b);
        G2[b].push_back(a);
    }
    
    vector<vector<int>> R1 = build(G1, r1, n);
    vector<vector<int>> R2 = build(G2, r2, n);
    
    long long h1 = f(R1, r1);
    long long h2 = f(R2, r2);
    
    if (h1 == h2) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    
    return 0;
}