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):
import sys
sys.setrecursionlimit(10**6)

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


def dfs(n):
    visited = [False] * N
    stack = [[n, 0]]
    longest = [-1, -1]

    while stack:
        node, weight = stack.pop()
        if visited[node]:
            continue
        visited[node] = True
        if longest[1] < weight:
            longest = [node, weight]

        for n, w in G[node]:
            if not visited[n]:
                stack.append([n, w + weight])

    return longest


xn, xw = dfs(0)
yn, yw = dfs(xn)
print(yw)

Solution (Python):




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):
        visited = [False] * graph.v
        weights = [0] * graph.v
        stack = [(s, 0)]
        while stack:
            v, weight = stack.pop()
            if not visited[v]:
                visited[v] = True
                weights[v] = weight
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        stack.append((w, weight + e.weight))
        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()

Solution (Python):




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):
        visited = [False] * graph.v
        weights = [0] * graph.v
        stack = [(s, 0)]
        while stack:
            v, weight = stack.pop()
            if not visited[v]:
                visited[v] = True
                weights[v] = weight
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        stack.append((w, weight + e.weight))
        return weights

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


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

Solution (Python):


import sys
from heapq import heappop, heappush

sys.setrecursionlimit(10 ** 9)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
INF=float('inf')


def dijkstra(N: int, nodes: list, src: int) -> list:
    
    
    res = [float('inf')] * N
    
    que = [(0, src)]
    res[src] = 0
    
    while len(que) != 0:
        
        dist, cur = heappop(que)
        
        for nxt, cost in nodes[cur]:
            
            if res[cur] + cost < res[nxt]:
                res[nxt] = res[cur] + cost
                
                heappush(que, (res[nxt], nxt))
    
    return res

N=INT()
nodes=[[] for i in range(N)]
for i in range(N-1):
    u,v,w=MAP()
    nodes[u].append((v, w))
    nodes[v].append((u, w))

res=dijkstra(N, nodes, 0)
x=res.index(max(res))
res=dijkstra(N, nodes, x)
print(max(res))

Solution (Python):
def solve(prev, r, dic):
    d = 0
    t = r
    stack = []
    stack += [[prev, r, d]]
    while stack:
        prev, r, d1 = stack.pop(-1)
        if r in dic:
            for vtx, cost in dic[r]:
                if vtx == prev:
                    continue
                stack += [[r, vtx, d1 + cost]]
                if d < d1 + cost:
                    d = d1 + cost
                    t = vtx
    return d, t

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]]
r1, t1 = solve(-1, 0, edge)
r2, t2 = solve(-1, t1, edge)
print(r2)

Solution (Python):
def postorder(g):
    parent_stack = []
    dfs_stack = [(0, None)]            
    while dfs_stack:
        u, prev = dfs_stack.pop()
        dfs_stack.extend((t, u) for d, t in g[u])
        while parent_stack and parent_stack[-1] != prev:
            yield parent_stack.pop()
        parent_stack.append(u)
    while parent_stack:
        yield parent_stack.pop()

from sys import stdin
from collections import defaultdict
readline = stdin.readline

n = int(readline())
g = defaultdict(list)
for _ in range(n - 1):
    s, t, d = map(int, readline().split())
    g[s].append((d, t))
diameter = [0]
dp = [0] * n
for i in postorder(g):
    if len(g[i]) == 0:
        continue
    candidate = sorted(d + dp[t] for d, t in g[i])
    dp[i] = candidate[-1]
    diameter.append(dp[i] if len(candidate) == 1 else sum(candidate[-2:]))

print(max(diameter))

Solution (Python):
def dfs(root):
    visited = [False] * n
    queue = [(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


n = int(input())

edges = [set() for _ in range(n)]

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

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

Solution (Python):


import sys

f_i = sys.stdin

n = int(f_i.readline())

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

for l_i in f_i:
    s, t, w = map(int, l_i.split())
    edges[s].append((t, w))
    edges[t].append((s, w))



import collections

def tree_walk(start, switch = 0):
    path = collections.deque()
    path.append(start)

    weight = collections.deque()
    weight.append(0)
    
    unvisited = [True] * n
    unvisited[start] = False
    
    rest = n - 1
    end_point = start
    diameter = 0
    
    while True:
        u = path[-1]
        for v, w in edges[u]:
            if unvisited[v]:
                path.append(v)
                unvisited[v] = False
                rest -= 1
                weight.append(w)
                break

        if u == path[-1]:
            distance = sum(weight)
            if diameter < distance:
                diameter = distance
                end_point = u
            if rest == 0:
                break
            path.pop()
            weight.pop()

    if switch:
        print(diameter)
    else:
        return end_point



tree_walk(tree_walk(0), 1)

Solution (Python):



"""
input:
4
0 1 2
1 2 1
1 3 3

output:
5
"""

import sys
from collections import deque
from math import isinf


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = map(int, each)
        init_adj_table[v_from][v_to] = edge_weight
        init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def graph_bfs(v_init):
    global distance
    distance = [float('inf')] * vertices
    distance[v_init] = 0
    queue.appendleft(v_init)

    while queue:
        current = queue.popleft()
        adj_weight = adj_table[current]
        for adj in adj_weight.keys():
            if isinf(distance[adj]):
                distance[adj] = distance[current] + adj_weight[adj]
                queue.append(adj)
    return None


def solve():
    graph_bfs(init_v)
    max_v, bridge_v = 0, 0
    for i in range(vertices):
        if isinf(distance[i]):
            continue
        if max_v < distance[i]:
            max_v = distance[i]
            bridge_v = i

    graph_bfs(bridge_v)
    max_v = 0
    for j in range(vertices):
        if isinf(distance[j]):
            continue
        max_v = max(max_v, distance[j])

    return max_v


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices = int(_input[0])
    v_info = map(lambda x: x.split(), _input[1:])

    queue = deque()
    distance = [float('inf')] * vertices

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)

    init_v = 0
    print(solve())

Solution (Python):



"""
input:
4
0 1 2
1 2 1
1 3 3

output:
5
"""

import sys
from collections import deque
from math import isinf


def generate_adj_table(v_table):
    for each in v_table:
        v_from, v_to, edge_weight = map(int, each)
        init_adj_table[v_from][v_to] = edge_weight
        init_adj_table[v_to][v_from] = edge_weight

    return init_adj_table


def graph_bfs(v_init):
    global distance
    distance = [float('inf')] * vertices
    distance[v_init] = 0
    queue.appendleft(v_init)

    while queue:
        current = queue.popleft()
        adj_weight = adj_table[current]
        for adj in adj_weight.keys():
            if isinf(distance[adj]):
                distance[adj] = distance[current] + adj_weight[adj]
                queue.append(adj)
    return None


def solve():
    graph_bfs(init_v)
    diameter, bridge_v = 0, 0
    for v in range(vertices):
        if isinf(distance[v]):
            continue
        if diameter < distance[v]:
            diameter = distance[v]
            bridge_v = v

    graph_bfs(bridge_v)
    diameter = 0
    for v in range(vertices):
        if isinf(distance[v]):
            continue
        diameter = max(diameter, distance[v])

    return diameter


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices = int(_input[0])
    v_info = map(lambda x: x.split(), _input[1:])

    queue = deque()
    distance = [float('inf')] * vertices

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)

    init_v = 0
    print(solve())

Solution (Python):



"""
input:
4
0 1 2
1 2 1
1 3 3

output:
5
"""

import sys
from collections import deque
from math import isinf


def generate_adj_table(v_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source].setdefault(target, cost)
        init_adj_table[target].setdefault(source, cost)

    return init_adj_table


def graph_bfs(v_init):
    global distance
    distance = [float('inf')] * vertices
    distance[v_init] = 0
    queue.appendleft(v_init)

    while queue:
        current = queue.popleft()
        adj_weight = adj_table[current]
        for adj in adj_weight.keys():
            if isinf(distance[adj]):
                distance[adj] = distance[current] + adj_weight[adj]
                queue.append(adj)
    return None


def solve():
    graph_bfs(init_v)
    diameter, bridge_v = 0, 0
    for v in range(vertices):
        if isinf(distance[v]):
            continue
        if diameter < distance[v]:
            diameter = distance[v]
            bridge_v = v

    graph_bfs(bridge_v)
    diameter = 0
    for v in range(vertices):
        if isinf(distance[v]):
            continue
        diameter = max(diameter, distance[v])

    return diameter


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    vertices = int(_input[0])
    v_info = map(lambda x: x.split(), _input[1:])

    queue = deque()
    distance = [float('inf')] * vertices

    init_adj_table = tuple(dict() for _ in range(vertices))
    adj_table = generate_adj_table(v_info)

    init_v = 0
    print(solve())

Solution (Python):



"""
input:
4
0 1 2
1 2 1
1 3 3

output:
5
"""

import sys
from math import isinf
from collections import deque


def generate_adj_table(v_table, init_adj_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
        init_adj_table[target][source] = cost

    return init_adj_table


def graph_bfs(current, v_num, adj_table):
    queue = deque()
    distance = [float('inf')] * v_num
    distance[current] = 0
    queue.appendleft(current)

    while queue:
        current = queue.popleft()
        for adj, cost in adj_table[current].items():
            if isinf(distance[adj]):
                distance[adj] = distance[current] + cost
                queue.append(adj)
    return distance


def calc_tree_diameter(v_num, adj_table):
    
    init_v = 0
    distance_1 = graph_bfs(init_v, v_num, adj_table)
    diameter, bridge_v = 0, 0
    for v, dis_1 in enumerate(distance_1):
        if isinf(dis_1):
            continue
        elif diameter < dis_1:
            diameter = dis_1
            bridge_v = v

    
    distance_2 = graph_bfs(bridge_v, v_num, adj_table)
    diameter = 0
    for dis_2 in distance_2:
        if isinf(dis_2):
            continue
        diameter = max(diameter, dis_2)

    return diameter


def solve():
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    edges = map(lambda x: x.split(), _input[1:])

    init_adj_table = tuple(dict() for _ in range(v_num))
    adj_table = generate_adj_table(edges, init_adj_table)
    ans = calc_tree_diameter(v_num, adj_table)
    print(ans)
    return None


if __name__ == '__main__':
    solve()

Solution (Python):



"""
input:
4
0 1 2
1 2 1
1 3 3

output:
5
"""

import sys
from math import isinf
from collections import deque


def generate_adj_table(v_table, init_adj_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
        init_adj_table[target][source] = cost

    return init_adj_table


def graph_bfs(current, v_num, adj_table):
    queue = deque()
    distance = [float('inf')] * v_num
    distance[current] = 0
    queue.appendleft(current)

    while queue:
        current = queue.popleft()
        for adj, cost in adj_table[current].items():
            if isinf(distance[adj]):
                distance[adj] = distance[current] + cost
                queue.append(adj)
    return distance


def calc_tree_diameter(v_num, adj_table):
    
    init_v = 0
    distance_1 = graph_bfs(init_v, v_num, adj_table)
    diameter, bridge_v = 0, 0
    for v, dis_1 in enumerate(distance_1):
        if isinf(dis_1):
            continue
        elif diameter < dis_1:
            diameter = dis_1
            bridge_v = v

    
    distance_2 = graph_bfs(bridge_v, v_num, adj_table)
    diameter = 0
    for dis_2 in distance_2:
        if isinf(dis_2):
            continue
        diameter = max(diameter, dis_2)

    return diameter


def solve():
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    edges = map(lambda x: x.split(), _input[1:])

    init_adj_table = tuple(dict() for _ in range(v_num))
    adj_table = generate_adj_table(edges, init_adj_table)
    ans = calc_tree_diameter(v_num, adj_table)
    print(ans)
    return None


if __name__ == '__main__':
    solve()

Solution (Python):



"""
input:
4
0 1 2
1 2 1
1 3 3

output:
5
"""

import sys
from math import isinf
from collections import deque


def generate_adj_table(v_table, init_adj_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
        init_adj_table[target][source] = cost

    return init_adj_table


def graph_bfs(current, v_num, adj_table):
    queue = deque()
    distance = [float('inf')] * v_num
    distance[current] = 0
    queue.appendleft(current)

    while queue:
        current = queue.popleft()
        for adj, cost in adj_table[current].items():
            if isinf(distance[adj]):
                distance[adj] = distance[current] + cost
                queue.append(adj)
    return distance


def calc_tree_diameter(v_num, adj_table):
    
    init_v = 0
    distance_1 = graph_bfs(init_v, v_num, adj_table)
    diameter, bridge_v = 0, 0
    for v, dis_1 in enumerate(distance_1):
        if isinf(dis_1):
            continue
        elif diameter < dis_1:
            diameter = dis_1
            bridge_v = v

    
    distance_2 = graph_bfs(bridge_v, v_num, adj_table)
    diameter = 0
    for dis_2 in distance_2:
        if isinf(dis_2):
            continue
        diameter = max(diameter, dis_2)

    return diameter


def solve():
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    edges = map(lambda x: x.split(), _input[1:])

    init_adj_table = tuple(dict() for _ in range(v_num))
    adj_table = generate_adj_table(edges, init_adj_table)
    ans = calc_tree_diameter(v_num, adj_table)
    print(ans)
    return None


if __name__ == '__main__':
    solve()

Solution (Python):



"""
input:
4
0 1 2
1 2 1
1 3 3

output:
5
"""

import sys
from math import isinf
from collections import deque


def generate_adj_table(v_table, init_adj_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
        init_adj_table[target][source] = cost

    return init_adj_table


def graph_bfs(current, v_num, adj_table):
    queue = deque()
    distance = [float('inf')] * v_num
    distance[current] = 0
    queue.appendleft(current)

    while queue:
        current = queue.popleft()
        for adj, cost in adj_table[current].items():
            if isinf(distance[adj]):
                distance[adj] = distance[current] + cost
                queue.append(adj)
    return distance


def calc_tree_diameter(v_num, adj_table):
    
    init_v = 0
    distance_1 = graph_bfs(init_v, v_num, adj_table)
    diameter, bridge_v = 0, 0
    for v, dis_1 in enumerate(distance_1):
        if isinf(dis_1):
            continue
        elif diameter < dis_1:
            diameter = dis_1
            bridge_v = v

    
    distance_2 = graph_bfs(bridge_v, v_num, adj_table)
    diameter = 0
    for dis_2 in distance_2:
        if isinf(dis_2):
            continue
        diameter = max(diameter, dis_2)

    return diameter


def solve():
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    edges = map(lambda x: x.split(), _input[1:])

    init_adj_table = tuple(dict() for _ in range(v_num))
    adj_table = generate_adj_table(edges, init_adj_table)
    ans = calc_tree_diameter(v_num, adj_table)
    print(ans)
    return None


if __name__ == '__main__':
    solve()

Solution (Python):



"""
input:
4
0 1 2
1 2 1
1 3 3

output:
5
"""

import sys
from math import isinf
from collections import deque


def generate_adj_table(v_table, init_adj_table):
    for each in v_table:
        source, target, cost = map(int, each)
        init_adj_table[source][target] = cost
        init_adj_table[target][source] = cost

    return init_adj_table


def graph_bfs(current, v_num, adj_table):
    queue = deque()
    distance = [float('inf')] * v_num
    distance[current] = 0
    queue.appendleft(current)

    while queue:
        current = queue.popleft()
        for adj, cost in adj_table[current].items():
            if isinf(distance[adj]):
                distance[adj] = distance[current] + cost
                queue.append(adj)
    return distance


def calc_tree_diameter(v_num, adj_table):
    
    init_v = 0
    distance_1 = graph_bfs(init_v, v_num, adj_table)
    d1, bridge_v = 0, 0
    for v, each in enumerate(distance_1):
        if isinf(each):
            continue
        elif d1 < each:
            d1 = each
            bridge_v = v

    
    distance_2 = graph_bfs(bridge_v, v_num, adj_table)
    d2 = 0
    for each in distance_2:
        if isinf(each):
            continue
        d2 = max(d2, each)

    return d2


def solve():
    _input = sys.stdin.readlines()
    v_num = int(_input[0])
    edges = map(lambda x: x.split(), _input[1:])

    init_adj_table = tuple(dict() for _ in range(v_num))
    adj_table = generate_adj_table(edges, init_adj_table)
    ans = calc_tree_diameter(v_num, adj_table)
    print(ans)
    return None


if __name__ == '__main__':
    solve()

Solution (Python):


import sys
import os
import pprint
from queue import Queue

"""Diameter of Tree"""





class Edge:
    def __init__(self, to, weight):
        self.to = to
        self.weight = weight

    def __str__(self):
        return '{} {}'.format(self.to, self.weight)


N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    start, end, weight = list(map(int, input().split()))

    
    edge = Edge(end, weight)
    G[start].append(edge)

    
    edge = Edge(start, weight)
    G[end].append(edge)



def bfs(index):
    d = [float('inf')] * N
    visited = [False] * N
    queue = Queue()
    queue.put(index)
    d[index] = 0

    while not queue.empty():
        u = queue.get()
        visited[u] = True

        for edge in G[u]:
            if d[u] + edge.weight < d[edge.to]:
                d[edge.to] = d[u] + edge.weight
            if not visited[edge.to]:
                queue.put(edge.to)

    max_i = 0
    max_d = 0
    for i in range(N):
        if max_d < d[i]:
            max_i = i
            max_d = d[i]
    
    return max_i, max_d


temp_i, temp_d = bfs(0)

temp_i, temp_d = bfs(temp_i)


print(temp_d)

Solution (Python):


import sys
import os
import pprint
from queue import Queue

"""Diameter of Tree"""





class Edge:
    def __init__(self, to, weight):
        self.to = to
        self.weight = weight

    def __str__(self):
        return '{} {}'.format(self.to, self.weight)


N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    start, end, weight = list(map(int, input().split()))

    
    edge = Edge(end, weight)
    G[start].append(edge)

    
    edge = Edge(start, weight)
    G[end].append(edge)



def bfs(index):
    d = [float('inf')] * N
    visited = [False] * N
    queue = Queue()
    queue.put(index)
    d[index] = 0

    while not queue.empty():
        u = queue.get()
        visited[u] = True

        for edge in G[u]:
            if d[u] + edge.weight < d[edge.to]:
                d[edge.to] = d[u] + edge.weight
            if not visited[edge.to]:
                queue.put(edge.to)

    max_i = 0
    max_d = 0
    for i in range(N):
        if max_d < d[i]:
            max_i = i
            max_d = d[i]
    
    return max_i, max_d


temp_i, temp_d = bfs(0)

temp_i, temp_d = bfs(temp_i)


print(temp_d)

Solution (Python):
import heapq as pq
inf = float("inf")
n = int(input())
M = [[] for i in range(n)]

for i in range(n-1):
    s,t,d = map(int, input().split())
    M[s].append([t,d])
    M[t].append([s,d])
  
def dijkstra(s):
    color = [0] * n
    d = [inf] * n
    d[s] = 0
    
    H =[]
    pq.heappush(H, [0, s])
    while len(H) != 0:
        u2,u1 = pq.heappop(H)
        color[u1] = 1
        if d[u1] < u2:
            continue
        for v1,v2 in M[u1]:
            if color[v1] == 1: continue

            if d[u1] + v2 < d[v1]:
                d[v1] = d[u1] + v2
                pq.heappush(H, [d[v1], v1])
    return d
  
d = dijkstra(0)
r = d.index(max(d))
d = dijkstra(r)
print(max(d))

Solution (Python):
from collections import deque
n = input()
G = [[] for i in xrange(n)]
for i in xrange(n-1):
    s, t, w = map(int, raw_input().split())
    G[s].append((t, w))
    G[t].append((s, w))

deq = deque()
def bfs(s):
    used = {s: 0}
    deq.append(s)
    while deq:
        s = deq.popleft()
        for t, w in G[s]:
            if t in used:
                continue
            used[t] = used[s] + w
            deq.append(t)
    return used.items()[used.values().index(max(used.values()))]
t, co = bfs(0)
print bfs(t)[1]

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
from math import isinf
INF = float("inf")
sys.setrecursionlimit(200000)
n = int(readline())
G = [[] for _ in range(n)]
D = [INF] * n
for _ in [0] * (n - 1):
    s, t, w = map(int, readline().split())
    G[s].append([t, w])
    G[t].append([s, w])
def bfs(s, D):
    dq = deque([s])
    D = [INF] * n
    D[s] = 0
    while dq:
        u = dq.popleft()
        for i in range(len(G[u])):
            e = G[u][i]
            if isinf(D[e[0]]):
                D[e[0]] = D[u] + e[1]
                dq.append(e[0])
    return D
D = bfs(0, D)
maxv = 0
tgt = 0
for i in range(n):
    if isinf(D[i]): continue
    if maxv < D[i]:
        maxv = D[i]
        tgt = i
D = bfs(tgt, D)
maxv = 0
for i in range(n):
    if isinf(D[i]): continue
    maxv = max(maxv, D[i])
print(maxv)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
from math import isinf
INF = float("inf")
sys.setrecursionlimit(200000)
n = int(readline())
G = [[] for _ in range(n)]
D = [INF] * n
for _ in [0] * (n - 1):
    s, t, w = map(int, readline().split())
    G[s].append([t, w])
    G[t].append([s, w])
def bfs(s, D):
    dq = deque([s])
    D = [INF] * n
    D[s] = 0
    while dq:
        u = dq.popleft()
        for i in range(len(G[u])):
            e = G[u][i]
            if isinf(D[e[0]]):
                D[e[0]] = D[u] + e[1]
                dq.append(e[0])
    return D
D = bfs(0, D)
maxv = 0
tgt = 0
for i in range(n):
    if isinf(D[i]): continue
    if maxv < D[i]:
        maxv = D[i]
        tgt = i
D = bfs(tgt, D)
print(max(D[i] for i in range(n) if not isinf(D[i])))

Solution (Python):
import sys
readline = sys.stdin.readline
def dfs(root):
    visited = [False] * n
    queue = [(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
n = int(readline())
edges = [set() for _ in range(n)]
for _ in range(n - 1):
    s, t, w = map(int, readline().split())
    edges[s].add((w, t))
    edges[t].add((w, s))
_, ln = dfs(0)
ld, _ = dfs(ln)
print(ld)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
def dfs(root):
    visited = [False] * n
    queue = deque([(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
n = int(readline())
edges = [set() for _ in range(n)]
for _ in range(n - 1):
    s, t, w = map(int, readline().split())
    edges[s].add((w, t))
    edges[t].add((w, s))
_, ln = dfs(0)
ld, _ = dfs(ln)
print(ld)

Solution (Python):
import sys
readline = sys.stdin.readline
from collections import deque
def dfs(root):
    visited = [False] * n
    queue = deque([(0, root)])
    longest = (-1, -1)
    while queue:
        total_weight, node = queue.popleft()
        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
n = int(readline())
edges = [set() for _ in range(n)]
for _ in range(n - 1):
    s, t, w = map(int, readline().split())
    edges[s].add((w, t))
    edges[t].add((w, s))
_, ln = dfs(0)
ld, _ = dfs(ln)
print(ld)

Solution (Python):
import sys
readline = sys.stdin.readline
def dfs(root):
    visited = [False] * n
    queue = [(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))
        queue.extend((total_weight + w, t) for w, t in edges[node] if not visited[t])
    return longest
n = int(readline())
edges = [set() for _ in range(n)]
for _ in range(n - 1):
    s, t, w = map(int, readline().split())
    edges[s].add((w, t))
    edges[t].add((w, s))
_, ln = dfs(0)
ld, _ = dfs(ln)
print(ld)

Solution (Python):
import sys
readline = sys.stdin.readline
def dfs(root):
    visited = [False] * n
    queue = [(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))
        queue += [(total_weight + w, t) for w, t in edges[node] if not visited[t]]
    return longest
n = int(readline())
edges = [set() for _ in range(n)]
for _ in range(n - 1):
    s, t, w = map(int, readline().split())
    edges[s].add((w, t))
    edges[t].add((w, s))
_, ln = dfs(0)
ld, _ = dfs(ln)
print(ld)

Solution (Python):



import heapq
from collections import defaultdict

INF = float('inf')
N = int(input())
Adj_list = defaultdict(set)

for i in range(N-1):
    s, t, w = map(int, input().split())
    Adj_list[s].add((t, w))
    Adj_list[t].add((s, w))
    
def dijkstra(x, vertex):
    d = [INF] * x
    d[vertex] = 0
    hq = [(0, vertex)]
    
    while hq:
        u = heapq.heappop(hq)[1]
        for (v, c) in Adj_list[u]:
            if d[v] > d[u] + c:
                d[v] = d[u] + c
                heapq.heappush(hq, (d[u]+c, v))

    return d


l_0 =  dijkstra(N, 0)
x = l_0.index(max(l_0))
l_x = dijkstra(N, x)
print(max(l_x))