概要

各木について、子の訪問順序を自由に変えたときに作れるすべての巡回記録を集合として列挙します。
その後、2 つの集合の共通部分を取り、辞書順に出力します。

考察

巡回記録は、根付き木を DFS したときの「入るときに a、出るときに b」という括弧列のような文字列です。

例えば、ある頂点が葉なら、その頂点の巡回記録は必ず

ab

です。

一方、ある頂点 \(v\) に子が複数ある場合、子を訪れる順番を自由に並べ替えられます。
また、それぞれの子部分木の中でも、さらに自由に順番を選べます。

つまり、頂点 \(v\) の巡回記録は次のように作れます。

1. 各子部分木から作れる巡回記録の集合を求める
2. 子の並び順を全通り試す
3. その順番に従って、各子の巡回記録を 1 つずつ選んで連結する
4. 先頭に a、末尾に b を付ける

例えば、子の巡回記録がそれぞれ ab, aabb なら、順番によって

a + ab + aabb + b = aabaabbb
a + aabb + ab + b = aaabbabb

のように異なる文字列が得られます。

ただし、同じ形の子が複数ある場合など、異なる訪問順序から同じ文字列ができることがあります。
問題では重複なく出力する必要があるため、生成した文字列は set で管理します。

制約は \(N \leq 10\) と非常に小さいため、各木についてすべての巡回記録を全列挙しても十分間に合います。

アルゴリズム

まず、入力の木は無向グラフとして与えられるので、部屋 \(1\) を根として親子関係を作ります。

その後、次の再帰関数を考えます。

dfs(v)

頂点 \(v\) を根とする部分木から作れる巡回記録の集合を返す。

• \(v\) が葉なら、返す集合は {"ab"}
• そうでなければ、
  • 各子 \(c\) について dfs(c) を計算する
  • 子の並び順を全順列で試す
  • その順番に従って、各子の巡回記録を 1 つずつ選ぶ全組み合わせを試す
  • 連結して a + 子たちの記録 + b を作り、集合に追加する

コードでは、子の並び順の全列挙に permutations、子ごとの巡回記録の選び方の全列挙に product を使っています。

最後に、

records_a = generate_records(adj_a)
records_b = generate_records(adj_b)
common = sorted(records_a & records_b)

として、2 つの木から得られる巡回記録集合の共通部分を取り、辞書順に並べます。

Python の文字列比較では 'a' < 'b' なので、そのまま sorted すれば問題文の辞書順になります。

計算量

• 時間計算量: \(O\left(\sum_v d_v! \prod_{c} R_c \cdot s_v + K \log K \cdot N\right)\)
• 空間計算量: \(O\left(\sum_v R_v \cdot s_v\right)\)

ここで、

• \(d_v\) は頂点 \(v\) の子の数
• \(R_v\) は頂点 \(v\) の部分木から作れる巡回記録の個数
• \(s_v\) は頂点 \(v\) の部分木サイズ
• \(K\) は共通巡回記録の個数

です。

各候補文字列の長さは最大 \(2N\) なので、文字列の連結やソート比較に \(O(N)\) 程度かかります。
ただし制約が \(N \leq 10\) と小さいため、全列挙で十分高速です。

実装のポイント

• 入力の木は無向辺なので、まず根 \(1\) から探索して children を作る

• 各部分木の巡回記録は set で管理し、重複を除く

• 葉の巡回記録は必ず {"ab"}

• 子の順序は permutations で全通り試す

• 各子の巡回記録の選び方は product で全通り試す

• 最後は集合の共通部分 records_a & records_b を取り、sorted で辞書順に並べる

  ソースコード

import sys
from itertools import permutations, product

def generate_records(adj):
    n = len(adj)
    children = [[] for _ in range(n)]
    parent = [-1] * n
    parent[0] = -2
    stack = [0]

    for v in stack:
        for to in adj[v]:
            if parent[to] == -1:
                parent[to] = v
                children[v].append(to)
                stack.append(to)

    sys.setrecursionlimit(10000)

    def dfs(v):
        if not children[v]:
            return {"ab"}

        child_sets = [dfs(c) for c in children[v]]
        k = len(child_sets)
        res = set()

        for perm in permutations(range(k)):
            ordered_sets = [child_sets[i] for i in perm]
            for parts in product(*ordered_sets):
                res.add("a" + "".join(parts) + "b")

        return res

    return dfs(0)

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    idx = 1

    adj_a = [[] for _ in range(n)]
    for _ in range(n - 1):
        u = data[idx] - 1
        v = data[idx + 1] - 1
        idx += 2
        adj_a[u].append(v)
        adj_a[v].append(u)

    adj_b = [[] for _ in range(n)]
    for _ in range(n - 1):
        u = data[idx] - 1
        v = data[idx + 1] - 1
        idx += 2
        adj_b[u].append(v)
        adj_b[v].append(u)

    records_a = generate_records(adj_a)
    records_b = generate_records(adj_b)

    common = sorted(records_a & records_b)

    out = [str(len(common))]
    out.extend(common)
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

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