結果
問題 |
No.3206 う し た ウ ニ 木 あ く ん 笑
|
ユーザー |
👑 ![]() |
提出日時 | 2025-07-20 00:58:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 518 ms / 3,000 ms |
コード長 | 1,466 bytes |
コンパイル時間 | 319 ms |
コンパイル使用メモリ | 82,672 KB |
実行使用メモリ | 122,392 KB |
最終ジャッジ日時 | 2025-07-20 00:58:41 |
合計ジャッジ時間 | 9,423 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
import sys from sys import stdin #重みのないグラフでの最短経路問題 #隣接リストと始点を与えると始点からの距離のリスト & 親のリストを返す from collections import deque def NC_Dij(lis,start): ret = [float("inf")] * len(lis) ret[start] = 0 q = deque([start]) plis = [i for i in range(len(lis))] visit = [] while len(q) > 0: now = q.popleft() visit.append(now) for nex in lis[now]: if ret[nex] > ret[now] + 1: ret[nex] = ret[now] + 1 plis[nex] = now q.append(nex) return ret,plis,visit N = int(stdin.readline()) lis = [ [] for i in range(N)] for i in range(N-1): u,v = map(int,stdin.readline().split()) u -= 1 v -= 1 lis[u].append(v) lis[v].append(u) _,plis,visit = NC_Dij(lis,0) visit.reverse() dpc = [1] * N for v in visit: if plis[v] != v: dpc[plis[v]] = max(dpc[plis[v]], dpc[v] + 1) ans = 1 visit.reverse() dpu = [0] * N for v in visit: links = [ dpu[v] ] for nex in lis[v]: if nex == plis[v]: continue links.append( dpc[nex] ) links.sort() links.reverse() for i in range(len(links)): ans = max(ans, 1+(i+1)*links[i]) for nex in lis[v]: if nex == plis[v]: continue cost = (links[0] if links[0]!=dpc[nex] else links[1]) + 1 dpu[nex] = cost print (ans)