概要

2つの根付き木（高橋君の施設と青木君の施設）が与えられ、それぞれの木において「子の訪問順序を任意に決めたときのDFS巡回記録（行きに a、帰りに b を追加）」をすべて生成し、それらの共通集合を辞書順に列挙する問題です。

ノード数 \(N\) が最大 10 と非常に小さいため、再帰的にすべての可能な文字列を生成するアプローチで解くことができます。

考察

巡回記録の構造

あるノード \(v\) を根とする部分木の巡回記録は、以下の形式になります。 'a' + (子1の部分木の記録) + (子2の部分木の記録) + ... + (子kの部分木の記録) + 'b'

ここで、子の訪問順序は任意であるため、子 \(1, \dots, k\) の並び替え（順列）の数だけパターンの候補が生じます。さらに、各子の部分木についても複数の巡回記録があり得るため、それらの組み合わせ（直積）も考慮する必要があります。

重複の排除

同じ構造を持つ部分木が複数ある場合、それらを入れ替えても得られる文字列は変わりません。無駄な計算を避けるために、生成した文字列の集合をソート・一意化しながら再帰的に処理を進めるのが効率的です。

アルゴリズム

各ノード \(u\) について、その部分木から生成可能な巡回記録の集合（文字列のリスト）を返す関数 get_all_strings(u) を考えます。

1. ベースケース: ノード \(u\) が葉（子を持たない）の場合、{"ab"} を返します。
2. 再帰ステップ:
   • \(u\) のすべての子 \(v_1, v_2, \dots, v_k\) に対して、再帰的に get_all_strings(v_i) を呼び出し、各子の文字列集合を取得します。
   • 子の集合の並び順を全通り試します（next_permutation を使用）。
   • 各並び順において、各子の集合から文字列を1つずつ選ぶすべての組み合わせ（直積）を生成し、'a' + ... + 'b' の形に結合します。
   • 得られたすべての文字列をソートし、重複を取り除いたものを \(u\) の結果として返します。
3. 最終処理:
   • 高橋君の木（根=1）から得られる集合 \(S_A\) と、青木君の木（根=1）から得られる集合 \(S_B\) を求めます。
   • \(S_A\) と \(S_B\) の共通部分（積集合）を求め、その個数と内容を出力します。

計算量

\(N \le 10\) という制約下では、生成される文字列の総数はそれほど多くなりません。 - 時間計算量: 最悪ケースでも \(N\) 個の括弧列の総数（カタラン数 \(C_{N-1}\)）や順列の組み合わせに関連しますが、\(N=10\) では十分に高速に動作します。 - 空間計算量: 各ノードで保持する文字列のリストが支配的ですが、これもメモリ制限内に収まります。

実装のポイント

• 順列の生成: std::next_permutation を使う際、子の集合自体をソートしておくことで、同じ構造を持つ子（同じ文字列集合を返す子）の重複した順列を自動的にスキップできます。

• 直積の生成: 子の順序を固定したあと、各子の集合から1つずつ選ぶ処理は、再帰や多重ループ（またはバックトラッキング）で実装できます。

• 共通部分の取得: std::set_intersection を使うと、2つのソート済みベクトルから効率的に共通要素を取り出すことができます。

  ソースコード

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <iterator>

using namespace std;

/**
 * Problem: Common Traversal Records
 * Given two rooted trees with N nodes, both rooted at node 1.
 * A traversal record is generated by a DFS traversal where children are visited in any order.
 * 'a' is added when entering a node, and 'b' is added when leaving.
 * We need to find the intersection of all possible traversal records for both trees
 * and list them in lexicographical order.
 * N is small (N <= 10), so the number of possible strings is manageable (at most Catalan number C_{N-1}).
 */

// Function to generate all unique traversal strings for a subtree rooted at u
vector<string> get_all_strings(int u, int p, const vector<vector<int>>& adj) {
    vector<vector<string>> child_sets;
    for (int v : adj[u]) {
        if (v == p) continue;
        // Recursively get all possible traversal records for each child's subtree
        child_sets.push_back(get_all_strings(v, u, adj));
    }
    
    // Base case: If u is a leaf, the only traversal record is "ab" (entering then leaving)
    if (child_sets.empty()) {
        return {"ab"};
    }

    // Sort the sets of strings from children to handle identical children efficiently
    // This allows next_permutation to generate only unique orderings of the children.
    sort(child_sets.begin(), child_sets.end());
    
    vector<string> results;
    int k = child_sets.size();
    string current = "";

    // Recursive function to pick one string from each child's set and concatenate them
    function<void(int)> combine = [&](int idx) {
        if (idx == k) {
            // A traversal record for the current node is 'a' + concatenated child strings + 'b'
            results.push_back("a" + current + "b");
            return;
        }
        int old_size = current.size();
        for (const string& s : child_sets[idx]) {
            current += s;
            combine(idx + 1);
            current.resize(old_size); // Backtrack
        }
    };

    // next_permutation generates all unique permutations of the children's sets
    do {
        combine(0);
    } while (next_permutation(child_sets.begin(), child_sets.end()));

    // Sort and remove duplicates to return only unique traversal records for this subtree
    sort(results.begin(), results.end());
    results.erase(unique(results.begin(), results.end()), results.end());
    return results;
}

int main() {
    // Optimize standard I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    
    // Adjacency lists for Takahashi's facility (Tree A) and Aoki's facility (Tree B)
    vector<vector<int>> adjA(N + 1), adjB(N + 1);
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        if (!(cin >> u >> v)) break;
        adjA[u].push_back(v);
        adjA[v].push_back(u);
    }
    for (int i = 0; i < N - 1; ++i) {
        int u, v;
        if (!(cin >> u >> v)) break;
        adjB[u].push_back(v);
        adjB[v].push_back(u);
    }

    // Generate all possible traversal records for both facilities starting from root 1
    vector<string> setA = get_all_strings(1, 0, adjA);
    vector<string> setB = get_all_strings(1, 0, adjB);

    // Find the common records by intersecting the two sorted sets
    vector<string> common;
    set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(), back_inserter(common));

    // Output the total number of common records
    cout << common.size() << "\n";
    // Output each common record in lexicographical order
    for (const string& s : common) {
        cout << s << "\n";
    }

    return 0;
}

この解説は gemini-3-flash-thinking によって生成されました。