概要

2つの根付き木それぞれから、子の訪問順序を変えて生成できるすべての「巡回記録」文字列の集合を求め、その共通部分を辞書順に出力する問題です。\(N \leq 10\) という小さな制約を活かして全列挙で解きます。

考察

巡回記録とは何か

巡回記録は、木のDFS（深さ優先探索）の過程を括弧列として記録したものです。ノードに入るとき a を、出るとき b を追加します。

例えば、根が2つの子を持ち、それぞれが葉である場合： - 根に入る → a - 子1に入る → a、子1から出る → b - 子2に入る → a、子2から出る → b - 根から出る → b

結果: aababbb ではなく a ab ab b = aababb （長さ \(2N = 6\)）

重要な気づき

• 子の訪問順序を変えると、異なる巡回記録が得られる可能性がある
• 各子の部分木が生成する文字列自体も、その内部の訪問順序によって複数パターンありうる
• \(N \leq 10\) なので、生成される文字列の総数は高々 \(9! = 362880\) 程度（最悪でもスター型の場合）であり、全列挙が十分間に合う

アプローチ

制約が非常に小さいので、各木について可能な巡回記録をすべて列挙し、集合の共通部分を求めるブルートフォースが有効です。

アルゴリズム

1. 木の構築: 入力のグラフから、BFSで部屋1を根とした親子関係を決定する。

2. 巡回記録の全列挙（再帰関数 generate）:

   • 葉ノードの場合: "ab" のみを返す
   • 子がいる場合:
     1. 各子ノードについて、その部分木が生成可能な文字列の集合を再帰的に求める
     2. 各子から1つずつ文字列を選ぶ全組合せを列挙する
     3. 各組合せについて、子の並び順の全順列を試し、"a" + (子の文字列を順に連結) + "b" を集合に追加する

3. 共通部分の計算: 2つの集合の積集合（set_intersection）を求める。

4. 出力: set<string> を使っているので自動的に辞書順にソートされている。

計算量

• 時間計算量: 最悪ケースでは、各ノードの子が生成する文字列数の積 × 子の順列数を掛け合わせたものになる。\(N = 10\) でスター型（根に9個の子）の場合、\(9! = 362880\) 通り。部分木がさらに分岐する場合でも、\(N\) が小さいため実用上は十分高速。厳密な上界は \(O(N!)\) 程度。
• 空間計算量: \(O(N! \cdot N)\)（生成される文字列の集合を格納）

実装のポイント

• BFSで木を構築: 無向グラフとして入力されるため、根からBFSして親子関係を確定する。

• 再帰的な集合生成: 各子の部分木が返す文字列集合の「直積」を取り、さらに順列で並べ替えるという二段階の列挙が必要。

• 重複排除: set<string> を使うことで、異なる訪問順序から同じ文字列が生成された場合の重複を自動的に除去できる。

• set_intersectionの利用: STLの set_intersection を使えば、ソート済み集合の共通部分を効率的に求められる。

  ソースコード

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

int N;
vector<int> adj[11];
vector<int> ch[11];

void buildTree(vector<int> adjs[], vector<int> chs[]) {
    for (int i = 1; i <= N; i++) chs[i].clear();
    vector<bool> visited(N + 1, false);
    queue<int> q;
    q.push(1);
    visited[1] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adjs[u]) {
            if (!visited[v]) {
                visited[v] = true;
                chs[u].push_back(v);
                q.push(v);
            }
        }
    }
}

set<string> generate(vector<int> chs[], int node) {
    if (chs[node].empty()) {
        return {"ab"};
    }
    
    int k = chs[node].size();
    vector<vector<string>> childStrings(k);
    for (int i = 0; i < k; i++) {
        auto s = generate(chs, chs[node][i]);
        childStrings[i] = vector<string>(s.begin(), s.end());
    }
    
    // Generate all combinations of one string from each child
    vector<vector<string>> allCombos;
    vector<string> cur(k);
    function<void(int)> genComb = [&](int idx) {
        if (idx == k) {
            allCombos.push_back(cur);
            return;
        }
        for (const string& s : childStrings[idx]) {
            cur[idx] = s;
            genComb(idx + 1);
        }
    };
    genComb(0);
    
    set<string> result;
    vector<int> perm(k);
    iota(perm.begin(), perm.end(), 0);
    
    for (const auto& combo : allCombos) {
        vector<int> p(k);
        iota(p.begin(), p.end(), 0);
        do {
            string s = "a";
            for (int i = 0; i < k; i++) {
                s += combo[p[i]];
            }
            s += "b";
            result.insert(s);
        } while (next_permutation(p.begin(), p.end()));
    }
    
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;
    
    vector<int> adjA[11], adjB[11];
    vector<int> chA[11], chB[11];
    
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adjA[u].push_back(v);
        adjA[v].push_back(u);
    }
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        adjB[u].push_back(v);
        adjB[v].push_back(u);
    }
    
    // Build trees rooted at 1
    // For A
    {
        vector<bool> visited(N + 1, false);
        queue<int> q;
        q.push(1); visited[1] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adjA[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    chA[u].push_back(v);
                    q.push(v);
                }
            }
        }
    }
    // For B
    {
        vector<bool> visited(N + 1, false);
        queue<int> q;
        q.push(1); visited[1] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adjB[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    chB[u].push_back(v);
                    q.push(v);
                }
            }
        }
    }
    
    set<string> setA = generate(chA, 1);
    set<string> setB = generate(chB, 1);
    
    vector<string> intersection;
    set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(), back_inserter(intersection));
    
    cout << intersection.size() << "\n";
    for (const string& s : intersection) {
        cout << s << "\n";
    }
    
    return 0;
}

この解説は claude4.6opus-thinking によって生成されました。