Submission #6216205

---

Source Code Expand

# 木グラフの直径
import sys
input = sys.stdin.readline
from scipy.sparse import *

N = int(input())
edge = [[] for _ in range(N)]
for _ in range(N-1):
  a,b = map(lambda x: int(x)-1, input().split())
  edge[a].append(b)
  edge[b].append(a)
  
def dijkstra(start):
  dist = [None] * N
  dist[start] = 0
  q = [start]
  d = 0
  while q:
    d += 1
    qq = []
    for x in q:
      for y in edge[x]:
        if dist[y] is not None:
          continue
        dist[y] = d
        qq.append(y)
    q = qq
  return dist

dist = dijkstra(0)
x = dist.index(max(dist))
dist = dijkstra(x)
y = dist.index(max(dist))
print(x+1,y+1)

Submission Info

Judge Result