Overview

For each tree, we generate the set of traversal records obtained by trying all possible orderings of visiting children, then output the intersection of the two sets in lexicographic order.

Analysis

The traversal record of a room \(v\) takes the following form:

\[{\tt a} + \text{traversal records of child subtrees arranged in some order} + {\tt b}\]

For example, if the children of room \(v\) are \(c_1, c_2, \dots, c_m\), then for any permutation \(\pi\) of the visiting order of children:

\[{\tt a} + R_{c_{\pi_1}} + R_{c_{\pi_2}} + \dots + R_{c_{\pi_m}} + {\tt b}\]

For a leaf node, there are no children, so the traversal record is always "ab".

Therefore, for each vertex, we can recursively compute “the set of traversal records that can be produced from its subtree” from the bottom up.

An important note: different visiting orders of children can produce the same string.
For example, if the root has two leaf children, regardless of which leaf is visited first, both children’s records are "ab", so the resulting string is the same.

For this reason, we manage results using a set to eliminate duplicates.

Since \(N \leq 10\) is small, exhaustively searching all permutations of children is fast enough.

Algorithm

1. Since the input tree is given as undirected edges, perform DFS rooted at room \(1\) to build the children list for each vertex.
2. The function generate_records(v) returns the set of traversal records that can be produced from the subtree rooted at vertex \(v\).
   • If there are no children, return the set {"ab"}.
   • If there are children:
     1. Recursively compute the set of traversal records for each child.
     2. Try all permutations of the children’s ordering.
     3. For each ordering, select one traversal record from each child’s set and concatenate them.
     4. Prepend "a" and append "b" to the resulting string, then add it to the set.
3. Compute the set of traversal records for both Takahashi’s tree and Aoki’s tree.
4. Iterate through Takahashi’s set, and add to the answer any element that is also contained in Aoki’s set.
   • Since a set is traversed in lexicographic order, the answer is also in lexicographic order.

Complexity

Let \(d_v\) be the number of children of each vertex \(v\).
The number of ways to choose the visiting order of children across the entire tree is

\[P = \prod_v d_v!\]

Since \(\sum_v d_v = N - 1\), we have \(P \leq (N-1)!\).

• Time complexity: \(O(N^2 P \log(P+1))\)
• Space complexity: \(O(NP)\)

Under the constraints \(N \leq 10\), the exhaustive search is at most approximately \(9!\) in size.

Implementation Notes

• Since the input is an undirected tree, we first convert it to a rooted tree using build_children.

• We use set<string> to eliminate duplicate traversal records.

• Since set<string> maintains elements in lexicographic order, simply iterating through it at the end gives lexicographic output.

• In C++ character ordering, 'a' < 'b', which matches the lexicographic order defined in the problem.

  Source Code

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

void build_children(int v, int p, const vector<vector<int>>& g, vector<vector<int>>& children) {
    for (int to : g[v]) {
        if (to == p) continue;
        children[v].push_back(to);
        build_children(to, v, g, children);
    }
}

set<string> generate_records(int v, const vector<vector<int>>& children) {
    vector<set<string>> child_records;
    for (int c : children[v]) {
        child_records.push_back(generate_records(c, children));
    }

    int m = child_records.size();
    set<string> res;

    if (m == 0) {
        res.insert("ab");
        return res;
    }

    vector<int> perm(m);
    iota(perm.begin(), perm.end(), 0);

    do {
        vector<string> cur = {""};

        for (int id : perm) {
            vector<string> nxt;
            for (const string& prefix : cur) {
                for (const string& s : child_records[id]) {
                    nxt.push_back(prefix + s);
                }
            }
            cur.swap(nxt);
        }

        for (const string& body : cur) {
            res.insert("a" + body + "b");
        }
    } while (next_permutation(perm.begin(), perm.end()));

    return res;
}

set<string> solve_tree(int N, const vector<vector<int>>& g) {
    vector<vector<int>> children(N);
    build_children(0, -1, g, children);
    return generate_records(0, children);
}

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

    int N;
    cin >> N;

    vector<vector<int>> GA(N), GB(N);

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        GA[u].push_back(v);
        GA[v].push_back(u);
    }

    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        GB[u].push_back(v);
        GB[v].push_back(u);
    }

    set<string> A = solve_tree(N, GA);
    set<string> B = solve_tree(N, GB);

    vector<string> ans;
    for (const string& s : A) {
        if (B.count(s)) ans.push_back(s);
    }

    cout << ans.size() << '\n';
    for (const string& s : ans) {
        cout << s << '\n';
    }

    return 0;
}

This editorial was generated by gpt-5.5-xhigh.