結果

問題 No.1976 Cut then Connect
ユーザー lam6er
提出日時 2025-03-31 17:47:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 297 ms / 2,000 ms
コード長 3,821 bytes
コンパイル時間 188 ms
コンパイル使用メモリ 82,588 KB
実行使用メモリ 102,124 KB
最終ジャッジ日時 2025-03-31 17:49:15
合計ジャッジ時間 6,586 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    sys.setrecursionlimit(1 << 25)
    N = int(sys.stdin.readline())
    adj = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = map(int, sys.stdin.readline().split())
        adj[u].append(v)
        adj[v].append(u)

    def find_farthest(start):
        visited = [-1] * (N + 1)
        q = deque([start])
        visited[start] = 0
        max_dist = 0
        far_node = start
        while q:
            u = q.popleft()
            for v in adj[u]:
                if visited[v] == -1:
                    visited[v] = visited[u] + 1
                    q.append(v)
                    if visited[v] > max_dist:
                        max_dist = visited[v]
                        far_node = v
        return far_node, visited

    s, _ = find_farthest(1)
    t, dist_s = find_farthest(s)
    s_new, dist_t = find_farthest(t)
    assert s_new == s  # To confirm t is farthest from s

    parent = [0] * (N + 1)
    q = deque([s])
    parent[s] = -1
    while q:
        u = q.popleft()
        for v in adj[u]:
            if parent[v] == 0 and v != parent[u]:
                parent[v] = u
                q.append(v)
                if v == t:
                    q = deque()  # Break early
                    break

    path = []
    u = t
    while u != s:
        path.append(u)
        u = parent[u]
    path.append(s)
    path = path[::-1]
    D = len(path) - 1

    d = [0] * (D + 1)
    for i in range(D + 1):
        current = path[i]
        prev_node = path[i - 1] if i > 0 else None
        next_node = path[i + 1] if i < D else None
        branches = []
        for v in adj[current]:
            if v != prev_node and v != next_node:
                branches.append(v)
        if not branches:
            d[i] = 0
            continue
        visited = {current}
        max_depth = 0
        q = deque()
        for b in branches:
            q.append((b, 1))
            visited.add(b)
            max_depth = max(max_depth, 1)
        while q:
            u_node, depth = q.popleft()
            for v in adj[u_node]:
                if v not in visited and v != current:
                    visited.add(v)
                    new_depth = depth + 1
                    if new_depth > max_depth:
                        max_depth = new_depth
                    q.append((v, new_depth))
        d[i] = max_depth

    max_left = [0] * (D + 1)
    max_left_sub = [0] * (D + 1)
    current_max = d[0] + 0
    current_max_sub = d[0] - 0
    max_left[0] = current_max
    max_left_sub[0] = current_max_sub
    for i in range(1, D + 1):
        current_max = max(current_max, d[i] + i)
        current_max_sub = max(current_max_sub, d[i] - i)
        max_left[i] = current_max
        max_left_sub[i] = current_max_sub

    max_right = [0] * (D + 1)
    max_right_sub = [0] * (D + 1)
    current_max = d[D] + D
    current_max_sub = d[D] - D
    max_right[D] = current_max
    max_right_sub[D] = current_max_sub
    for i in range(D - 1, -1, -1):
        current_max = max(current_max, d[i] + i)
        current_max_sub = max(current_max_sub, d[i] - i)
        max_right[i] = current_max
        max_right_sub[i] = current_max_sub

    min_candidate = float('inf')
    for i in range(D):
        len1 = i
        sum1 = max_left[i] + max_left_sub[i]
        diam1 = max(len1, sum1)

        len2 = D - (i + 1)
        if i + 1 > D:
            sum2 = 0
        else:
            sum2 = max_right[i + 1] + max_right_sub[i + 1]
        diam2 = max(len2, sum2)

        radii1 = (diam1 + 1) // 2
        radii2 = (diam2 + 1) // 2
        candidate = max(diam1, diam2, radii1 + radii2 + 1)
        if candidate < min_candidate:
            min_candidate = candidate

    print(min_candidate)

if __name__ == '__main__':
    main()
0