結果

問題 No.3206 う　し　た　ウ　ニ　木　あ　く　ん　笑
ユーザー dp_ijk
提出日時 2025-07-18 22:45:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,061 ms / 3,000 ms
コード長 3,054 bytes
コンパイル時間 453 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 160,640 KB
最終ジャッジ日時 2025-07-18 22:46:08
合計ジャッジ時間 15,750 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

def rerooting(X_f, X_unit, pull, put, T, *, subtree=False):
   N = len(T)
   root = T.root
   root_to_leaf = T.root_to_leaf
   pi = T.pi

   dp = [X_unit]*N

   floated = [X_unit]*N

   lower_sum = [X_unit]*N

   for v in reversed(root_to_leaf):
      if v == root:
         continue
      p = pi[v]

      dp[v] = put(v, lower_sum[v])
      floated[v] = pull(p, v, dp[v])
      lower_sum[p] = X_f(lower_sum[p], floated[v])

   topdown = [X_unit]*N
   for v in root_to_leaf:
      adj = T.T
      prefix = topdown[v]
      for a in adj[v]:
         topdown[a] = prefix
         prefix = X_f(prefix, floated[a])

      suffix = X_unit
      for a in reversed(adj[v]):
         topdown[a] = X_f(topdown[a], suffix)
         suffix = X_f(floated[a], suffix)

         topdown[a] = put(v, topdown[a])

         topdown[a] = pull(a, v, topdown[a])

   return topdown

import typing
INF = typing.cast(int, float("INF"))

def solve(N, G):
   T = Tree(G, 0)
   H2 = rerooting(max, -INF, lambda v, a, sm: sm+1, lambda v, sm: max(0, sm), T)
   H2 = [x-1 for x in H2]

   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

   def proc(X):
      X = [x+1 for x in X if x != -INF]
      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(H2[v])
      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)


def naive(N, G):
   res = 1
   for r in range(N):
      T = Tree(G, r)
      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
      tmp = [H[v] for v in T[r]]
      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
      res = max(res, proc(tmp))
   return res


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