結果
| 問題 |
No.1976 Cut then Connect
|
| コンテスト | |
| ユーザー |
 lam6er
|
| 提出日時 | 2025-03-26 15:50:01 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,599 bytes |
| コンパイル時間 | 248 ms |
| コンパイル使用メモリ | 82,456 KB |
| 実行使用メモリ | 157,012 KB |
| 最終ジャッジ日時 | 2025-03-26 15:50:28 |
| 合計ジャッジ時間 | 13,311 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 8 WA * 23 |
ソースコード
import sys
from sys import stdin
from collections import deque
sys.setrecursionlimit(1 << 25)
def main():
N = int(stdin.readline())
edges = [[] for _ in range(N+1)]
for _ in range(N-1):
u, v = map(int, stdin.readline().split())
edges[u].append(v)
edges[v].append(u)
root = 1
parent = [0]*(N+1)
children = [[] for _ in range(N+1)]
visited = [False]*(N+1)
q = deque([root])
visited[root] = True
while q:
u = q.popleft()
for v in edges[u]:
if not visited[v]:
visited[v] = True
parent[v] = u
children[u].append(v)
q.append(v)
down_diameter = [0]*(N+1)
max_depth = [0]*(N+1)
post_order = []
stack = [(root, False)]
while stack:
u, processed = stack.pop()
if processed:
post_order.append(u)
max_d = 0
max1 = -1
max2 = -1
diam = 0
for v in children[u]:
current_depth = max_depth[v] + 1
if current_depth > max1:
max2 = max1
max1 = current_depth
elif current_depth > max2:
max2 = current_depth
if down_diameter[v] > diam:
diam = down_diameter[v]
if max1 + max2 > diam:
diam = max1 + max2
down_diameter[u] = diam
max_depth[u] = max1 if max1 != -1 else 0
else:
stack.append((u, True))
for v in reversed(children[u]):
stack.append((v, False))
up_diameter = [0]*(N+1)
up_depth = [0]*(N+1)
pre_order = deque()
pre_order.append(root)
q = deque([root])
while q:
u = q.popleft()
for v in children[u]:
pre_order.append(v)
q.append(v)
prefix_max_depth = {}
prefix_second_max_depth = {}
prefix_max_down = {}
suffix_max_depth = {}
suffix_second_max_depth = {}
suffix_max_down = {}
for u in pre_order:
child_list = children[u]
k = len(child_list)
if k == 0:
continue
prefix_max_depth[u] = [ -1 ] * (k+1)
prefix_second_max_depth[u] = [ -1 ] * (k+1)
prefix_max_down[u] = [ -1 ] * (k+1)
current_max_depth = -1
current_second_max_depth = -1
current_max_down = -1
for i in range(1, k+1):
v = child_list[i-1]
depth = max_depth[v] + 1
down = down_diameter[v]
if depth > current_max_depth:
current_second_max_depth = current_max_depth
current_max_depth = depth
elif depth > current_second_max_depth:
current_second_max_depth = depth
if down > current_max_down:
current_max_down = down
prefix_max_depth[u][i] = current_max_depth
prefix_second_max_depth[u][i] = current_second_max_depth
prefix_max_down[u][i] = current_max_down
suffix_max_depth[u] = [ -1 ] * (k+1)
suffix_second_max_depth[u] = [ -1 ] * (k+1)
suffix_max_down[u] = [ -1 ] * (k+1)
current_max_depth = -1
current_second_max_depth = -1
current_max_down = -1
for i in range(k-1, -1, -1):
v = child_list[i]
depth = max_depth[v] + 1
down = down_diameter[v]
if depth > current_max_depth:
current_second_max_depth = current_max_depth
current_max_depth = depth
elif depth > current_second_max_depth:
current_second_max_depth = depth
if down > current_max_down:
current_max_down = down
suffix_max_depth[u][i] = current_max_depth
suffix_second_max_depth[u][i] = current_second_max_depth
suffix_max_down[u][i] = current_max_down
for i in range(k):
v = child_list[i]
if k == 1:
max_other_depth = -1
second_other_depth = -1
max_down_other = -1
else:
max_prefix = prefix_max_depth[u][i] if i > 0 else -1
max_suffix = suffix_max_depth[u][i+1] if i+1 < k else -1
max_other_depth = max(max_prefix, max_suffix)
down_prefix = prefix_max_down[u][i] if i > 0 else -1
down_suffix = suffix_max_down[u][i+1] if i+1 < k else -1
max_down_other = max(down_prefix, down_suffix)
if max_prefix == -1 and max_suffix == -1:
max_other_depth = -1
second_other_depth = -1
elif max_prefix > max_suffix:
second_prefix = prefix_second_max_depth[u][i] if i > 0 else -1
second_other_depth = max(second_prefix, max_suffix)
elif max_prefix < max_suffix:
second_suffix = suffix_second_max_depth[u][i+1] if i+1 < k else -1
second_other_depth = max(max_prefix, second_suffix)
else:
second_prefix = prefix_second_max_depth[u][i] if i > 0 else -1
second_suffix = suffix_second_max_depth[u][i+1] if i+1 < k else -1
second_other_depth = max(second_prefix, second_suffix)
a = up_diameter[u]
b = max_down_other if max_down_other != -1 else 0
c = (up_depth[u] + max_other_depth + 1) if max_other_depth != -1 else 0
if max_other_depth == -1:
c = up_depth[u] + 1
d = (max_other_depth + second_other_depth + 2) if (max_other_depth != -1 and second_other_depth != -1) else 0
current_diam = max(a, b, c, d)
up_diameter[v] = current_diam
if max_other_depth == -1:
up_depth_v = up_depth[u] + 1
else:
up_depth_v = max(up_depth[u] + 1, max_other_depth + 1)
up_depth[v] = up_depth_v
min_diam = float('inf')
for u in range(1, N+1):
for v in children[u]:
d1 = down_diameter[v]
d2 = up_diameter[v]
r1 = (d1 + 1) // 2
r2 = (d2 + 1) // 2
candidate = max(d1, d2, r1 + r2 + 1)
if candidate < min_diam:
min_diam = candidate
if N == 2:
print(1)
else:
print(min_diam)
if __name__ == "__main__":
main()