Изоморфизм деревьев

from collections import deque

def find_centers(tree, n):
    if n == 1:
        return [0]
    
    deg = [0] * n
    leaves = deque()
    
    for u in range(n):
        deg[u] = len(tree[u])
        if deg[u] == 1:
            leaves.append(u)
    
    rem = n
    while rem > 2:
        for _ in range(len(leaves)):
            leaf = leaves.popleft()
            for nb in tree[leaf]:
                deg[nb] -= 1
                if deg[nb] == 1:
                    leaves.append(nb)
            rem -= 1
    
    return list(leaves)

def encode(tree, node, parent):
    if len(tree[node]) == 1 and parent != -1:
        return "01"
    
    codes = []
    for nb in tree[node]:
        if nb != parent:
            codes.append(encode(tree, nb, node))
    
    codes.sort()
    return "0" + "".join(codes) + "1"

def are_isomorphic(t1, t2, n):
    c1 = find_centers(t1, n)
    c2 = find_centers(t2, n)
    
    if len(c1) != len(c2):
        return False
    
    codes1 = set()
    for c in c1:
        codes1.add(encode(t1, c, -1))
    
    for c in c2:
        if encode(t2, c, -1) in codes1:
            return True
    
    return False

n = int(input())
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)

if are_isomorphic(G1, G2, n):
    print("Yes")
else:
    print("No")

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

vector<int> find_centers(const vector<vector<int>>& tree, int n) {
    if (n == 1) return {0};
    
    vector<int> deg(n);
    queue<int> leaves;
    
    for (int u = 0; u < n; u++) {
        deg[u] = tree[u].size();
        if (deg[u] == 1) leaves.push(u);
    }
    
    int rem = n;
    while (rem > 2) {
        int leaves_count = leaves.size();
        for (int i = 0; i < leaves_count; i++) {
            int leaf = leaves.front();
            leaves.pop();
            for (int nb : tree[leaf]) {
                deg[nb]--;
                if (deg[nb] == 1) leaves.push(nb);
            }
            rem--;
        }
    }
    
    vector<int> result;
    while (!leaves.empty()) {
        result.push_back(leaves.front());
        leaves.pop();
    }
    return result;
}

string encode(const vector<vector<int>>& tree, int node, int parent) {
    if (tree[node].size() == 1 && parent != -1) return "01";
    
    vector<string> codes;
    for (int nb : tree[node]) {
        if (nb != parent) {
            codes.push_back(encode(tree, nb, node));
        }
    }
    
    sort(codes.begin(), codes.end());
    string result = "0";
    for (const string& code : codes) {
        result += code;
    }
    result += "1";
    return result;
}

bool are_isomorphic(const vector<vector<int>>& t1,
                    const vector<vector<int>>& t2, int n) {
    vector<int> c1 = find_centers(t1, n);
    vector<int> c2 = find_centers(t2, n);
    
    if (c1.size() != c2.size()) return false;
    
    set<string> codes1;
    for (int c : c1) {
        codes1.insert(encode(t1, c, -1));
    }
    
    for (int c : c2) {
        if (codes1.find(encode(t2, c, -1)) != codes1.end()) {
            return true;
        }
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    
    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);
    }
    
    if (are_isomorphic(G1, G2, n)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}