#!/usr/bin/env python3 from collections import deque # Formát vstupu: # První řádek: (N = počet vrcholů stromu) # N-1 následujících řádků: (vrchol 1) (vrchol 2) # V každé hraně musí být první vrchol menší než druhý. # Vrcholy jsou číslovány {0, 1, ... N-1}. def convert_to_neighbour_lists(N, edges): """Převede strom daný seznamem hran na seznamy sousedů.""" neighbours = [[] for _ in range(N)] for x, y in edges: assert x < y neighbours[x].append(y) neighbours[y].append(x) return neighbours def calculate_distances(N, edges, start_vertices): """Najde vzdálenosti vrcholů od daného vrcholu/vrcholů.""" assert N >= 1 neighbours = convert_to_neighbour_lists(N, edges) distances = [None for _ in range(N)] queue = deque(start_vertices) for start_vertex in start_vertices: distances[start_vertex] = 0 while len(queue) > 0: vertex = queue.popleft() for neighbour in neighbours[vertex]: if distances[neighbour] is None: distances[neighbour] = distances[vertex] + 1 queue.append(neighbour) return distances def reconstruct_path(neighbours, distances, a, b): """Rekonstruuje cestu z A do B z pole vzdáleností od A.""" path = [b] while path[-1] != a: neighbours_of_last = neighbours[path[-1]] for neighbour in neighbours_of_last: if distances[neighbour] < distances[path[-1]]: path.append(neighbour) break return path def find_longest_path(N, edges): """Najde nejdelší cestu ve stromu daném seznamem hran. Vrátí indexy vrcholů nejdelší cesty v pořadí na cestě.""" assert N >= 1 # 1) Najdi nejvzdálenější vrchol od libovolného kořene. distances = calculate_distances(N, edges, [0]) a = distances.index(max(distances)) # 2) Najdi nejvzdálenější vrchol od něj. distances = calculate_distances(N, edges, [a]) b = distances.index(max(distances)) # Nejdelší cesta je cesta mezi A a B. # Rekonstruuj ji postupným hledáním bližších sousedů. neighbours = convert_to_neighbour_lists(N, edges) return reconstruct_path(neighbours, distances, a, b) def calculate_path_depths(N, edges, path): """Najde pro každý vrchol dané cesty největší hloubku jeho podstromu mimo cestu pomocí BFS z každého jejího vrcholu.""" neighbours = convert_to_neighbour_lists(N, edges) depths = [None for _ in range(N)] visited = [False for _ in range(N)] for vertex in path: visited[vertex] = True for path_vertex in path: queue = deque([path_vertex]) depth = -1 while len(queue) > 0: queue2 = deque() while len(queue) > 0: vertex = queue.popleft() visited[vertex] = True for neighbour in neighbours[vertex]: if visited[neighbour]: continue queue2.append(neighbour) queue = queue2 depth += 1 depths[path_vertex] = depth return depths def calculate_left_radii(depths): """Dostane posloupnost hloubek pod nejdelší cestou, spočítá průměry levých polovin. Dá se použít symetricky na spočítání průměrů pravých polovin.""" assert depths[0] == 0 left_radii = [0] longest_path_so_far = 1 # počítáno ve vrcholech longest_path_from_end = 1 # počítáno ve vrcholech for added_depth in depths[1:]: longest_path_from_end += 1 new_long_path = longest_path_from_end + added_depth longest_path_so_far = max(longest_path_so_far, new_long_path) longest_path_from_end = max(longest_path_from_end, added_depth + 1) left_radii.append(longest_path_so_far // 2) return left_radii def get_component(N, edges, root): """Najde všechny vrcholy ve stejné komponentě souvislosti jako daný vrchol.""" neighbours = convert_to_neighbour_lists(N, edges) vertices = [] visited = [False for _ in range(N)] queue = deque([root]) while len(queue) > 0: vertex = queue.popleft() vertices.append(vertex) for neighbour in neighbours[vertex]: if not visited[neighbour]: queue.append(neighbour) visited[neighbour] = True return vertices def find_center(N, edges, noted_vertices=None): """Najde centrální vrchol daného stromu. Počítá jenom s danou množinou vrcholů.""" if noted_vertices is None: noted_vertices = range(N) assert len(noted_vertices) >= 1 if len(noted_vertices) == 1: return noted_vertices[0] is_noted_vertex = [False for _ in range(N)] for vertex in noted_vertices: is_noted_vertex[vertex] = True edges = [(x, y) for x, y in edges if is_noted_vertex[x] and is_noted_vertex[y]] degrees = [0 for _ in range(N)] for x, y in edges: assert x < y degrees[x] += 1 degrees[y] += 1 leaves = [x for x in range(N) if degrees[x] == 1] remaining = len([x for x in range(N) if degrees[x] > 0]) neighbours = convert_to_neighbour_lists(N, edges) while remaining > 2: assert sorted(leaves) == [x for x in range(N) if degrees[x] == 1] new_leaves = [] for leaf in leaves: remaining -= 1 for neighbour in neighbours[leaf]: degrees[neighbour] -= 1 degrees[leaf] -= 1 if degrees[neighbour] == 1: new_leaves.append(neighbour) leaves = new_leaves assert len(leaves) == remaining return leaves[0] def canonical_edge(a, b): return (min(a, b), max(a, b)) def find_best_split(N, edges, longest_path, left_radii, right_radii): """Najde nejlepší rozdělení nejdelší cesty na levý a pravý sektor. Cesta může být rozdělena ve vrcholu, nebo ve hraně. Nejlepší rozdělení je reprezentováno jako pár hran, které oddělují od sebe levou a pravou polovinu.""" best_split = None best_split_time = None # Rozdělení podle vrcholu, který bude spálený oběma stranami zároveň. for split in range(1, len(left_radii) - 1): time = max(left_radii[split], right_radii[split]) if best_split is None or time < best_split_time: best_split = ('vertex', split) best_split_time = time for split in range(len(left_radii) - 1): time = max(left_radii[split], right_radii[split + 1]) if best_split is None or time < best_split_time: best_split = ('edge', split) best_split_time = time type, location = best_split left_removed, right_removed = None, None if type == 'vertex': left_removed = (longest_path[location], longest_path[location + 1]) right_removed = (longest_path[location - 1], longest_path[location]) elif type == 'edge': left_removed = (longest_path[location], longest_path[location + 1]) right_removed = (longest_path[location], longest_path[location + 1]) else: raise return (canonical_edge(*left_removed), canonical_edge(*right_removed)) def find_central_pair(N, edges): """Najde centrální pár vrcholů a vrátí jej společně s časem na evakuaci.""" # Najdi nejdelší cestu. longest_path = find_longest_path(N, edges) # Pro každý vrchol na nejdelší cestě spočítej největší hloubku jeho # podstromu. subtree_depths = calculate_path_depths(N, edges, longest_path) # Spočítej průměry levých a pravých polovin. depths = [] for vertex in longest_path: depths.append(subtree_depths[vertex]) left_radii = calculate_left_radii(depths) right_radii = calculate_left_radii(depths[::-1])[::-1] # Najdi nejlepší místo na rozpůlení. best_split = find_best_split(N, edges, longest_path, left_radii, right_radii) left_removed, right_removed = best_split edges_left, edges_right = edges[:], edges[:] edges_left.remove(left_removed) edges_right.remove(right_removed) # Rozděl strom na levý a pravý podstrom podle rozpůlení. left_component = get_component(N, edges_left, longest_path[0]) right_component = get_component(N, edges_right, longest_path[-1]) a = find_center(N, edges_left, noted_vertices=left_component) b = find_center(N, edges_right, noted_vertices=right_component) # Pokud jsme zvolili dvakrát shodný vrchol, druhý vrchol zvol jiný. if a == b: b = (a + 1) % N return (a, b) def main(): N = int(input()) edges = [] for i in range(N - 1): parts = input().split() assert len(parts) == 2 a, b = int(parts[0]), int(parts[1]) assert a < b edges.append((a, b)) pair = find_central_pair(N, edges) a, b = pair print('Zavolej do kanceláří', a, ';', b, '.') if __name__ == '__main__': main()