思路与算法

一棵有根树的形状由各儿子子树形状的多重集唯一决定。建立全局形状编号器：空多重集对应叶子；每个多重集用固定编号值域上的持久线段树精确表示。叶子存该形状出现次数，内部节点按左右孩子ID全局驻留，相同孩子对一定共用ID。哈希表只是查找完整孩子对，发生哈希碰撞仍比较完整整数键。先后序计算向下分支形状，再换根计算父侧分支形状和每个顶点作根的全树形状。将A全部根形状放入集合。对B每个叶子x，其邻点v的完整邻居多重集中删去一个“单叶形状”，得到B-x以v为根的形状；若属于A的根形状集合，x可删除，按原编号升序找第一个。

正确性说明

对有根树节点数归纳：单叶为空多重集；一般根树同构当且仅当各儿子子树可按形状一一匹配，等价于儿子形状多重集相同。规范化线段树对每个编号保存精确次数，内部ID由完整孩子对唯一确定，因此多重集ID相同当且仅当内容相同，得到无碰撞的精确形状编号。换根时删去某儿子贡献，剩余多重集恰为从该儿子看父侧分支；加上父侧贡献得到当前顶点的完整根形状。删B的叶子仅移除邻点的一个单叶分支，其余结构不变，故上述减少后的根形状准确。无根树同构必使B-x的根v对应A中的某个点；反之若与A某根形状相同，忘记根仍然同构，所以集合判定充要。升序枚举保证最小编号。

复杂度

设n=N，形状编号范围R=2^20。两棵树的子树、父侧分支和全树形状总数少于7n+10，满足固定值域。建树、数组与遍历初始化O(n)，持久多重集每次修改O(log R)，修改次数O(n)，总为期望O(n log R)时间（精确结构哈希索引）和O(n log R)空间。哈希索引表容量2^24，初始化也需O(2^24)时间和空间；此外预留节点容量14000010及形状索引容量，均为题目n≤10^5的显式工程常数，不可忽略其资源。没有递归深树遍历，只有20层值域修改递归。

易错点

无标号同构不能比较原节点编号或只比较度数。相同儿子形状可以多次出现，必须维护次数而非集合。删叶时减的是邻点的单叶分支；不能只比较B叶子的原子树编号。线段树内部驻留比较完整孩子ID，不能把有限模数哈希值直接视为同构证据。全局编号器供A/B共同使用；N=1也应正确处理。

参考代码（C++11）

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
struct Node {
    int l, r;
};
struct Canonical {
    vector<Node> nodes;
    vector<int> table;
    unordered_map<int, int> shapes;
    int shapeCount = 1;
    Canonical() : table(1 << 24, 0) {
        nodes.reserve(14000010);
        nodes.push_back({0, 0});
        shapes.reserve(800000);
        shapes[0] = 1;
    }
    static unsigned long long hash64(unsigned long long x) {
        x ^= x >> 30;
        x *= 0xbf58476d1ce4e5b9ULL;
        x ^= x >> 27;
        x *= 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    int intern(int l, int r) {
        if (!l && !r)
            return 0;
        unsigned long long key = ((unsigned long long)(unsigned int)l << 32) | (unsigned int)r;
        unsigned pos = hash64(key) & (table.size() - 1);
        while (table[pos]) {
            int id = table[pos];
            if (nodes[id].l == l && nodes[id].r == r)
                return id;
            pos = (pos + 1) & (table.size() - 1);
        }
        int id = nodes.size();
        nodes.push_back({l, r});
        table[pos] = id;
        return id;
    }
    int update(int root, int pos, int delta, int level = 19) {
        if (level < 0) {
            int count = -root + delta;
            assert(count >= 0);
            return -count;
        }
        int l = root ? nodes[root].l : 0, r = root ? nodes[root].r : 0;
        if (pos >> level & 1)
            r = update(r, pos, delta, level - 1);
        else
            l = update(l, pos, delta, level - 1);
        return intern(l, r);
    }
    int shape(int root) {
        auto it = shapes.find(root);
        if (it != shapes.end())
            return it->second;
        assert(shapeCount + 1 < (1 << 20));
        return shapes[root] = ++shapeCount;
    }
};
struct Tree {
    int n;
    vector<vector<int>> g;
    vector<int> parent, order, sub, multi, up, full, rootShape;
    Tree(int n) : n(n), g(n), parent(n, -1), sub(n), multi(n), up(n), full(n), rootShape(n) {
    }
    void read() {
        for (int i = 1, a, b; i < n; i++) {
            cin >> a >> b;
            --a;
            --b;
            g[a].push_back(b);
            g[b].push_back(a);
        }
    }
    void process(Canonical &c) {
        order.push_back(0);
        parent[0] = 0;
        for (size_t k = 0; k < order.size(); k++) {
            int v = order[k];
            for (int u : g[v])
                if (u != parent[v])
                    parent[u] = v, order.push_back(u);
        }
        for (int k = n - 1; k >= 0; k--) {
            int v = order[k], r = 0;
            for (int u : g[v])
                if (u != parent[v])
                    r = c.update(r, sub[u], 1);
            multi[v] = r;
            sub[v] = c.shape(r);
        }
        for (int v : order) {
            int r = multi[v];
            if (v)
                r = c.update(r, up[v], 1);
            full[v] = r;
            rootShape[v] = c.shape(r);
            for (int u : g[v])
                if (u != parent[v])
                    up[u] = c.shape(c.update(r, sub[u], -1));
        }
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n))
        return 0;
    Tree a(n), b(n + 1);
    a.read();
    b.read();
    Canonical c;
    a.process(c);
    b.process(c);
    unordered_set<int> target(a.rootShape.begin(), a.rootShape.end());
    for (int i = 0; i <= n; i++)
        if (b.g[i].size() == 1) {
            int neighbor = b.g[i][0];
            int reduced = c.update(b.full[neighbor], 1, -1);
            int shape = c.shape(reduced);
            if (target.count(shape)) {
                cout << i + 1 << '\n';
                return 0;
            }
        }
    cout << "-1\n";
}