結果

問題 No.1789 Tree Growing
ユーザー gew1fw
提出日時 2025-06-12 13:15:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,973 bytes
コンパイル時間 581 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 86,624 KB
最終ジャッジ日時 2025-06-12 13:17:58
合計ジャッジ時間 13,722 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 2 TLE * 2 -- * 81
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from sys import stdin
from collections import defaultdict, deque

def input():
    return stdin.read()

def tree_edges(n, edges):
    adj = [[] for _ in range(n+1)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj

def is_subdivision(T1_adj, T1_nodes, T2_adj, mapping):
    visited = set()
    T1_edges = []
    for u in T1_nodes:
        for v in T1_adj[u]:
            if v > u:
                T1_edges.append((u, v))
    
    used_edges = set()
    parent = {}
    for u, v in T1_edges:
        start = mapping[u]
        end = mapping[v]
        path = []
        stack = [(start, -1)]
        found = False
        local_parent = {}
        while stack:
            node, p = stack.pop()
            local_parent[node] = p
            if node == end:
                found = True
                break
            for neighbor in T2_adj[node]:
                if neighbor != p and neighbor not in local_parent:
                    stack.append((neighbor, node))
        if not found:
            return False
        path = []
        current = end
        while current != start:
            path.append(current)
            current = local_parent[current]
        path.append(start)
        path = path[::-1]
        for i in range(len(path)-1):
            a = path[i]
            b = path[i+1]
            if (a, b) in used_edges or (b, a) in used_edges:
                return False
            used_edges.add((a, b))
    return True

def check_remaining(T2_adj, core_nodes):
    visited = set(core_nodes)
    components = []
    for node in range(1, len(T2_adj)):
        if node not in visited:
            stack = [node]
            component = set()
            component.add(node)
            visited.add(node)
            parent = {}
            while stack:
                u = stack.pop()
                for v in T2_adj[u]:
                    if v not in visited:
                        visited.add(v)
                        stack.append(v)
                        component.add(v)
                        parent[v] = u
                    elif v in component and parent.get(u) != v:
                        return False
            components.append(component)
    for comp in components:
        entry = None
        count = 0
        for node in comp:
            for neighbor in T2_adj[node]:
                if neighbor not in comp:
                    if entry is None:
                        entry = neighbor
                    else:
                        if neighbor != entry:
                            return False
                    count += 1
        if count != 1:
            return False
    return True

def solve():
    data = sys.stdin.read().split()
    ptr = 0
    K = int(data[ptr])
    ptr +=1
    T1_edges = []
    for _ in range(K-1):
        a = int(data[ptr])
        b = int(data[ptr+1])
        ptr +=2
        T1_edges.append((a, b))
    T1_adj = [[] for _ in range(K+1)]
    for a, b in T1_edges:
        T1_adj[a].append(b)
        T1_adj[b].append(a)
    N = int(data[ptr])
    ptr +=1
    T2_edges = []
    for _ in range(N-1):
        c = int(data[ptr])
        d = int(data[ptr+1])
        ptr +=2
        T2_edges.append((c, d))
    T2_adj = [[] for _ in range(N+1)]
    for c, d in T2_edges:
        T2_adj[c].append(d)
        T2_adj[d].append(c)
    
    from itertools import permutations
    if K > N:
        print(-1)
        return
    
    T1_nodes = list(range(1, K+1))
    best = -1
    for perm in permutations(range(1, N+1), K):
        mapping = {i+1: perm[i] for i in range(K)}
        if is_subdivision(T1_adj, T1_nodes, T2_adj, mapping):
            core_nodes = set()
            for u in T1_nodes:
                core_nodes.add(mapping[u])
            for u, v in T1_edges:
                start = mapping[u]
                end = mapping[v]
                path = []
                stack = [(start, -1)]
                local_parent = {}
                while stack:
                    node, p = stack.pop()
                    local_parent[node] = p
                    if node == end:
                        break
                    for neighbor in T2_adj[node]:
                        if neighbor != p and neighbor not in local_parent:
                            stack.append((neighbor, node))
                current = end
                while current != start:
                    core_nodes.add(current)
                    current = local_parent[current]
            valid = check_remaining(T2_adj, core_nodes)
            if valid:
                core_edges = 0
                visited = set()
                for u in core_nodes:
                    for v in T2_adj[u]:
                        if v in core_nodes and (v, u) not in visited:
                            core_edges +=1
                            visited.add((u, v))
                best = max(best, core_edges)
    print(best if best !=0 else -1)

solve()
0