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

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

Solution (Python):

def diameter(N, E, D):
    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))

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


graph = Graph()
graph.bfs(0, 0)
x, w = max(graph.out, key=lambda x: x[1])


graph = Graph()
graph.bfs(x, 0)
y, w = max(graph.out, key=lambda x: x[1])


print(w)

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

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

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

Solution (Python):

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



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


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


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



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


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











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






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


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

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

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):
def dfs(root):
  isVisited = [False] * n
  queue = [(0, root)]
  
  longest = (-1, -1)

  while queue:
    total_weight, node = queue.pop()
    if isVisited[node]:
      continue
    isVisited[node] = True
    longest = max(longest, (total_weight, node))
    
    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)

ld, _ = dfs(ln)

print(ld)

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