結果

問題 No.1789 Tree Growing
ユーザー qwewe
提出日時 2025-05-14 13:18:11
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 8,624 bytes
コンパイル時間 220 ms
コンパイル使用メモリ 82,816 KB
実行使用メモリ 79,556 KB
最終ジャッジ日時 2025-05-14 13:19:00
合計ジャッジ時間 12,900 ms
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 81
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
import collections
import itertools

# Increase recursion depth if needed, although the current approach is iterative.
# sys.setrecursionlimit(2000) 

def solve():
    # Read input for T1
    K = int(sys.stdin.readline())
    adj1 = collections.defaultdict(list)
    edges1 = []
    # Check if K is 0 or 1 (though problem constraints say K >= 2)
    if K < 2:
       # Handle edge cases, possibly print 0 or -1 depending on N
       # Given constraints 2 <= K <= N, this block might not be needed
       pass

    for _ in range(K - 1):
        u, v = map(int, sys.stdin.readline().split())
        # Adjust to 0-based indexing
        u -= 1
        v -= 1
        adj1[u].append(v)
        adj1[v].append(u)
        # Store edges of T1 for iteration later. Ensure canonical representation.
        edges1.append(tuple(sorted((u, v)))) 

    # Read input for T2
    N = int(sys.stdin.readline())
    adj2 = collections.defaultdict(list)
    for _ in range(N - 1):
        u, v = map(int, sys.stdin.readline().split())
        # Adjust to 0-based indexing
        u -= 1
        v -= 1
        adj2[u].append(v)
        adj2[v].append(u)

    # If the initial tree T1 has more vertices than the target tree T2, it's impossible.
    if K > N:
        print("-1")
        return

    # Special case: K=2. T1 is just a single edge.
    # We need to find the longest path (diameter) in T2. The length of the diameter
    # corresponds to the maximum number of red edges possible.
    if K == 2:
        if N == 0: # Should not happen based on constraints
             print(0)
             return
        if N == 1: # Need at least 2 vertices for an edge
             print(0) # Or maybe -1 if K=2 requires N>=2? Based on constraints N>=K>=2.
             return

        # Use two BFS passes to find the diameter of T2
        
        # First BFS: Find the farthest node from an arbitrary starting node (e.g., node 0)
        q = collections.deque([(0, 0)]) # (node, distance)
        dists = [-1] * N
        dists[0] = 0
        farthest_node = 0
        max_dist = 0
        
        visited = {0}
        
        while q:
            curr, d = q.popleft()
            if d > max_dist:
                max_dist = d
                farthest_node = curr

            for neighbor in adj2[curr]:
                 if neighbor not in visited:
                     visited.add(neighbor)
                     dists[neighbor] = d + 1
                     q.append((neighbor, d+1))

        # Second BFS: Find the farthest node from the node found in the first BFS
        q = collections.deque([(farthest_node, 0)])
        dists = [-1] * N
        dists[farthest_node] = 0
        diameter = 0
        
        visited = {farthest_node}

        while q:
            curr, d = q.popleft()
            diameter = max(diameter, d)
            for neighbor in adj2[curr]:
                 if neighbor not in visited:
                     visited.add(neighbor)
                     dists[neighbor] = d + 1
                     q.append((neighbor, d+1))
        
        print(diameter)
        return


    # General Case for K > 2
    
    # Precompute all pairs shortest paths and parent pointers in T2 using BFS from each node.
    # dist[i][j] stores the distance from node i to node j.
    # parent_path[i][j] stores the predecessor of j on the shortest path from i.
    dist = [[-1] * N for _ in range(N)]
    parent_path = [[-1] * N for _ in range(N)]

    for i in range(N):
        q = collections.deque([(i, 0)]) # (node, distance)
        dist[i][i] = 0
        visited = {i}
        
        while q:
            curr, d = q.popleft()
            
            for neighbor in adj2[curr]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    dist[i][neighbor] = d + 1
                    parent_path[i][neighbor] = curr # Store parent for path reconstruction
                    q.append((neighbor, d + 1))

    # Helper function to get the path nodes and path edges between two nodes in T2
    def get_path(start_node, end_node):
        # Check if path exists using precomputed distances
        if dist[start_node][end_node] == -1:
             return None, None 
        
        path_nodes = []
        curr = end_node
        # Handle path of length 0 (start_node == end_node)
        if start_node == end_node:
             return [start_node], set()

        # Reconstruct path by backtracking using parent pointers
        while curr != start_node:
            path_nodes.append(curr)
            prev = parent_path[start_node][curr] 
            # Error check: prev should not be -1 unless curr is start_node
            if prev == -1: return None, None 
            curr = prev
        path_nodes.append(start_node)
        path_nodes.reverse() # Path nodes are now in order from start_node to end_node
        
        # Collect edges on the path. Use a set for uniqueness and canonical representation.
        path_edges = set() 
        for i in range(len(path_nodes) - 1):
             u, v = path_nodes[i], path_nodes[i+1]
             path_edges.add(tuple(sorted((u, v)))) # Store edge tuple (min_idx, max_idx)

        return path_nodes, path_edges


    V1 = list(range(K)) # Vertices of T1
    V2 = list(range(N)) # Vertices of T2

    max_red_edges = -1 # Initialize maximum red edges found so far

    # The core logic involves finding a subdivision of T1 within T2.
    # This requires mapping vertices of T1 (V1) to distinct vertices in T2 (branch vertices),
    # and mapping edges of T1 to paths in T2 connecting corresponding branch vertices.
    # These paths must be internally vertex-disjoint from each other and from branch vertices.
    # We want to maximize the total number of unique edges used in these paths.

    # The following approach tries all possible injective mappings from V1 to V2.
    # It has complexity O(P(N, K) * K * N), where P(N, K) = N! / (N-K)!.
    # This is computationally expensive and will likely TLE for large N and K.
    # For N, K <= 100, this is too slow unless K is very small.
    # However, for small K (e.g., K <= 8) or small N, it might pass within the time limit.
    
    # Iterate through all permutations of V2 of length K, representing injective mappings V1 -> V2
    for p_V2 in itertools.permutations(V2, K):
        # Define the mapping phi based on the current permutation
        phi = {V1[i]: p_V2[i] for i in range(K)}
        # Set of vertices in T2 that are images of V1 vertices (branch vertices)
        phi_values = set(p_V2) 
        
        possible = True # Flag to track if the current mapping is valid
        # Keep track of internal vertices used by paths to ensure disjointness
        used_internal_nodes = set()
        # Keep track of all edges used by paths (red edges)
        current_total_red_edges_set = set()

        # Iterate over all edges in T1
        for u1, v1 in edges1: 
            # Find corresponding vertices in T2 under the current mapping phi
            u2, v2 = phi[u1], phi[v1]
            
            # Find the shortest path between u2 and v2 in T2
            path_nodes, path_edges = get_path(u2, v2)
            
            # If path doesn't exist (should not happen in a connected tree), mapping is invalid
            if path_nodes is None: 
                 possible = False 
                 break

            # Extract internal vertices of the path (excluding endpoints u2, v2)
            internal_nodes_on_path = set(path_nodes[1:-1])

            # Check validity condition 1: Internal nodes cannot be branch vertices
            if not internal_nodes_on_path.isdisjoint(phi_values):
                possible = False
                break

            # Check validity condition 2: Internal nodes cannot overlap with those from other paths
            if not internal_nodes_on_path.isdisjoint(used_internal_nodes):
                 possible = False
                 break
            
            # If valid so far, update the set of used internal nodes and collect the path edges
            used_internal_nodes.update(internal_nodes_on_path)
            current_total_red_edges_set.update(path_edges)

        # If any check failed for this mapping, continue to the next permutation
        if not possible: 
            continue

        # If all edges of T1 were successfully mapped to valid paths
        # Update the maximum number of red edges found
        max_red_edges = max(max_red_edges, len(current_total_red_edges_set))

    # Print the result
    print(max_red_edges)

# Execute the main function
solve()
0