Problem:


Diameter of a Tree

Given a tree T with non-negative weight, find the diameter of the tree.

The diameter of a tree is the maximum distance between two nodes in a tree.

Input

n
s1 t1 w1
s2 t2 w2
:
sn-1 tn-1 wn-1

The first line consists of an integer n which represents the number of nodes in the tree. Every node has a unique ID from 0 to n-1 respectively.

In the following n-1 lines, edges of the tree are given.

si and ti represent end-points of the i-th edge (undirected) and wi represents the weight (distance) of the i-th edge.

Output

Print the diameter of the tree in a line.

Constraints

 1 ≤ n ≤ 100,000
	

 0 ≤ wi ≤ 1,000
	

Sample Input 1

4
0 1 2
1 2 1
1 3 3

Sample Output 1

5

Sample Input 2

4
0 1 1
1 2 2
2 3 4

Sample Output 2

7



Sample input:
4
0 1 2
1 2 1
1 3 3


Sample output:
5

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush, heappushpop, heapreplace


def diameter(tonodes, n):
    visited = [False for _ in range(n)]
    queue = []
    max_weight = 0
    max_node = 0
    for i, node in enumerate(tonodes):
        if len(node) > 0:
            visited[i] = True
            max_node = i
            for edge in node:
                heappush(queue, (-edge[0], edge[1]))
            break

    while len(queue) > 0:
        weight, node = heappop(queue)
        visited[node] = True
        if max_weight < -weight:
            max_weight = -weight
            max_node = node
        for edge in tonodes[node]:
            if not visited[edge[1]]:
                heappush(queue, (weight - edge[0], edge[1]))

    for i in range(n):
        visited[i] = False

    visited[max_node] = True

    for edge in tonodes[max_node]:
        heappush(queue, (-edge[0], edge[1]))

    max_weight = 0

    while len(queue) > 0:
        weight, node = heappop(queue)
        visited[node] = True
        if max_weight < -weight:
            max_weight = -weight
            max_node = node
        for edge in tonodes[node]:
            if not visited[edge[1]]:
                heappush(queue, (weight - edge[0], edge[1]))

    return max_weight


def main():
    n = int(input())
    tonodes = [[] for _ in range(n)]
    for _ in range(n - 1):
        s, t, w = map(int, input().split())
        tonodes[s].append((w, t))
        tonodes[t].append((w, s))
    max_weight = diameter(tonodes, n)
    print(max_weight)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def tree_diameter(T, w):
    N = len(T)
    v = 0
    def dfs(r):
        depth = [-1] * N # the depth of each vertex
        stack = [(r, -1, 0)] # (vertex, parent, status)
        d = 0 # current depth
        while stack:
            v, p, st = stack.pop()
            if st == 0: # visited v for the first time
                d += (0 if p == -1 else w[p][v])
                depth[v] = d
                n_children = 0
                for u in T[v]:
                    if depth[u] >= 0:
                        continue
                    if n_children == 0:
                        stack += [(v, p, 2), (u, v, 0)]
                        n_children += 1
                    else:
                        stack += [(v, p, 1), (u, v, 0)]
                        n_children += 1
                if n_children == 0: # v is a leaf
                    d -= (0 if p == -1 else w[p][v])
            elif st == 1: # now searching
                continue
            else: # search finished
                d -= (0 if p == -1 else w[p][v])
        return depth
    
    dist = dfs(v)
    u, _ = max(enumerate(dist), key=lambda x: x[1])
    dist = dfs(u)
    v, d = max(enumerate(dist), key=lambda x: x[1])
    return (u, v), d

INF = float('inf')
N = int(input())
E = [[] for _ in range(N)]
weight = [{} for _ in range(N)]
for _ in range(N-1):
    s, t, w = map(int, input().split())
    E[s].append(t); E[t].append(s)
    weight[s].setdefault(t, w); weight[t].setdefault(s, w)
_, d = tree_diameter(E, weight)
print(d)

Submission status: Accepted

Solution code:
class Edge:
    def __init__(self, dst, weight):
        self.dst, self.weight = dst, weight

    def __lt__(self, e):
        return self.weight > e.weight


class Graph:
    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class TreeDiameter:
    def __init__(self, graph: Graph) -> None:
        self.graph = graph
        self.diameter = None
        self.fathest_pair = None

    def run(self):
        _, v1 = self.calc_farthest(0, -1)
        diameter, v2 = self.calc_farthest(v1, -1)
        self.diameter = diameter
        self.fathest_pair = (v1, v2)
        return diameter

    def calc_farthest(self, target: int, par: int = -1):
        dists = [None] * self.graph.V
        stack = [(target, par)]

        while stack:
            v, par = stack[-1]
            if dists[v] is None:
                dists[v] = (0, v)
                for child in self.graph.E[v]:
                    if child.dst == par:
                        continue
                    stack.append((child.dst, v))
            else:
                stack.pop()
                ret_dist, ret_v = dists[v]
                for child in self.graph.E[v]:
                    if child.dst == par:
                        continue
                    cand_dist, cand_v = dists[child.dst]
                    if cand_dist + child.weight > ret_dist:
                        ret_dist = cand_dist + child.weight
                        ret_v = cand_v
                dists[v] = (ret_dist, ret_v)

        return dists[target]


def aoj():
    N = int(input())
    graph = Graph(N)
    for _ in range(N-1):
        s, t, w = map(int, input().split())
        graph.add_edge(s, t, w)
        graph.add_edge(t, s, w)
    diam = TreeDiameter(graph)
    print(diam.run())


if __name__ == "__main__":
    aoj()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import queue

INF = 2000000000

class Edge:
    def __init__(self, to, weight, val):
        self.val = val
        self.to = to
        self.weight = weight
        
def bfs(s):
    global d
    d = [INF] * n
    Q.put(s)
    d[s] = 0
    
    while not Q.empty():
        u = Q.get()
        for i in range(len(G[u])):
            e = G[u][i]
            
            if d[e.to] == INF:
                d[e.to] = d[u] + e.weight
                Q.put(e.to)


def solve():
    bfs(0)
    
    tgt = 0
    maxv = 0
    for i in range(n):
        if d[i] == INF:
            continue
        if maxv < d[i]:
            maxv = d[i]
            tgt = i
    bfs(tgt)
    
    maxv = 0
    for i in range(n):
        if d[i] == INF:
            continue
        if maxv < d[i]:
            maxv = d[i]
    return maxv

n = int(input())

G = [[] for j in range(n)]
d = [INF] * n
for i in range(n-1):
    nums=list(map(int,input().split()))
    G[nums[0]].append(Edge(nums[1], nums[2], i))
    G[nums[1]].append(Edge(nums[0], nums[2], i))
Q = queue.Queue()
print(solve())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
G = []
class Edge:
    def __init__(self, to, w):
        self.to = to
        self.w = w

def dfs(s, d, fr, dist):
    dist[s] = d
    for edge in G[s]:
        if edge.to != fr:
            dfs(edge.to, d + edge.w, s, dist)


def main():
    global G
    n = int(input().strip())
    G = [[] for _ in range(n)]
    d1 = [0] * n
    d2 = [0] * n
    for i in range(n-1):
        s, t, w = map(int, input().strip().split())
        G[s].append(Edge(t, w))
        G[t].append(Edge(s, w))
    dfs(0, 0, -1, d1)
    j = d1.index(max(d1))
    dfs(j, 0, -1, d2)
    print(max(d2))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/all/GRL_5_A
# 全点間の距離を求めているとO(n**2)でパソコンが爆発する。
# P354はO(n)のシンプルなアルゴリズム。
# 厳密な証明は知らないけど、直感的に良さそう

from collections import deque, defaultdict
Tree = defaultdict(lambda: [])

# input data
N = int(input())
for _ in range(N - 1):
    s, t, w = list(map(int, input().split()))
    Tree[s].append((t, w))
    Tree[t].append((s, w))


def bfs(Tree, n_V, s):
    '''
    指定した点sからの単一始点で各点までの距離を返す。
    n_Vは頂点の数
    Treeはdefault dictで、valueには(隣接ノード,そこまでのコスト)がリスト形式で格納されているとする。
    '''
    INF = 10**9
    Dists = [INF] * n_V  # 距離の初期化 #こいつを更新して返すことにする
    is_visited = [False] * n_V
    is_visited[s] = True
    que = deque([(s, 0)])  # (ノード番号,そこまでたどり着くためのコスト)
    while que:
        cur, cost = que.popleft()
        Dists[cur] = cost
        for nx_node, nx_cost in Tree[cur]:
            if is_visited[nx_node]:
                continue
            que.append((nx_node, nx_cost + cost))
            is_visited[nx_node] = True

    return Dists


# 任意の点から一番遠い点を求めて、そこからさらに一番遠い点がほしい
Dists = bfs(Tree, N, 0)
next_node = Dists.index(max(Dists))
Dists = bfs(Tree, N, next_node)

print(max(Dists))

Submission status: Accepted

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    s, t, w = map(int, input().split())
    G[s].append((t, w))
    G[t].append((s, w))

from collections import deque
def bfs(s):
    dist = [None]*N
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w, c in G[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + c
            que.append(w)
    d = max(dist)
    return dist.index(d), d
u, _ = bfs(0)
v, d = bfs(u)

print(d)

Submission status: Accepted

Solution code:
from typing import List, Deque
from collections import deque

INF = 1 << 89

# 重み付き枝（隣接リストで表現）
class Edge:
	def __init__(self, t: int, w: int) -> None:
		self.t = t # to vertex t
		self.w = w # weight w

# Treeに対してbfs（閉路を気にしなくてよい）
def bfs(s: int) -> List[int]:
	d: List[int] = [INF for _ in range(n)]
	Q: Deque[int] = deque()
	Q.append(s)
	d[s] = 0
	while len(Q) > 0:
		u = Q.popleft()
		for e in G[u]:
			if d[e.t] == INF:
				d[e.t] = d[u] + e.w
				Q.append(e.t)
	return d

def solve() -> int:
	d: List[int] = bfs(0)
	maxv: int = 0
	tgt: int = 0
	for i in range(n):
		if d[i] == INF:
			continue
		if maxv < d[i]:
			maxv = d[i]
			tgt = i
	d = bfs(tgt)
	maxv = 0
	for i in range(n):
		if d[i] == INF:
			continue
		maxv = max(maxv, d[i])
	return maxv

if __name__ == "__main__":
	n = int(input())
	G: List[Edge] = [[] for _ in range(n)]
	for _ in range(n - 1): # 木の枝数は（節点数 - 1）
		s, t, w = map(int, input().split())
		G[s].append(Edge(t, w))
		G[t].append(Edge(s, w))
	ans = solve()
	print(ans)

Submission status: Accepted

Solution code:
from  collections import deque

n = int(input())

E = [[] for _ in range(n)]

for _ in range(n-1):
    s,t,w =map(int, input().split( ))
    E[s].append([t,w])
    E[t].append([s,w])

r = 0

Q = deque()
Q.append(r)
Done = [0 for _ in range(n)]

Dist = [0 for _ in range(n)]

while Q:
    v = Q.popleft()
    Done[v] = 1
    for e in E[v]:
        if not Done[e[0]]:
            Dist[e[0]] = Dist[v] + e[1]
            Q.append(e[0])
            Done[e[0]] = 1
u = 0

for v in range(n):
    if Dist[u] < Dist[v]:
        u = v

Q = deque()
Q.append(u)
Done = [0 for _ in range(n)]
Dist = [0 for _ in range(n)]

while Q:
    v = Q.popleft()
    Done[v] = 1
    for e in E[v]:
        if not Done[e[0]]:
            Dist[e[0]] = Dist[v] + e[1]
            Q.append(e[0])
            Done[e[0]] = 1

u = 0

for v in range(n):
    if Dist[u] < Dist[v]:
        u = v
print(Dist[u])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9 + 7)

  
def dfs1(pos, par):
    """その頂点の部分木内で最も遠い頂点(葉)までの距離を求める""" 
    for next_pos, cost in graph[pos]:
        if next_pos == par:
            continue
        dfs1(next_pos, pos)
        distance1[pos] = max(distance1[pos], distance1[next_pos] + cost)
    return


def dfs2(pos, dist_par, par):
    """全方位木DP""" 
    tmp = [(0, -1), (0, -1)]
    for next_pos, cost in graph[pos]:
        if next_pos == par:
            tmp.append((dist_par + cost, next_pos))
        else:
            tmp.append((cost + distance1[next_pos], next_pos))
    tmp = sorted(tmp, reverse = True)
    distance2[pos] = tmp[0][0] + tmp[1][0]
    for next_pos, cost in graph[pos]: 
        if next_pos == par:
            continue
        else:
            if tmp[0][1] != next_pos:
                dfs2(next_pos, tmp[0][0], pos)
            else:
                dfs2(next_pos, tmp[1][0], pos)
    

n = int(input())
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
for i in range(n-1):
    a, b, cost = info[i]
    graph[a].append((b, cost))
    graph[b].append((a, cost))

distance1 = [0]*n
distance2 = [0]*n
dfs1(0, -1)
dfs2(0, 0, -1)
print(max(distance2))

Submission status: Accepted

Solution code:
from collections import deque
from typing import Tuple


def dfs(root: int) -> Tuple[int, int]:
    global edges
    visited = [False] * n
    queue: deque = deque()
    queue.append((0, root))
    longest = (-1, -1)

    while queue:
        total_weight, node = queue.pop()
        if visited[node]:
            continue
        visited[node] = True
        longest = max(longest, (total_weight, node))
        for w, t in edges[node]:
            if not visited[t]:
                queue.append((total_weight + w, t))

    return longest


if __name__ == "__main__":
    n = int(input())
    edges = [set() for _ in range(n)]  # type: ignore

    for _ in range(n - 1):
        s, t, w = map(lambda x: int(x), input().split())
        edges[s].add((w, t))
        edges[t].add((w, s))

    _, ln = dfs(0)  # Find the deepest node.
    ans, _ = dfs(ln)  # Traverse from the deepest node.
    print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop


def input(f):
    n, = map(int, f.readline().split())
    s = [None for _ in range(n-1)]
    t = [None for _ in range(n-1)]
    w = [None for _ in range(n-1)]
    for i in range(n-1):
        s[i], t[i], w[i] = map(int, f.readline().split())
    return n, s, t, w


def solve(n, s, t, w):
    graph = [[] for _ in range(n)]
    def add_edge(src, dst, w):
        graph[src].append((dst, w))
        graph[dst].append((src, w))
    for i in range(n-1):
        add_edge(s[i], t[i], w[i])
    
    queue = []
    def find(root):
        INF = 100000 * 1000 + 1;
        best = [INF for _ in range(n)]
        best[root] = 0
        while queue:
            _, cur_v = heappop(queue)
            for nxt_v, nxt_w in graph[cur_v]:
                dist = best[cur_v] + nxt_w
                if dist < best[nxt_v]:
                    best[nxt_v] = dist
                    heappush(queue, (dist, nxt_v))
                    
        res = (0, root)
        for i in range(n):
            if best[i] > res[0]:
                res = (best[i], i)
        return res
        
    heappush(queue, (0, 0))
    ret = find(0)
    heappush(queue, (0, ret[1]))
    res = find(ret[1])
    
    return res[0]

with open('/dev/stdin') as f:
    print(solve(*input(f)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)

from heapq import heappop, heappush

def input(f):
    n, = map(int, f.readline().split())
    s = [None for _ in range(n-1)]
    t = [None for _ in range(n-1)]
    w = [None for _ in range(n-1)]
    for i in range(n-1):
        s[i], t[i], w[i] = map(int, f.readline().split())
    return n, s, t, w

def solve(n, s, t, w):
    g = [[] for _ in range(n)]
    for i in range(n-1):
        g[s[i]].append((t[i], w[i]))
        g[t[i]].append((s[i], w[i]))

    def find(root):
        best = (0, root)
        q = []
        heappush(q, best)

        inf = 10**8+1
        dist = [inf for _ in range(n)]
        dist[root] = 0
        while q:
            cur = heappop(q)
            for nxt in g[cur[1]]:
                if cur[0] + nxt[1] < dist[nxt[0]]:
                    dist[nxt[0]] = cur[0] + nxt[1]
                    heappush(q, (cur[0] + nxt[1], nxt[0]))

        for i in range(n):
            if dist[i] != inf and dist[i] > best[0]:
                best = (dist[i], i)
        return best

    ret1 = find(0)
    ret2 = find(ret1[1])
    return ret2[0]

with open('/dev/stdin') as f:
    print(solve(*input(f)))

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_A&lang=jp
def diameter(N, E, D):#diamete of a tree
    from collections import deque
    V = [-1]*N
    V[0] = 0
    q = deque([0])
    while q:
        v = q.popleft()
        for w in E[v]:
            if V[w] == -1:
                V[w] = V[v] + D[(v,w)]
                q.append(w)
    s = V.index( max(V))
    p = deque([s])
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.popleft()
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + D[(v,w)]
                p.append(w)
    return max(W)

from collections import defaultdict
N = int( input())
E = [ [] for _ in range(N)]
D = defaultdict( int)
for _ in range(N-1):
    a, b, w = map( int, input().split())
    E[a].append(b)
    E[b].append(a)
    D[(a,b)] = D[(b,a)] = w
print( diameter( N, E, D))

Submission status: Accepted

Solution code:
from collections import deque


class Graph:
    # クラス変数
    WHITE = 0
    GRAY = 1

    def __init__(self):
        self.color = [self.__class__.WHITE] * n
        self.out = deque([])
        self.Q = deque([])

    def bfs(self, s, w):
        self.Q.appendleft((s, w))
        self.color[s] = self.__class__.GRAY
        while self.Q:
            u, w = self.Q.popleft()

            self.out.append((u, w))

            for v, dw in G[u]:
                if self.color[v] == self.__class__.WHITE:
                    self.color[v] = self.__class__.GRAY
                    self.Q.append((v, dw+w))


n = int(input())
G = {}
for i in range(n):
    G[i] = []
for i in range(1, n):
    s, t, w = map(int, input().split())
    G[s].append((t, w))
    G[t].append((s, w))

# 最も遠い点xを求める
graph = Graph()
graph.bfs(0, 0)
x, w = max(graph.out, key=lambda x: x[1])

# xから最も遠い点yを求める
graph = Graph()
graph.bfs(x, 0)
y, w = max(graph.out, key=lambda x: x[1])

# x, yの距離が答え
print(w)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

n = int(input())
e = [[] for _ in range(n)]
weights = {}
for i in range(n-1):
    s, t, w = map(int, input().split())
    e[s].append(t)
    e[t].append(s)
    weights[(s, t)] = w
    weights[(t, s)] = w


def dfs(v, d, visited):
    r = [d, v]
    visited[v] = True
    for tv in e[v]:
        if not visited[tv]:
            r = max([dfs(tv, d+weights[(v, tv)], visited), r])
    return r


def fartheast(v):
    visited = [False]*n
    return dfs(v, 0, visited)


def diameter(a, b, d, visited):
    visited[a] = True
    for tv in e[a]:
        if not visited[tv]:
            td = diameter(tv, b, d+weights[(a, tv)], visited)
            if td > 0:
                return td
    return d if a == b else 0


xd, x = fartheast(0)
yd, y = fartheast(x)
print(yd)

Submission status: Accepted

Solution code:
import heapq
from sys import stdin

def read_graph(n):
    A = [ [] for _ in range(n) ]
    while True:
        try:
            line = stdin.readline().strip().split()
            u = line[0]
            v = line[1]
            w = line[2]
            A[int(u)].append((int(v), int(w)))
            A[int(v)].append((int(u), int(w)))
        except:
            break
    return A

def dijkstra(n, A, s):
    color = [ 'WHITE' for i in range(n) ]
    d = [ float('inf') for i in range(n) ]
    d[s] = 0
    pq = []

    heapq.heappush(pq, (0, s))

    while pq:
        costu, u = heapq.heappop(pq)
        color[u] = 'BLACK'

        if d[u] < costu:
            continue

        for v, costv in A[u]:
            if color[v] != 'BLACK':
                if d[u] + costv < d[v]:
                    d[v] = d[u] + costv
                    color[v] = 'GRAY'
                    heapq.heappush(pq, (d[v], v))
    return d

n = int(input())
A = read_graph(n)
a = dijkstra(n, A, 0)
b = dijkstra(n, A, a.index(max(a)))
print(max(b))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(int(1e7))

n = int(input())

graph = {}

for i in range(n-1):
    s, t, w = map(int, input().split())
    if s not in graph:
        graph[s] = {}
    graph[s][t] = w
    if t not in graph:
        graph[t] = {}
    graph[t][s] = w

visited = set()


def visit(v):
    visited.add(v)
    if v not in graph:
        return (0, v)

    costs = []
    for t, w in graph[v].items():
        if t in visited:
            continue
        cost, d = visit(t)
        costs.append((cost + w, d))

    return max(costs) if len(costs) > 0 else (0, v)


_, u = visit(0)
visited.clear()
cost, _ = visit(u)

print(cost)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
import math
import bisect
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

# 1:shortest path
# 1_A
"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
                print(dist, q)
    return dist

v,e,r = map(int, input().split(" "))
adj = [[] for i in range(v)]
for i in range(e):
    s,t,d = map(int, input().split(" "))
    adj[s].append([t, d])
lis = dijkstra(v, r)
print(lis)
for i in lis:
    print(str(i).upper())
"""

# 1_B
"""
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
                if dist[k] > dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
                    if i == num-1:
                        return False
        if not update:
            break
    return dist

v,e,r = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t,d = map(int, input().split(" "))
    adj.append([s, t, d])
lis = bellman_ford(v, r)
if not lis:
    print("NEGATIVE CYCLE")
else:
    for i in lis:
        print(str(i).upper())
"""

# 1_C
"""
def warshallfloyd(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i]+d[i][k])
v,e = map(int, input().split())
d = [[float("inf") for j in range(v)] for i in range(v)]
for i in range(v):
    d[i][i] = 0
for i in range(e):
    s, t, c = map(int, input().split())
    d[s][t] = c
warshallfloyd(v)
for i in range(v):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        quit()
for i in d:
    for j in range(v):
        if j < v-1:
            print(str(i[j]).upper(), end = " ")
        else:
            print(str(i[j]).upper())
"""

# 2:spanning tree
# 2_A
"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
v,e = LI()
c = LIR(e)
c.sort(key = lambda x:x[2])
par = [i for i in range(v)]
rank = [0 for i in range(v)]
k = 0
ans = 0
for a,b,w in c:
    if not same(a,b):
        k += 1
        unite(a,b)
        ans += w
    if k == v-1:
        break
print(ans)
"""

#2_B
"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank(x) < rank(y):
        par[x] = y
    else:
        par[y] = x
        if rank(x) == rank(y):
            rank[x] += 1
"""

#3:connected components
#3_A

#3_B

#3_C


#4:path/cycle
#4_A
"""
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
            if dist[k] > dist[j] + l:
                dist[k] = dist[j] + l
                update = True
                if i == num-1:
                    return False
        if not update:
            break
    return True

v, e = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t = map(int, input().split(" "))
    adj.append([s, t, -1])
for i in range(v):
    if not bellman_ford(v,i):
        print(1)
        quit()
print(0)
"""

#4_B


#5:tree
#5_A
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = II()
adj = [[] for i in range(n)]
for i in range(n-1):
    s,t,w = LI()
    adj[s].append([t, w])
    adj[t].append([s, w])
d = dijkstra(n,0)
i = d.index(max(d))
d2 = dijkstra(n,i)
print(max(d2))

#5_B
"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = int(input())
adj = [[] for i in range(n)]
for i in range(n-1):
    s, t, w = map(int, input().split(" "))
    adj[s].append([t, w])
    adj[t].append([s, w])
for i in range(n):
    s = dijkstra(n,i)
    print(max(s))
"""
#5_C

#5_D

#5_E


#6
#6_A

#6_B


#7
#7_A

Submission status: Accepted

Solution code:
class Node():
    def __init__(self, key):
        self.key = key
        self.passed = False
        self.adj = []

    def __repr__(self):
        return "Node({}, {}, {})".format(
            self.key,
            [(a.key, w) for a, w in self.adj])


def read_inputs():
    n = int(input())
    T = [Node(i) for i in range(n)]
    for _ in range(n - 1):
        s, t, w = [int(x) for x in input().split()]
        T[s].adj.append((T[t], w))
        T[t].adj.append((T[s], w))
    return T


def furthest(T, s):

    for v in T:
        v.passed = False
    fur = -1
    fur_v = None
    S = []
    S.append((s, 0))

    while S != []:
        v, vr = S.pop()
        if vr > fur:
            fur = vr
            fur_v = v
        v.passed = True
        for a, w in v.adj:
            if not a.passed:
                S.append((a, vr + w))

    return fur, fur_v


def tree_diameter(T):
    fur, s2 = furthest(T, T[0])
    fur, fur_v = furthest(T, s2)
    return fur


def main():
    T = read_inputs()
    r = tree_diameter(T)
    print(r)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(root):
  isVisited = [False] * n
  queue = [(0, root)]
  # print('queue is', queue)
  longest = (-1, -1)

  while queue:
    total_weight, node = queue.pop()
    if isVisited[node]:
      continue
    isVisited[node] = True
    longest = max(longest, (total_weight, node))
    # print("longest is", longest)
    for w, t in edges[node]:
      if not isVisited[t]:
        queue.append((total_weight + w, t))

  return longest

n = int(input())

edges =[[] for i in range(n)]

for i in range(n-1):
  s,t,w = map(int, input().split())
  edges[s].append((w, t))
  edges[t].append((w, s))

_, ln = dfs(0)
# print("ln", ln)
ld, _ = dfs(ln)
# print("ld", ld)
print(ld)

Submission status: Accepted

Solution code:
from collections import deque

INFTY = 1 << 30

class Edge:
    def __init__(self, t, w):
        self.t = t
        self.w = w


def bfs(s, n, g):
    d = [INFTY] * n
    q = deque()
    q.append(s)
    d[s] = 0
    while len(q) != 0:
        u = q.popleft()
        for i in range(len(g[u])):
            e = g[u][i]
            if d[e.t] == INFTY:
                d[e.t] = d[u] + e.w
                q.append(e.t)
    return d


def solve(n, g):
    d = bfs(0, n, g)
    maxv = 0
    tgt = 0
    for i in range(n):
        if d[i] == INFTY:
            continue
        if maxv < d[i]:
            maxv = d[i]
            tgt = i

    d = bfs(tgt, n, g)
    maxv = 0
    for i in range(n):
        if d[i] == INFTY:
            continue
        maxv = max(maxv, d[i])

    print(maxv)




if __name__ == '__main__':
    n = int(input())
    g = [[] for i in range(n)]
    for i in range(n - 1):
        s, t, w = [int(v) for v in input().split()]
        g[s].append(Edge(t, w))
        g[t].append(Edge(s, w))
    solve(n, g)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# GRL_5_A: Tree - Diameter of a Tree


class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class WeightedEdge(Edge):
    __slots__ = ('v', 'w', 'weight')

    def __init__(self, v, w, weight):
        super().__init__(v, w)
        self.weight = weight


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


def diameter(graph):
    def dfs(s):
        def _dfs(v, weight):
            if not visited[v]:
                visited[v] = True
                weights[v] = weight
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        _dfs(w, weight + e.weight)

        visited = [False] * graph.v
        weights = [0] * graph.v
        _dfs(s, 0)
        return weights

    v0 = 0
    ws0 = dfs(v0)
    v1 = max((wg, v) for v, wg in enumerate(ws0))[1]
    ws1 = dfs(v1)
    v2 = max((wg, v) for v, wg in enumerate(ws1))[1]

    return max(ws0[v2], ws1[v2])


def run():
    n = int(input())
    g = Graph(n)

    for _ in range(n-1):
        s, t, w = [int(i) for i in input().split()]
        g.add(WeightedEdge(s, t, w))

    print(diameter(g))


if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
from heapq import heappush, heappop

INF =  10000000000

def dijkstra(r, v, dic):
    dp = []
    q = []
    dp = [INF] * v
    dp[r] = 0
    heappush(q, (0, r))
    while q:
        cost, vtx = heappop(q)
        if dp[vtx] < cost:
            continue
        for vtx1, cost1 in dic[vtx]:
            if cost + cost1 < dp[vtx1]:
                dp[vtx1] = cost + cost1
                heappush(q, (cost + cost1, vtx1))
    return dp

dp = []
line = input()
n = int(line)
edge = {}
for _ in range(0, n - 1):
    line = input()
    s, t, d = list(map(int, line.split()))
    if s not in edge:
        edge[s] = [[t, d]]
    else:
        edge[s] += [[t, d]]
    if t not in edge:
        edge[t] = [[s, d]]
    else:
        edge[t] += [[s, d]]
diam = []
dp = dijkstra(0, n, edge)
i = [j for j, x in enumerate(dp) if x == max(dp)]
dp = dijkstra(i[0], n, edge)
diam = max(dp[i] if dp[i] != INF else 0 for i in range(0, n))
print(diam)