Submission #24633674

---

Source Code Expand

import sys
from collections import defaultdict, deque

def main(f):
  N = int(f.readline())
  link_from = [[] for _ in range(N+1)]
  link_count = [None] + [0] * (N)
  for _ in range(1, N):
    a, b = map(int, f.readline().split())
    link_from[a].append(b)
    link_from[b].append(a)
    link_count[a] += 1
    link_count[b] += 1

  dp = [0] * (N+1)
  flag = [False] * (N+1)

  q = deque()
  for n in range(1, N+1):
    if link_count[n] == 1:
      q.append(n)

  result = 0
  while q:
    #print(dp)
    a = q.pop()
    flag[a] = True
    find = False
    for b in link_from[a]:
      if not flag[b]:
        find = True
        break
    if not find:
      break
    result = max(result, dp[b] + dp[a] + 2)
    dp[b] = max(dp[b], dp[a]+1)
    link_count[b] -= 1
    if link_count[b] == 1:
      q.append(b)

  print(result)

main(sys.stdin)

Submission Info

Judge Result