概要

各木について、子を訪れる順番をすべて試して得られる巡回記録の集合を作り、2 つの集合の共通部分を辞書順に出力します。

考察

ある部屋 \(v\) の巡回記録は、次の形になります。

\[{\tt a} + \text{子部分木の巡回記録を何らかの順番で並べたもの} + {\tt b}\]

例えば、部屋 \(v\) の子が \(c_1, c_2, \dots, c_m\) だとすると、子の訪問順序を任意の順列 \(\pi\) として、

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

という形になります。

葉の場合は子がいないので、巡回記録は必ず "ab" です。

したがって、各頂点について「その部分木から作れる巡回記録の集合」を下から再帰的に求めればよいです。

注意点として、異なる子の訪問順序から同じ文字列ができることがあります。
例えば、根に葉の子が 2 つある場合、どちらの葉を先に訪れても両方の子の記録は "ab" なので、得られる文字列は同じです。

そのため、結果は set で管理して重複を取り除きます。

\(N \leq 10\) と小さいので、子の順列を全探索しても十分間に合います。

アルゴリズム

1. 入力の木は無向辺で与えられるので、部屋 \(1\) を根として DFS し、各頂点の子リストを作る。
2. 関数 generate_records(v) で、頂点 \(v\) を根とする部分木から作れる巡回記録の集合を返す。
   • 子がいない場合、集合 {"ab"} を返す。
   • 子がいる場合、
     1. 各子について再帰的に巡回記録の集合を求める。
     2. 子の並び順をすべての順列で試す。
     3. その順番に従って、各子の巡回記録集合から 1 つずつ選び、連結する。
     4. できた文字列の前後に "a" と "b" を付けて集合に追加する。
3. 高橋君の木、青木君の木それぞれについて巡回記録の集合を求める。
4. 高橋君側の集合を順に見て、青木君側にも含まれるものを答えに追加する。
   • set は辞書順に走査されるため、答えも辞書順になる。

計算量

各頂点 \(v\) の子の数を \(d_v\) とします。
木全体で子の訪問順序を選ぶ方法の数は

\[P = \prod_v d_v!\]

であり、\(\sum_v d_v = N - 1\) なので、\(P \leq (N-1)!\) です。

• 時間計算量: \(O(N^2 P \log(P+1))\)
• 空間計算量: \(O(NP)\)

制約では \(N \leq 10\) なので、最大でもおよそ \(9!\) 程度の全探索で済みます。

実装のポイント

• 入力は無向木なので、まず build_children で根付き木に変換します。

• 巡回記録の重複を除くために set<string> を使います。

• set<string> は辞書順に要素を保持するため、最後に走査するだけで辞書順出力になります。

• C++ の文字順では 'a' < 'b' なので、問題の辞書順と一致します。

  ソースコード

#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;
}

---

この解説は gpt-5.5-xhigh によって生成されました。