結果
| 問題 |
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 |
ソースコード
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()