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: Wrong Answer

Solution code:
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 tree_diameter(T):
    def dfs(n):
        visited = [False] * N
        stack = [T[0][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 T[node]:
                if not visited[n]:
                    stack.append([n, w + weight])

        return longest

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

    return yn, yw


n, w = tree_diameter(G)
print(w)

Submission status: Wrong Answer

Solution code:
INF = 999999999999

def BellmanFord(s, v, edge):
    dp = [INF] * v
    dp[s] = 0
    for i in range(0, v):
        dp1 = dp[:]
        for fr, to, d in edge:
            if dp[fr] == INF:
                continue
            if dp[to] > dp[fr] + d:
                dp[to] = dp[fr] + d
                if i == v - 1:
                    return -1
        if dp == dp1:
            break
    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()))
    edge += [[s, t, - d]]
diam = 0
for s in range(0, n - 1):
    dp = BellmanFord(s, n, edge)
    diam = max(max(- dp[i] if dp[i] != INF else 0 for i in range(0, n)), diam)
print(diam)

Submission status: Wrong Answer

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
        if vtx not in dic:
            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 s != 0:
        if t not in edge:
            edge[t] = [[s, d]]
        else:
            edge[t] += [[s, d]]
diam = []
for t, d in edge[0]:
    dp = dijkstra(t, n, edge)
    diam += [d + max(dp[i] if dp[i] != INF else 0 for i in range(0, n))]
print(sum(sorted(diam)[-2::]))

Submission status: Wrong Answer

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)]
print(dp, i)
dp = dijkstra(i[0], n, edge)
diam = max(dp[i] if dp[i] != INF else 0 for i in range(0, n))
print(diam)

Submission status: Wrong Answer

Solution code:
# Acceptance of input

import sys

f_i = sys.stdin

n = int(f_i.readline())

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

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

# Tree Walk and Output

distance = [0] * n

def tree_walk(u, d, p):
    for v, e in enumerate(edges[u]):
        if e and v != p:
            c_d = d + e
            distance[v] = c_d
            tree_walk(v, c_d, u)

tree_walk(0, 0, None)

end_point = distance.index(max(distance))

tree_walk(end_point, 0, None)

print(max(distance))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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 x(random node) -> bridge vertex
    init_v = 0
    distance_1 = graph_bfs(init_v, v_num, adj_table)
    d1, bridge_v = 0, 0
    for v, dis_1 in enumerate(distance_1):
        if isinf(dis_1):
            continue
        elif d1 < dis_1:
            d1 = dis_1
            bridge_v = v

    # bridge vertex -> y
    # distance_2 = graph_bfs(bridge_v, v_num, adj_table)
    # d2 = 0
    # for dis_2 in distance_2:
    #     if isinf(dis_2):
    #         continue
    #     d2 = max(d2, dis_2)

    return d1


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

Submission status: Wrong Answer

Solution code:
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)]
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):
    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 = bfs(max([i for i in range(n) if not isinf(D[i]) and 0 < D[i]]))
print(max(D[i] for i in range(n) if not isinf(D[i])))

Submission status: Wrong Answer

Solution code:
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)]
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):
    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)
tgt = max([i for i in range(n) if not isinf(D[i]) and 0 < D[i]])
D = bfs(tgt)
print(max(D[i] for i in range(n) if not isinf(D[i])))

Submission status: Wrong Answer

Solution code:
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

d = [float('inf')] * n
visited = [False] * n
d[mi] = 0
bfs(mi)
print(max(d))

Submission status: Time Limit Exceeded

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
        if vtx not in dic:
            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 = 0
for s in range(0, n - 1):
    dp = dijkstra(s, n, edge)
    diam = max(max(dp[i] if dp[i] != INF else 0 for i in range(0, n)), diam)
print(diam)

Submission status: Time Limit Exceeded

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
        if vtx not in dic:
            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]]
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)

Submission status: Time Limit Exceeded

Solution code:
# Acceptance of input

import sys

f_i = sys.stdin

n = int(f_i.readline())

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

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

# dfs tree walk 1

import collections

path = collections.deque()
path.append(0)

distance = 0
max_distance = 0

end_point = 0

unvisited = [False] + [True] * (n - 1)

while True:
    u = path[-1]
    adj_e = edges[u]
    for v, e in enumerate(adj_e):
        if unvisited[v] and e != None:
            path.append(v)
            distance += e
            unvisited[v] = False
            if max_distance < distance:
                max_distance = distance
                end_point = v
            break
    if u == path[-1]:
        path.pop()
        if path:
            distance -= edges[u][path[-1]]
        else:
            break

# Measurement of diameter(dfs tree walk 2)

path.append(end_point)

distance = 0
diameter = 0

unvisited = [True] * n
unvisited[end_point] = False

while True:
    u = path[-1]
    adj_e = edges[u]
    for v, e in enumerate(adj_e):
        if unvisited[v] and e != None:
            path.append(v)
            distance += e
            unvisited[v] = False
            if diameter < distance:
                diameter = distance
                end_point = v
            break
    if u == path[-1]:
        path.pop()
        if path:
            distance -= edges[u][path[-1]]
        else:
            break

# output

print(diameter)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import deque


if __name__ == '__main__':

    n = int(input())
    A = [[float("inf") for j in range(n)] for i in range(n)]

    for i in range(n - 1):
        A[i][i] = 0
        s, t, d = map(int, input().split())
        A[s][t] = d
        A[t][s] = d

    Q = deque()

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

        return d

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

Submission status: Memory Limit Exceeded

Solution code:
# Acceptance of input

import sys

f_i = sys.stdin

n = int(f_i.readline())

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

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

# Tree Walk and Output

distance = [0] * n

sys.setrecursionlimit(10000)

def tree_walk(u, d, p):
    for v, e in enumerate(edges[u]):
        if e != None and v != p:
            c_d = d + e
            distance[v] = c_d
            tree_walk(v, c_d, u)

tree_walk(0, 0, None)

end_point = distance.index(max(distance))

tree_walk(end_point, 0, None)

print(max(distance))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

# ダイクストラ(頂点数, 隣接リスト(0-indexed), 始点)
def dijkstra(N: int, nodes: list, src: int) -> list:
    # 頂点[ある始点からの最短距離]
    # (経路自体を知りたい時はここに前の頂点も持たせる)
    res = [float('inf')] * N
    # スタート位置
    que = [(0, src)]
    res[src] = 0
    # キューが空になるまで
    while len(que) != 0:
        # srcからの距離, 現在のノード
        dist, cur = heappop(que)
        # 出発ノードcurの到着ノードでループ
        for nxt, cost in nodes[cur]:
            # 今回の経路のが短い時
            if res[cur] + cost < res[nxt]:
                res[nxt] = res[cur] + cost
                # 現在の移動距離をキューの優先度として、早い方から先に処理するようにする
                heappush(que, (res[nxt], nxt))
    # ノードsrcからの最短距離リストを返却
    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))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Acceptance of input

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

# Tree Walk function

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

# Output

tree_walk(tree_walk(0), 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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 x -> bridge vertex
    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

    # bridge vertex -> y
    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()