Problem:


Diameter of a Tree

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

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

Input

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

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

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

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

Output

Print the diameter of the tree in a line.

Constraints

 1 ≤ n ≤ 100,000
	

 0 ≤ wi ≤ 1,000
	

Sample Input 1

4
0 1 2
1 2 1
1 3 3

Sample Output 1

5

Sample Input 2

4
0 1 1
1 2 2
2 3 4

Sample Output 2

7



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


Sample output:
5

Submission status: Accepted

Solution code:
#!/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)
    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()

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(random node) -> bridge vertex
    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

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

Submission status: Accepted

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

import sys
import os
import pprint
from queue import Queue

"""Diameter of Tree"""

#fd = os.open('GRL_5_A.txt', os.O_RDONLY)
#os.dup2(fd, sys.stdin.fileno())


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)


# ???i??????1????????????????±???????
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]
    #print('farthest i {} d {}'.format(max_i, max_d))
    return max_i, max_d

# ?§???????????????§????????????????????????1???????????????????????????
temp_i, temp_d = bfs(0)
# ?¬????????????????1???????????????????????????
temp_i, temp_d = bfs(temp_i)

# diameter
print(temp_d)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# Dijkstra????????¨??????vertex???????????¢?????????
# ???????????????????????????????????¢?????´???????????§??´???????±???????

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

#??????????????????????????¢?????´???????????????????????????s???????????§???0??¨???????????????
l_0 =  dijkstra(N, 0)
x = l_0.index(max(l_0))
l_x = dijkstra(N, x)
print(max(l_x))

Submission status: Accepted

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
        md = k
d = [float('inf')] * n
visited = [False] * n
d[mi] = 0
bfs(mi)
print(max(d))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	diameter_of_a_tree
# CreatedDate:  2020-07-10 20:12:23 +0900
# LastModified: 2020-07-29 00:12:01 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd
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()

Submission status: Accepted

Solution code:

# 全方位木DP

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys,collections
sys.setrecursionlimit(1000000)
N = int(sys.stdin.readline())
#sdw = [[src1 dist1 d1][src1 dist1 d1]...]# vect source1 -> distance1 distances
INF = float("inf")

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

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

for s,t,w in stw:
    G[s][t] = w
    G[t][s] = w
#print(G)
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())
#print(distance)
i = distance.index(max(distance))
dfs(i,0,set())
#print(distance)

print(max(distance))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import queue

# input
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()
        # print(f'corrent_node: {current_node}, current_dist: {current_dist}')
        distance[current_node] = current_dist
        foot_print[current_node] = True

        for node, dist in tree[current_node]:
            # print(f'node: {node}, dist: {dist}')
            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)

Submission status: Accepted

Solution code:
###参考 https://ei1333.hateblo.jp/entry/2017/04/10/224413
# 非負の重みをもつ無向の木 T の直径
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)
    #print(dist)
    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()

"""


"""

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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