트리의 지름

박현주#00002026. 05. 24. AM 02:5420
```py import sys input = sys.stdin.readline V = int(input()) g = [[] for _ in range(V+1)] for _ in range(V): arr = list(map(int,input().split())) x = arr[0] for i in range(1,len(arr)-1,2): y, w = arr[i], arr[i+1] g[x].append((y,w)) print(g) visit = [False]*(V+1) order = [] ch = [[] for _ in range(V+1)] s = [1] while s: x = s.pop() if visit[x]: continue visit[x] = True order.append(x) for y, w in g[x]: if visit[y]: continue s.append(y) ch[x].append((y,w)) print(ch) dist = [0]*(V+1) diam = [0]*(V+1) while order: x = order.pop() d = [] for y, w in ch[x]: d.append(dist[y]+w) diam[x] = max(diam[x], diam[y]) d.sort(reverse=True) if len(ch[x]) == 0: continue elif len(ch[x]) == 1: dist[x] = d[0] else: dist[x] = d[0] diam[x] = max(diam[x], d[0]+d[1]) print(dist) print(diam) print(max(dist[1], diam[1])) ```

댓글 0

댓글 불러오는 중...

댓글을 작성하려면 로그인 해주세요.