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  s 1  t 1  w 1  s 2  t 2  w 2 : s n-1  t n-1  w n-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. s i and t i represent end-points of the i -th edge (undirected) and w i 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 ≤ w i ≤ 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

Solution (Python):
n = int(input())
from collections import defaultdict
from queue import deque
g = defaultdict(list)

d = [float('inf')] * n
visited = [False] * n
d[0] = 0
def bfs(v):
    s = deque([v])
    visited[v] = True
    while len(s) > 0:
        t = s.pop()
        for c,w in g[t]:
            if not visited[c] and d[c] == float('inf'):
                d[c] = d[t] + w
                visited[c] = True
                s.append(c)
for i in range(n-1):
    s,t,w = map(int, input().split())
    g[s].append((t, w))
    g[t].append((s, w))

bfs(0)
mi = 0
md = 0
for i,k in enumerate(d):
    if md < k:
        mi = i
        md = k
d = [float('inf')] * n
visited = [False] * n
d[mi] = 0
bfs(mi)
print(max(d))

Solution (Python):
from collections import defaultdict
import sys
sys.setrecursionlimit(200000)

def dfs(source, used, all_weight, connect):
    max_weight = all_weight
    max_source = source
    used[source] = 1
    for target, weight in connect[source]:
        if not used[target]:
            now_weight = all_weight + weight
            this_source, this_weight = dfs(target, used, now_weight, connect)
            if max_weight < this_weight:
                max_weight = this_weight
                max_source = this_source
    return [max_source, max_weight]

vertice = int(input())
connect = defaultdict(list)
for _ in range(vertice - 1):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight])
    connect[v2].append([v1, weight])
answer = 0
start_v = 0
for i in range(2):
    used = [0 for n in range(vertice)]
    start_v, answer = dfs(start_v, used, 0, connect)
print(answer)

Solution (Python):


from collections import deque


if __name__ == '__main__':

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

    Q = deque()

    def bfs(s):
        d = [float("inf")] * n
        Q.append(s)
        d[s] = 0
        while Q:
            u = Q.popleft()
            for v, w in E[u]:
                if d[v] == float("inf"):
                    d[v] = d[u] + w
                    Q.append(v)

        return d

    d = bfs(0)
    tgt = d.index(max(d))
    d = bfs(tgt)
    print(max(d))

Solution (Python):
from heapq import heappop, heappush

INF = 10 ** 20

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

cost = [INF] * n
que = [(0, 0)]
cost[0] = 0

while que:
  acc, num = heappop(que)
  for weight, to in edges[num]:
    if weight + acc < cost[to]:
      cost[to] = weight + acc
      heappush(que, (weight + acc, to))

max_ind = cost.index(max(cost))
cost = [INF] * n
que = [(0, max_ind)]
cost[max_ind] = 0
while que:
  acc, num = heappop(que)
  for weight, to in edges[num]:
    if weight + acc < cost[to]:
      cost[to] = weight + acc
      heappush(que, (weight + acc, to))

print(max(cost))

Solution (Python):
from heapq import heappop, heappush

INF = 10 ** 20

def main():
  n = int(input())
  edges = [[] for _ in range(n)]
  for _ in range(n - 1):
    s, t, w = map(int, input().split())
    edges[s].append((w, t))
    edges[t].append((w, s))
  
  def func(start):
    cost = [INF] * n
    que = [(0, start)]
    cost[start] = 0
    
    while que:
      acc, num = heappop(que)
      for weight, to in edges[num]:
        if weight + acc < cost[to]:
          cost[to] = weight + acc
          heappush(que, (weight + acc, to))
    return cost
  
  cost1 = func(0)
  max_ind = cost1.index(max(cost1))
  cost2 = func(max_ind)
  
  print(max(cost2))
main()

Solution (Python):
from collections import deque

n = int(input())

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

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

def bfs(s):
    visited = [0]*n
    C = [float("inf")]*n
    queue = deque([(s, 0)])
    visited[s] = 1

    while queue:
        x, c = queue.popleft()
        C[x] = c
        for node, cost in G[x]:
            if visited[node] == 0:
                queue.append((node, c+cost))
                visited[node] = 1
                
    return max(C), C.index(max(C)) 
    
m, index = bfs(0)
ans, index = bfs(index)

print(ans)

Solution (Python):
import queue


def bfs(u):
    state = ['new']*n
    distance = [0]*n
    q = queue.Queue()
    
    state[u] = 'visited'
    distance[u] = 0
    q.put(u)
    
    while not q.empty():
        u = q.get()
        for v in Adj[u]:
            if state[v[0]] == 'new':
                state[v[0]] = 'visited'
                distance[v[0]] = distance[u]+v[1]
                q.put(v[0])
    
    return distance
    


n = int(input())

Adj = [[] for _ 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])

distance = bfs(0)
max_index = 0
max_d = 0
for i in range(n):
    if max_d<distance[i]:
        max_index = i
        max_d = distance[i]
print(max(bfs(max_index)))

Solution (Python):









import os
import sys


from collections import deque


class Graph():
    def __init__(self, vertex):
        self.V = vertex
        self.path = [[] for _ in range(self.V)]
        self.distance = [0] * self.V
        self.Q = deque()

    def addedge(self, s, t, w):
        self.path[s].append([w, t])
        self.path[t].append([w, s])

    def bfs(self, init):
        prev = init
        self.Q.append([init, prev])
        while self.Q:
            u, prev = self.Q.popleft()
            for w, v in self.path[u]:
                if self.distance[u] + w > self.distance[v] and prev != v:
                    self.distance[v] = self.distance[u] + w
                    self.Q.append([v, u])

        return max(self.distance), self.distance.index(max(self.distance))

    def clear(self):
        self.distance = [0] * self.V


def main():
    n = int(input())
    graph = Graph(n)
    for _ in range(n-1):
        s, t, w = map(int, input().split())
        graph.addedge(s, t, w)
    _, nt = graph.bfs(0)
    graph.clear()
    ans, _ = graph.bfs(nt)
    print(ans)


'''
    for init in range(n):
        ans = max(ans, graph.bfs(init))
        graph.clear()
'''
    

if __name__ == "__main__":
    main()

Solution (Python):



def resolve():
    def dfs1(r_topo, par):
        for idx in reversed(r_topo):
            for (to, cost) in G[idx]:
                if to == par[idx]:
                    continue
                dist[idx] = max(dist[idx], dist[to] + cost)

    def dfs2(idx, d_par, par):
        stack = [(idx, d_par, par)]
        while stack:
            idx, d_par, par = stack.pop()
            d_child = []
            d_child.append((0, -1))
            for (to, cost) in G[idx]:
                if to == par:
                    d_child.append((d_par + cost, to))
                else:
                    d_child.append((dist[to] + cost, to))
            d_child.sort(reverse=True)
            ans[idx] = d_child[0][0] + d_child[1][0]
            for (to, cost) in G[idx]:
                if to == par:
                    continue
                nx_d_par = d_child[d_child[0][1] == to][0]
                stack.append((to, nx_d_par, idx))

    N = int(input())
    if N == 1:
        return print(0)

    G = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b, c = map(int, input().split())
        G[a].append((b, c))
        G[b].append((a, c))

    topo = []
    P = [-1] * N
    node = [0]
    while node:
        s = node.pop()
        topo.append(s)
        for (to, cost) in G[s]:
            if to == P[s]:
                continue
            P[to] = s
            node.append(to)

    dist = [0] * N
    ans = [0] * N
    dfs1(topo, P)
    dfs2(0, 0, -1)
    print(max(ans))


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys, threading
sys.setrecursionlimit(1 << 30)
threading.stack_size(1 << 27)


def main():
    n, *E = map(int, open(0).read().split())
    E = zip(*[iter(E)]*3)
    
    G = [[] for _ in [0]*n]
    for s, t, w in E:
        G[s].append((t, w))
        G[t].append((s, w))
    
    def dfs(v, p=-1, d=0):
        maxd = d
        maxv = v
        for u, w in G[v]:
            if u == p:
                continue
            _d, _v = dfs(u, v, d+w)
            if _d > maxd:
                maxd, maxv = _d, _v
        return maxd, maxv
    
    _, v = dfs(n//2)
    ans, _ = dfs(v)
    
    print(ans)


if __name__ == '__main__':
    threading.Thread(target=main).start()

Solution (Python):
from collections import deque

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

INF = 10000000000

def BFS(start):
    D = [INF]*n
    q = deque()
    visited = [False]*n
    q.append(start)
    visited[start] = True
    D[start] = 0
    while q:
        node = q.pop()
        visited[node] = True
        for adj,w in C[node]:
            if D[node] + w < D[adj]:
                D[adj] = D[node] + w
            if not visited[adj]:
                q.append(adj)
    return D

D = BFS(0)
max_ind1 = D.index(max(D))
D = BFS(max_ind1)
print(max(D))

Solution (Python):
import queue

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

INF = float('inf')

def dfs(s):
    dist = [INF] * N
    Q = queue.Queue()
    Q.put(s)
    dist[s] = 0
    while not Q.empty():
        u = Q.get()
        for i in range(len(G[u])):
            if dist[G[u][i][0]] == INF:
                dist[G[u][i][0]] = dist[u] + G[u][i][1]
                Q.put(G[u][i][0])
    return dist

dist = dfs(0)
idx = dist.index(max(dist))
dist = dfs(idx)
print(max(dist))

Solution (Python):
import sys,collections
sys.setrecursionlimit(1000000)
N = int(sys.stdin.readline())

INF = float("inf")

stw = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N-1)) 

G = [{} for _ in range(N)]

for s,t,w in stw:
    G[s][t] = w
    G[t][s] = w

distance = [0]*N
ret = 0

def dfs(c,w,visited):
    if c in visited:
        return
    distance[c] = w
    visited.add(c)
    for to,dw in G[c].items():
        dfs(to,w+dw,visited)

dfs(0,0,set())

i = distance.index(max(distance))
dfs(i,0,set())


print(max(distance))

Solution (Python):
from collections import deque


def bfs(n, adj, source):
	dist = [-1] * n
	dist[source] = 0
	q = deque([source])
	mx = 0
	idx = 0
	while q:
		cur = q.popleft()
		for nxt, d in adj[cur]:
			if dist[nxt] < 0:
				dist[nxt] = dist[cur] + d
				if dist[nxt] > mx:
					mx = dist[nxt]
					idx = nxt
				q.append(nxt)
	return idx, mx


def main():
	n, *L = map(int, open(0).read().split())
	adj = [[] for _ in range(n)]
	for a, b, c in zip(*[iter(L)] * 3):
		adj[a].append((b, c))
		adj[b].append((a, c))
	idx1, _, = bfs(n, adj, 0)
	_, ans, = bfs(n, adj, idx1)
	print(ans)


if __name__ == '__main__':
	main()

Solution (Python):
import sys
import queue


n = int(input())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    s, t, w = map(int, sys.stdin.readline().strip().split())
    tree[s].append((t, w))
    tree[t].append((s, w))


def search(current):
    distance = [0] * n
    foot_print = [False] * n

    que = queue.LifoQueue()
    que.put((current, 0))

    while not que.empty():
        current_node, current_dist = que.get()
        
        distance[current_node] = current_dist
        foot_print[current_node] = True

        for node, dist in tree[current_node]:
            
            if foot_print[node] is True:
                continue
            que.put((node, dist + current_dist))

    return distance


dist = search(0)  
furthest_node = dist.index(max(dist))  
dist = search(furthest_node)  
diameter = max(dist)
print(diameter)

Solution (Python):


def main():
    N = I()
    if N==1:
        print(0)
        return
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        s, t, w = LI()
        V[s].append((t,w))
        V[t].append((s,w))
    dist = [0]*N

    def dfs1(start,parent):
        for i,w in V[start]:
            if i==parent:
                continue
            dfs1(i,start)
            dist[start] = max(dist[start],dist[i]+w)
        return
    def dfs2(s,d_p,p):
        child = [(0,-1)]
        for i,w in V[s]:
            if i==p:
                child.append((d_p+w,i))
            else:
                child.append((w+dist[i],i))
        child.sort(reverse=True)
        rep = child[0][0] + child[1][0]
        for i,w in V[s]:
            if i==p:
                continue
            rep = max(rep,dfs2(i,child[child[0][1]==i][0],s))
        return rep
    dfs1(N//2,-1)
    
    ans = dfs2(N//2,0,-1)
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    main()

"""


"""

Solution (Python):
import sys
input = sys.stdin.readline


def dfs(V, start):
    q = [(start, 0)]
    used = [False] * (n+1)
    farthest = 0
    pos = 0

    while q:
        s, cost = q.pop()
        if farthest < cost:
            pos = s
            farthest = cost
        used[s] = True
        for t, c in V[s].items():
            if used[t]:
                continue
            q.append((t, cost + c))
    
    return farthest, pos


if __name__ == "__main__":
    n = int(input())
    V = {i:dict() for i in range(n)}

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

    print(dfs(V, dfs(V, 0)[1])[0])

Solution (Python):
import sys
from collections import deque
sys.setrecursionlimit(10**7)


def BFS(s):
    color=["white" for _ in range(n)]
    D=[float("inf") for _ in range(n)]

    color[s]="gray"
    D[s]=0
    queue=deque([s])

    while len(queue)!=0:
        u=queue.popleft()
        for i,j in M[u]:
            if color[i]=="white":
                queue.append(i)
                color[i]="gray"
                D[i]=D[u]+j
        color[u]="black"

    return max(enumerate(D), key=lambda x:x[1])


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

add,ans=BFS(0)
print(max(ans,BFS(add)[1]))

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

sys.setrecursionlimit(100001)


class Edge:
    def __init__(self,arg_to,arg_dist):
        self.to = arg_to
        self.dist = arg_dist

V = int(input())
G = [[] for _ in range(V)]

for _ in range(V-1):
    from_,to_,dist_ = map(int,input().split())
    G[from_].append(Edge(to_,dist_))
    G[to_].append(Edge(from_,dist_))

ans = 0

def recursive(node_id,parent):
    max_path1 = 0
    max_path2 = 0

    global ans

    for edge in G[node_id]:
        if edge.to == parent:
            continue
        tmp_dist = edge.dist+recursive(edge.to,node_id)
        if tmp_dist > max_path1:
            max_path2 = max_path1
            max_path1 = tmp_dist
        elif tmp_dist > max_path2:
            max_path2 = tmp_dist

    ans = max(ans,max_path1+max_path2)
    return max_path1

recursive(V//2,-1)
print("%d"%(ans))

Solution (Python):
import sys
input = sys.stdin.readline

class Tree():
    def __init__(self,n,edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0]].append((e[1],e[2]))
            self.tree[e[1]].append((e[0],e[2]))

    def setroot(self,root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.distance = [None for _ in range(self.n)]
        self.distance[root] = 0
        stack = [root]
        while stack:
            node = stack.pop()
            for adj,cost in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node]+1
                    self.distance[adj] = self.distance[node]+cost
                    stack.append(adj)

    def diam(self):
        u = self.distance.index(max(self.distance))
        dist_u = [None for _ in range(N)]
        dist_u[u] = 0
        stack = [u]
        while stack:
            node = stack.pop()
            for adj,cost in self.tree[node]:
                if dist_u[adj] is None:
                    dist_u[adj] = dist_u[node]+cost
                    stack.append(adj)
        return max(dist_u)

N = int(input())
E = [list(map(int,input().split())) for _ in range(N-1)]

t = Tree(N,E)
t.setroot(0)

print(t.diam())

Solution (Python):
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()

Solution (Python):
def tree_diameter(T, w):
    N = len(T)
    v = 0
    def dfs(r):
        depth = [-1] * N 
        stack = [(r, -1, 0)] 
        d = 0 
        while stack:
            v, p, st = stack.pop()
            if st == 0: 
                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: 
                    d -= (0 if p == -1 else w[p][v])
            elif st == 1: 
                continue
            else: 
                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)

Solution (Python):
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()

Solution (Python):



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())

Solution (Python):
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()

Solution (Python):
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

sys.setrecursionlimit(100001)


class Edge:
    def __init__(self,arg_to,arg_dist):
        self.to = arg_to
        self.dist = arg_dist

V = int(input())
G = [[] for _ in range(V)]

for _ in range(V-1):
    from_,to_,dist_ = map(int,input().split())
    G[from_].append(Edge(to_,dist_))
    G[to_].append(Edge(from_,dist_))

ans = 0

def recursive(node_id,parent):
    max_path1 = 0
    max_path2 = 0

    global ans

    for edge in G[node_id]:
        if edge.to == parent:
            continue
        tmp_dist = edge.dist+recursive(edge.to,node_id)
        if tmp_dist > max_path1:
            max_path2 = max_path1
            max_path1 = tmp_dist
        elif tmp_dist > max_path2:
            max_path2 = tmp_dist

    ans = max(ans,max_path1+max_path2)
    return max_path1

recursive(V//2,-1)
print("%d"%(ans))

Solution (Python):





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


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))

Solution (Python):
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)

Solution (Python):
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 
		self.w = w 


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): 
		s, t, w = map(int, input().split())
		G[s].append(Edge(t, w))
		G[t].append(Edge(s, w))
	ans = solve()
	print(ans)

Solution (Python):
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])

Solution (Python):
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))

Solution (Python):
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)]  

    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)  
    ans, _ = dfs(ln)  
    print(ans)