結果
問題 |
No.1789 Tree Growing
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()