結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
コンテスト
ユーザー dp_ijk
提出日時 2025-07-18 22:04:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,004 bytes
コンパイル時間 821 ms
コンパイル使用メモリ 82,044 KB
実行使用メモリ 143,904 KB
最終ジャッジ日時 2025-07-18 22:04:41
合計ジャッジ時間 11,889 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

def solve(N, G):
   T = Tree(G, 0)
   H = [0]*N
   for v in reversed(T.root_to_leaf):
      if len(T[v]) == 0:
         continue
      H[v] = max(H[a] for a in T[v]) + 1

   from itertools import accumulate

   temp = [H[v] for v in T[0]]
   pref = list(accumulate(temp, func=max, initial=0))
   suff = list(accumulate(temp[::-1], func=max, initial=0))
   for id, v in enumerate(T[0]):
      temp[id] = max(pref[id], suff[len(temp) - (id+1)])

   memo = [-1]*N
   for id, v in enumerate(T[0]):
      memo[v] = temp[id]

   for v in T.root_to_leaf:
      if v == 0: continue
      if memo[v] == -1:
         memo[v] = memo[T.pi[v]]

   def proc(X):
      X = [x+1 for x in X]
      X.sort(reverse=True)
      res = 0
      for v in range(len(X)):
         res = max(res, X[v] * (v+1))
      return res+1

   cands = []
   cands.append(proc([H[v] for v in T[0]]))

   for v in T.root_to_leaf:
      if v == 0: continue
      X = [H[a] for a in T[v]]
      X.append(T.depth[v] + memo[v] - 1)
      cands.append(proc(X))

   return max(cands)


class Tree:
   def __init__(self, G, root):
      self.N = N = len(G)
      self.T = T = [[] for v in range(N)]
      self.root = root
      self.pi = pi = [-1]*N
      self.depth = depth = [-1]*N
      self.subtree_size = subtree_size = [1]*N
      depth[root] = 0
      Q = [root]
      for v in Q:
         for a in G[v]:
            if depth[a] == -1:
               depth[a] = depth[v] + 1
               T[v].append(a)
               pi[a] = v
               Q.append(a)
      self.root_to_leaf = Q

      for v in reversed(Q):
         if v == root:
            continue
         subtree_size[pi[v]] += subtree_size[v]

   def __getitem__(self, v):
      return self.T[v]

   def __repr__(self):
      return repr(self.T)

   def __len__(self):
      return len(self.T)


N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
   a, b = map(lambda x: int(x) - 1, input().split())
   G[a].append(b)
   G[b].append(a)

ans = solve(N, G)
print(ans)
0