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: Runtime Error

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]]
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: Runtime Error

Solution code:
def solve(prev, r, dic):
    d = 0
    t = r
    if r in dic:
        for vtx, cost in dic[r]:
            if vtx == prev:
                continue
            d1, t1 = solve(r, vtx, dic)
            d1 += cost
            if d < d1:
                d = d1
                t = t1
    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: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10000)

def solve(prev, r, dic):
    d = 0
    t = r
    if r in dic:
        for vtx, cost in dic[r]:
            if vtx == prev:
                continue
            d1, t1 = solve(r, vtx, dic)
            d1 += cost
            if d < d1:
                d = d1
                t = t1
    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: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(50000)

def solve(prev, r, dic):
    d = 0
    t = r
    if r in dic:
        for vtx, cost in dic[r]:
            if vtx == prev:
                continue
            d1, t1 = solve(r, vtx, dic)
            d1 += cost
            if d < d1:
                d = d1
                t = t1
    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: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(100000)

def solve(prev, r, dic):
    d = 0
    t = r
    if r in dic:
        for vtx, cost in dic[r]:
            if vtx == prev:
                continue
            d1, t1 = solve(r, vtx, dic)
            d1 += cost
            if d < d1:
                d = d1
                t = t1
    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: Runtime Error

Solution code:
def postorder(g):
    parent_stack = [None]
    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[-1] != prev:
            yield parent_stack.pop()
        parent_stack.append(u)
    while parent_stack[-1] is not None:
        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 = []
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(g[i]) == 1 else sum(candidate[-2:]))

print(max(diameter))

Submission status: Runtime Error

Solution code:
def root(g):
    return set(g.keys()).difference({y for x in g.values() for y in x}).pop()

def postorder(g):
    parent_stack = [None]
    dfs_stack = [(root(g), None)]            
    while dfs_stack:
        u, prev = dfs_stack.pop()
        dfs_stack.extend((t, u) for d, t in g[u])
        while parent_stack[-1] != prev:
            yield parent_stack.pop()
        parent_stack.append(u)
    while parent_stack[-1] is not None:
        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 = []
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(g[i]) == 1 else sum(candidate[-2:]))

print(max(diameter))

Submission status: Runtime Error

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 != 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: Runtime Error

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

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: Runtime Error

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 and Output

distance = [0] * n

sys.setrecursionlimit(10000)

def tree_walk(u, d, p):
    for v, w in edges[u]:
        if v != p:
            c_d = d + w
            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: Runtime Error

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 and Output

distance = [0] * n

sys.setrecursionlimit(100000)

def tree_walk(u, d, p):
    for v, w in edges[u]:
        if v != p:
            c_d = d + w
            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: Runtime Error

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 and Output

distance = [0] * n

sys.setrecursionlimit(200000)

def tree_walk(u, d, p):
    for v, w in edges[u]:
        if v != p:
            c_d = d + w
            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: Runtime Error

Solution code:
while 1:
    n = input()
    if n == 0:
        break
    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))

    def dfs(s, prev):
        if prev != -1 and len(G[s]) == 1:
            return (0, s)
        res = (0, -1)
        for t, w in G[s]:
            if t == prev:
                continue
            cost, v = dfs(t, s)
            res = max(res, (cost + w, v))
        return res
    co, t = dfs(0, -1)
    if t != -1:
        print dfs(t, -1)[0]
    else:
        print 0

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
while 1:
    n = input()
    if n == 0:
        break
    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))

    def dfs(s, prev):
        if prev != -1 and len(G[s]) == 1:
            return (0, s)
        res = (0, -1)
        for t, w in G[s]:
            if t == prev:
                continue
            cost, v = dfs(t, s)
            res = max(res, (cost + w, v))
        return res
    co, t = dfs(0, -1)
    if t != -1:
        print dfs(t, -1)[0]
    else:
        print 0

Submission status: Runtime Error

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

def dfs(s, prev):
    if prev != -1 and len(G[s]) == 1:
        return (0, s)
    res = (0, -1)
    for t, w in G[s]:
        if t == prev:
            continue
        cost, v = dfs(t, s)
        res = max(res, (cost + w, v))
    return res
co, t = dfs(0, -1)
if t != -1:
    print dfs(t, -1)[0]
else:
    print 0

Submission status: Runtime Error

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

def dfs(s, prev):
    if prev != -1 and len(G[s]) == 1:
        return (0, s)
    res = (0, s)
    for t, w in G[s]:
        if t == prev:
            continue
        cost, v = dfs(t, s)
        res = max(res, (cost + w, v))
    return res
co, t = dfs(0, -1)
print dfs(t, -1)[0]

Submission status: Runtime Error

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, 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)
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: Runtime Error

Solution code:
from collections import defaultdict

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: Runtime Error

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(100000)

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)