概要

各木について「子を訪れる順番を自由に変えたときに作れる巡回記録（a/b 文字列）」を全列挙し、最後に 2 つの集合の共通部分を辞書順で出力する問題です。
制約 \(N \le 10\) と小さいため、部分木ごとに作れる文字列集合を再帰的に構築すれば間に合います。

考察

この巡回記録は、各頂点 \(v\) で必ず

• 入るときに a
• 子を順に処理
• 出るときに b

という形です。
つまり、頂点 \(v\) の記録は必ず

\[ \text{"a"} + (\text{子部分木の記録を順に連結}) + \text{"b"} \]

になります。

重要な観察

• 子の順番だけが自由度なので、頂点 \(v\) の候補文字列は
  「子ごとの候補集合」×「子の順列」を組み合わせれば作れます。
• 葉なら候補は ab の 1 通りだけ。
• 木全体の候補は根（部屋 1）の候補集合。

素朴法の問題点

木全体で DFS 順を直接全部試すと、どの頂点でも順列分岐があり実装が複雑です。
また、同じ文字列が重複して出る（同型の子部分木など）ため、重複除去が必要です。

解決法

• まず木を根付き木（根 1）にして子配列を作る。
• dfs(v) で「頂点 \(v\) の部分木から作れる全巡回記録集合」を返す。
• 子の順列を next_permutation で全探索し、順列ごとに直積で連結。
• set<string> に入れて重複除去。
• これを高橋木・青木木で別々に行い、最後に集合の積集合を取る。

アルゴリズム

1. 入力された無向木を BFS で根 1 からたどり、parent と children を構築。
2. 再帰関数 dfs(v):
   • 各子 c について childSets[c] = dfs(c) を得る。
   • 子が 0 人なら {"ab"} を返す。
   • 子インデックス配列 idx = [0,1,...,k-1] を全順列で回す。
   • 各順列について、
     初期 cur = {""} から順に cur = { pre + add | pre in cur, add in childSets[id] } で連結候補を作る。
   • 各 mid in cur に対して "a" + mid + "b" を set に追加。
   • set の中身を vector<string> で返す。
3. 2 本の木それぞれで根の候補集合 SA, SB を得る。
4. SA, SB をソート＆unique 後、set_intersection で共通部分 inter を作る。
5. 個数と文字列を順に出力。

計算量

• 時間計算量: 厳密には生成される文字列総数に依存。
  各頂点で「子順列 \(k!\)」と「子集合の直積」を列挙するため、
  全体は 出力サイズ（および中間生成サイズ）にほぼ比例する指数時間。
  ただし \(N \le 10\) なので十分実行可能。
• 空間計算量: 生成・保持する文字列集合の総サイズに依存（これも出力サイズ依存）。

実装のポイント

• 根付き木化（親子の向き付け）を先にやると再帰が書きやすいです。

• 同じ文字列が複数経路で生成されるため、各頂点で set<string> を使って重複除去します。

• 最後の積集合のために SA, SB をソートしておくと set_intersection が使えて簡潔です。

• 文字列長は常に \(2N\) なので、比較（辞書順）も扱いやすいです。

  ソースコード

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

static vector<string> enumerate_records(int N, const vector<vector<int>>& g) {
    vector<int> parent(N + 1, -1);
    vector<vector<int>> children(N + 1);

    // root at 1
    {
        queue<int> q;
        q.push(1);
        parent[1] = 0;
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int to : g[v]) {
                if (parent[to] != -1) continue;
                parent[to] = v;
                children[v].push_back(to);
                q.push(to);
            }
        }
    }

    function<vector<string>(int)> dfs = [&](int v) -> vector<string> {
        vector<vector<string>> childSets;
        childSets.reserve(children[v].size());
        for (int c : children[v]) childSets.push_back(dfs(c));

        int k = (int)children[v].size();
        if (k == 0) return vector<string>{"ab"};

        vector<int> idx(k);
        iota(idx.begin(), idx.end(), 0);

        set<string> uniq; // deduplicate due to identical child-subtrees' strings

        do {
            vector<string> cur{""};
            for (int id : idx) {
                vector<string> nxt;
                nxt.reserve(cur.size() * childSets[id].size());
                for (const string& pre : cur) {
                    for (const string& add : childSets[id]) {
                        nxt.push_back(pre + add);
                    }
                }
                cur.swap(nxt);
            }
            for (auto &mid : cur) {
                uniq.insert("a" + mid + "b");
            }
        } while (next_permutation(idx.begin(), idx.end()));

        vector<string> res(uniq.begin(), uniq.end());
        return res;
    };

    return dfs(1);
}

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

    int N;
    cin >> N;

    vector<vector<int>> gA(N + 1), gB(N + 1);
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> 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;
        gB[u].push_back(v);
        gB[v].push_back(u);
    }

    vector<string> SA = enumerate_records(N, gA);
    vector<string> SB = enumerate_records(N, gB);

    vector<string> inter;
    {
        sort(SA.begin(), SA.end());
        SA.erase(unique(SA.begin(), SA.end()), SA.end());
        sort(SB.begin(), SB.end());
        SB.erase(unique(SB.begin(), SB.end()), SB.end());
        set_intersection(SA.begin(), SA.end(), SB.begin(), SB.end(), back_inserter(inter));
    }

    cout << inter.size() << '\n';
    for (auto &s : inter) cout << s << '\n';

    return 0;
}

---

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