結果
問題 | No.806 木を道に |
ユーザー |
![]() |
提出日時 | 2024-09-03 00:57:41 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,098 bytes |
コンパイル時間 | 425 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 97,212 KB |
最終ジャッジ日時 | 2024-09-03 00:57:48 |
合計ジャッジ時間 | 7,084 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 9 WA * 18 |
ソースコード
from collections import deque, defaultdictdef tree_diameter(n: int, adj: defaultdict) -> tuple[int, int, int]:def bfs(start):q = deque([start])dists = [-1] * ndists[start] = 0while q:v = q.popleft()for to in adj[v]:if dists[to] != -1: continuedists[to] = dists[v] + 1q.append(to)return max((d, i) for i, d in enumerate(dists))_, a = bfs(0)diam, b = bfs(a)return a, b, diamN = int(input())adj = defaultdict(list)degs = [0] * Nfor _ in range(N-1):a, b = map(lambda x: int(x)-1, input().split())adj[a].append(b)adj[b].append(a)degs[a] += 1degs[b] += 1u, v, _ = tree_diameter(N, adj)# 頂点 u, v 以外の次数 1 の頂点を取り除くq = deque()for i in range(N):if i == u or i == v: continueif degs[i] == 1:q.append(i)ans = 0while q:v = q.popleft()ans += 1degs[v] -= 1for to in adj[v]:degs[to] -= 1if degs[to] == 1:q.append(to)print(ans)