結果

問題 No.1789 Tree Growing
ユーザー gew1fw
提出日時 2025-06-12 13:23:08
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,360 bytes
コンパイル時間 179 ms
コンパイル使用メモリ 82,232 KB
実行使用メモリ 57,256 KB
最終ジャッジ日時 2025-06-12 13:27:04
合計ジャッジ時間 6,680 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 51 WA * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from itertools import permutations

def read_tree(n):
    edges = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, stdin.readline().split())
        edges[u].append(v)
        edges[v].append(u)
    return edges

def contract_degree_two(edges):
    n = len(edges) - 1
    new_edges = [set() for _ in range(n+1)]
    degree = [len(e) for e in edges]
    for u in range(1, n+1):
        if degree[u] != 2:
            stack = []
            visited = set()
            for v in edges[u]:
                if degree[v] == 1:
                    new_edges[u].add(v)
                    new_edges[v].add(u)
                else:
                    prev = u
                    current = v
                    path = []
                    while degree[current] == 2:
                        path.append(current)
                        next_nodes = [x for x in edges[current] if x != prev]
                        if not next_nodes:
                            break
                        prev, current = current, next_nodes[0]
                    if degree[current] != 2:
                        new_edges[u].add(current)
                        new_edges[current].add(u)
    new_adj = [[] for _ in range(n+1)]
    for u in range(1, n+1):
        for v in new_edges[u]:
            if v > u:
                new_adj[u].append(v)
                new_adj[v].append(u)
    return new_adj

def is_isomorphic(tree1, tree2):
    def encode(tree):
        n = len(tree) - 1
        labels = {}
        from collections import deque
        def bfs(root):
            visited = [False] * (n + 1)
            q = deque()
            q.append((root, -1))
            parent = {}
            children = {}
            while q:
                u, p = q.popleft()
                parent[u] = p
                children[u] = []
                for v in tree[u]:
                    if v != p:
                        children[u].append(v)
                        q.append((v, u))
            return children
        def dfs(u, p):
            res = []
            for v in tree[u]:
                if v != p:
                    res.append(dfs(v, u))
            res.sort()
            return tuple(res)
        centers = []
        degrees = [len(tree[i]) for i in range(len(tree))]
        max_degree = max(degrees)
        for i in range(1, len(tree)):
            if degrees[i] == max_degree:
                centers.append(i)
        for center in centers:
            encoded = dfs(center, -1)
            if encoded not in labels:
                labels[encoded] = len(labels)
            return labels[encoded]
        return None
    code1 = encode(tree1)
    code2 = encode(tree2)
    return code1 == code2

def main():
    K = int(stdin.readline())
    T1 = read_tree(K)
    N = int(stdin.readline())
    T2 = read_tree(N)
    if K > N:
        print(-1)
        return
    contracted_T2 = contract_degree_two(T2)
    if is_isomorphic(T1, contracted_T2):
        leaves_T2 = sum(1 for i in range(1, N+1) if len(T2[i]) == 1)
        leaves_T1 = sum(1 for i in range(1, K+1) if len(T1[i]) == 1)
        L = leaves_T2 - leaves_T1
        if L < 0:
            print(-1)
            return
        red_edges = (N-1) - L
        print(red_edges)
    else:
        print(-1)

if __name__ == "__main__":
    main()
0