結果
問題 | No.1976 Cut then Connect |
ユーザー |
![]() |
提出日時 | 2022-06-10 23:59:14 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 168 ms / 2,000 ms |
コード長 | 1,769 bytes |
コンパイル時間 | 299 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 91,364 KB |
最終ジャッジ日時 | 2024-11-24 12:16:54 |
合計ジャッジ時間 | 3,974 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
import sys input = sys.stdin.buffer.readline sys.setrecursionlimit(10 ** 7) inf = 10 ** 9 def dfs(N, root, G): que = [root] dist = [-1] * N par = [-1] * N dist[root] = 0 while que: s = que.pop() for t in G[s]: if t == par[s]: continue par[t] = s dist[t] = dist[s] + 1 que.append(t) return dist, par def search(N, path, G): M = len(path) res = [0] * M d = [-1] * N for i in range(M): ng = set() if i: ng.add(path[i-1]) if i < M - 1: ng.add(path[i+1]) que = [path[i]] d[path[i]] = 0 while que: s = que.pop() for t in G[s]: if t in ng: continue if d[t] == -1: d[t] = d[s] + 1 que.append(t) res[i] = max(res[i], d[t]) return res def calc(path, branch): M = len(path) res = [] d = 0 for i in range(M): d = max(d, i + branch[i]) res.append(d) return res N = int(input()) G = [[] for _ in range(N)] for _ in range(N-1): a, b = map(int, input().split()) a -= 1 b -= 1 G[a].append(b) G[b].append(a) r0 = 0 d0, p0 = dfs(N, r0, G) r1 = d0.index(max(d0)) d1, p1 = dfs(N, r1, G) r2 = d1.index(max(d1)) path = [r2] while 1: x = p1[path[-1]] if x == -1: break path.append(x) M = len(path) dep = [min(i, M - i - 1) for i in range(M)] branch = search(N, path, G) L = calc(path, branch) R = calc(path[::-1], branch[::-1])[::-1] ans = inf for i in range(M - 1): l = L[i] r = R[i+1] d = max(l, r, (l+1)//2 + (r+1)//2 + 1) ans = min(ans, d) print(ans)