結果
問題 |
No.1789 Tree Growing
|
ユーザー |
![]() |
提出日時 | 2025-06-12 13:28:37 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,360 bytes |
コンパイル時間 | 251 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 55,296 KB |
最終ジャッジ日時 | 2025-06-12 13:33:45 |
合計ジャッジ時間 | 7,053 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 WA * 34 |
ソースコード
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()