Problem:


Height of a Tree

Given a tree T with non-negative weight, find the height of each node of the tree. For each node, the height is the distance to the most distant leaf from the node.

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

The output consists of n lines. Print the height of each node 0, 1, 2, ..., n-1 in order.

Constraints

 1 ≤ n ≤ 10,000
	

 0 ≤ wi ≤ 1,000
	

Sample Input 1

4
0 1 2
1 2 1
1 3 3

Sample Output 1

5
3
4
5



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


Sample output:
5
3
4
5

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, dist


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)
	idx2, _, dist1 = bfs(n, adj, idx1)
	idx3, _, dist2 = bfs(n, adj, idx2)
	ans = [max(x, y) for x, y in zip(dist1, dist2)]
	print("\n".join(map(str, ans)))


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() 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)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    fl = defaultdict(lambda : 0)
    fr = defaultdict(lambda : 0)

    def dfs(x,hx):
        p = 0
        for y,c in v[x]:
            if hx < h[y]:
                continue
            fl[(x,y)] = p
            nh = h[y]+c
            if p < nh:
                p = nh
        p = 0
        for y,c in v[x][::-1]:
            if hx < h[y]:
                continue
            fr[(x,y)] = p
            nh = h[y]+c
            if p < nh:
                p = nh
        for y,c in v[x]:
            hy = h[y]
            if hx < hy:
                continue
            if ans[y]:continue
            nhx = max(fl[(x,y)],fr[(x,y)])
            ans[y] = nhy = max(h[y],nhx+c)
            h[x] = nhx
            dfs(y,nhy)
            h[x] = hx

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b,c = LI()
        v[a].append((b,c))
        v[b].append((a,c))
    q = [0]
    q2 = []
    h = [-1]*n
    h[0] = 0
    while q:
        x = q.pop()
        for y,c in v[x]:
            if h[y] < 0:
                h[y] = 0
                q.append(y)
                q2.append((y,x,c))
    while q2:
        y,x,c = q2.pop()
        nh = h[y]+c
        if h[x] < nh:
            h[x] = nh

    ans = [0]*n
    ans[0] = h[0]
    dfs(0,h[0])

    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import deque


def solve(tree, root):
    def dfs1():
        """各頂点の部分木内で最も遠い頂点(葉)までの距離を求める"""
        q1 = deque([root])
        q2 = deque([root])
        while q1:
            v = q1.pop()
            for nxt_v, cost in tree[v]:
                if nxt_v in par:
                    continue
                else:
                    par[nxt_v] = v
                    q1.append(nxt_v)
                    q2.append(nxt_v)
        while q2:
            v = q2.pop()
            for nxt_v, cost in tree[v]:
                if nxt_v == par[v]:
                    continue
                else:
                    dist1[v] = max(dist1[v], dist1[nxt_v] + cost)
    
    def dfs2():
        """全方位木DPで各頂点の最も遠い頂点(葉)までの距離を求める"""
        q = deque([(root, 0)])
        while q:
            v, par_d = q.pop()
            tmp = [(0, -1)]
            for nxt_v, cost in tree[v]:
                if nxt_v == par[v]:
                    tmp.append((par_d + cost, nxt_v))
                else:
                    tmp.append((cost + dist1[nxt_v], nxt_v))
            tmp = sorted(tmp, reverse=True)
            dist2[v] = tmp[0][0]
            for nxt_v, cost in tree[v]:
                if nxt_v == par[v]:
                    continue
                if tmp[0][1] != nxt_v:
                    q.append((nxt_v, tmp[0][0]))
                else:
                    q.append((nxt_v, tmp[1][0]))

    par = {root: -1}
    dist1 = [0] * n
    dist2 = [0] * n
    dfs1()
    dfs2()
    return dist2
    
    
n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b, cost = info[i]
    tree[a].append((b, cost))
    tree[b].append((a, cost))
root = 0

ans = solve(tree, root)
for res in ans:
    print(res)

Submission status: Accepted

Solution code:
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)
        d = max(dist_u)
        v = dist_u.index(d)
        return d,u,v
    def construct_lca(self):
        L = (self.n-1).bit_length()
        self.k_parent = [self.parent]
        prev = self.parent
        for k in range(L):
            array = [0 for _ in range(self.n)]
            for i in range(self.n):
                if prev[i] == -1: continue
                array[i] = prev[prev[i]]
            self.k_parent.append(array)
            prev = array
    def lca(self,u,v):
        d = self.depth[v]-self.depth[u]
        if d < 0: u,v,d = v,u,-d
        for k in self.k_parent:
            if d & 1: v = k[v]
            d >>= 1
        if u == v: return u
        for k in reversed(self.k_parent):
            pu,pv = k[u],k[v]
            if pu != pv: u,v = pu,pv
        return self.k_parent[0][u]
    def dist(self,u,v):
        l = self.lca(u,v)
        return self.distance[u]+self.distance[v]-2*self.distance[l]

import sys
input = sys.stdin.readline

N = int(input())
E = [tuple(map(int,input().split())) for _ in range(N-1)]

t = Tree(N,E)
t.setroot(0)
t.construct_lca()
d,u,v = t.diam()
ans = []

for i in range(N):
    ans.append(max(t.dist(i,u),t.dist(i,v)))

print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
def tree_height(T, w):
    N = len(T)
    # Consider T to be rooted at r = 0
    downward = [0] * N # the height of the subtree rooted at each v
    upward = [-1] * N # the height of the subtree which contains the root r and is rooted at each v
    height = [-1] * N
    def dfs1(r):
        nonlocal downward
        stack = [(r, -1, 0)] # (vertex, parent, status)
        while stack:
            v, p, st = stack.pop()
            if st == 0: # visited v for the first time
                n_children = 0
                for u in T[v]:
                    if u == p: continue
                    if n_children == 0:
                        stack += [(v, p, 2), (u, v, 0)]
                        n_children += 1
                    else:
                        stack += [(v, p, 1), (u, v, 0)]
                        n_children += 1
                if n_children == 0: # v is a leaf
                    if p != -1:
                        downward[p] = max(downward[p], downward[v] + w[p][v])
            elif st == 1: # now searching
                continue
            else: # search finished
                if p != -1:
                    downward[p] = max(downward[p], downward[v] + w[p][v])
    
    def dfs2(r):
        nonlocal upward, height
        stack = [(r, -1, 0)] # (vertex, parent, status)
        while stack:
            v, p, st = stack.pop()
            if p == -1:
                upward[v] = 0
                height[v] = max(upward[v], downward[v])
            if st == 0: # visited v for the first time
                max1, max2 = sorted([0, -1] + [downward[child] + w[child][v] for child in T[v] if child != p], reverse=True)[:2]
                n_children = 0
                for u in T[v]:
                    if u == p: continue
                    temp = max1
                    if downward[u] + w[u][v] == max1: temp = max2
                    if n_children == 0:
                        stack += [(v, p, 2), (u, v, 0)]
                        upward[u] = max(upward[v], temp) + w[u][v]
                        height[u] = max(upward[u], downward[u])
                        n_children += 1
                    else:
                        stack += [(v, p, 1), (u, v, 0)]
                        upward[u] = max(upward[v], temp) + w[u][v]
                        height[u] = max(upward[u], downward[u])
                        n_children += 1
                if n_children == 0:
                    continue
            elif st == 1: # now searching
                continue
            else: # search finished
                continue
    dfs1(0)
    dfs2(0)
    return height
    
N = int(input())
E = [[] for _ in range(N)]
weight = [{} for _ in range(N)]
for _ in range(N-1):
    s, t, w = map(int, input().split())
    E[s].append(t); E[t].append(s)
    weight[s].setdefault(t, w); weight[t].setdefault(s, w)
height = tree_height(E, weight)
print(*height, sep='\n')

Submission status: Accepted

Solution code:
import sys
from heapq import heappop, heappush
from typing import List


def func(start: int) -> List[int]:
    global edges
    cost = [sys.maxsize] * 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


if __name__ == "__main__":
    n = int(input())
    edges = [[] for _ in range(n)]  # type: ignore
    for _ in range(n - 1):
        s, t, w = map(int, input().split())
        edges[s].append((w, t))
        edges[t].append((w, s))

    cost1 = func(0)
    max_ind = cost1.index(max(cost1))
    cost2 = func(max_ind)
    max_ind2 = cost2.index(max(cost2))
    cost3 = func(max_ind2)
    for i in range(n):
        print(max(cost2[i], cost3[i]))

Submission status: Accepted

Solution code:
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
        
        def find_next(cur):
            for nxt_v, nxt_w in graph[cur]:
                dist = best[cur] + nxt_w
                if dist < best[nxt_v]:
                    best[nxt_v] = dist
                    yield dist, nxt_v
        
        def dequeue():
            _, cur_v = heappop(queue)
            for nxt in find_next(cur_v):
                heappush(queue, nxt)
        
        while queue:
            dequeue()

        res = (0, root)
        for i in range(n):
            if best[i] > res[0]:
                res = (best[i], i)
        return res, best
    
    def run(root):
        heappush(queue, (0, root))
        return find(root)
    
    ret0, best0 = run(0)
    ret1, best1 = run(ret0[1])
    ret2, best2 = run(ret1[1])
    
    for i in range(n):
        yield max(best1[i], best2[i])

with open('/dev/stdin') as f:
    for d in solve(*input(f)):
        print(d)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(int(1e7))

n = int(input())

tree = {}

for i in range(n - 1):
    s, t, w = map(int, input().split())
    if s not in tree:
        tree[s] = {}
    if t not in tree:
        tree[t] = {}
    tree[s][t] = tree[t][s] = w

max_cost = 0
max_id = 0


def visit(v: int, p: int, costs: list):
    global max_cost, max_id
    if v not in tree:
        return
    for t, w in tree[v].items():
        if t == p:
            continue
        costs[t] = costs[v] + w
        if costs[t] >= max_cost:
            max_cost = costs[t]
            max_id = t
        visit(t, v, costs)


costs0 = [0] * n
costs1 = [0] * n
costs2 = [0] * n

visit(0, -1, costs0)
visit(max_id, -1, costs1)
visit(max_id, -1, costs2)

for i in range(n):
    print(max(costs1[i], costs2[i]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# GRL_5_B: Tree - Height of a Tree

import bisect


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 heights(graph):
    def select_root():
        leaves = [v for v in range(graph.v) if len(graph.adj(v)) == 1]
        visited = [False] * graph.v
        while len(leaves) > 2:
            v, *leaves = leaves
            if not visited[v]:
                visited[v] = True
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        visited[w] = True
                        leaves.append(w)
        return leaves.pop()

    def dfs(s):
        visited = [False] * graph.v
        stack = [s]
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                stack.append(v)
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        edge_to[w] = e
                        stack.append(w)
            else:
                e = edge_to[v]
                if e is not None:
                    w = e.other(v)
                    bisect.insort(dists[w], (dists[v][-1][0] + e.weight, v))

    def _heights(s):
        hs = [0] * graph.v
        visited = [False] * graph.v
        stack = [s]
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                hs[v] = dists[v][-1][0]
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        for x, xv in reversed(dists[v]):
                            if xv != w:
                                bisect.insort(dists[w], (x + e.weight, v))
                                break
                        stack.append(w)
        return hs

    root = select_root()
    edge_to = [None] * graph.v
    dists = [[(0, i)] for i in range(graph.v)]
    dfs(root)
    return _heights(root)


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

    for w in heights(g):
        print(w)


if __name__ == '__main__':
    run()

Submission status: Runtime Error

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.readline



def main():
    n = int(readline())
    g = defaultdict(list)
    for _ in range(n - 1):
        s, t, d = map(int, readline().split())
        g[s].append([d, t])
    dp = defaultdict(dict)
    r = root(g)
    for i in postorder(g, r):
        if len(g[i]) == 0:
            continue
        for di, ti in g[i]:
            dp[i][ti] = di
            if g[ti]:
                dp[i][ti] += max(dp[ti].values())
    height = [None] * n
    for i in preorder(g, r):
        height[i] = max(dp[i].values())
        for d, t in g[i]:
            dp[t][i] = d
            if 1 < len(dp[i]):
                dp[t][i] += max(v for k, v in dp[i].items() if k != t)
    print('\n'.join(map(str, height)))

def root(g):
    return set(g.keys()).difference({t for x in g.values() for d, t in x}).pop()


def preorder(g, r):
    dfs_stack = [r]
    while dfs_stack:
        u = dfs_stack.pop()
        yield(u)
        dfs_stack.extend(t for d, t in g[u])


def postorder(g, r):
    parent_stack = []
    dfs_stack = [(r, 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()


main()

Submission status: Runtime Error

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(200000)


def dfs(u, prev):
    global post_order, pre_order

    pre_order.append((u, prev))
    for w, t in edges[u]:
        if t != prev:
            dfs(t, u)
    post_order.append(u)


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

post_order, pre_order = [], []
farthest = [{} for _ in range(n)]
height = [0] * n

dfs(0, None)

for i in post_order:
    for w, t in edges[i]:
        farthest[i][t] = w + max((d for tt, d in farthest[t].items() if tt != i), default=0)
for i, parent in pre_order:
    sorted_farthest = sorted(farthest[i].items(), key=itemgetter(1))
    max_t, max_d = sorted_farthest.pop()
    height[i] = max_d
    for w, t in edges[i]:
        if t == parent:
            continue
        farthest[t][i] = w + ((max_d if t != max_t else sorted_farthest[-1][1]) if sorted_farthest else 0)
for h in height:
    print(h)

Submission status: Runtime Error

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

def dfs(source, edge_index, connect):
    if connect[source][edge_index][2] >= 0:
        return connect[source][edge_index][2]
    this_edge = connect[source][edge_index]
    this_edge[2] = this_edge[1]
    dest = this_edge[0]
    for i, (next_dest, weight, all_weight) in enumerate(connect[dest]):
        if next_dest != source:
            this_edge[2] = max(this_edge[2], dfs(dest, i, connect) + this_edge[1])
    return this_edge[2]

v_num = int(input())
connect = defaultdict(list)
for _ in range(v_num - 1):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight, -1])
    connect[v2].append([v1, weight, -1])
for v in range(vertice):
    for i, (next_dest, weight, all_weight) in enumerate(connect[v]):
        connect[v][i][2] = dfs(v, i, connect)
for v in range(vertice):
    answer = 0
    for i, (next_dest, weight, all_weight) in enumerate(connect[v]):
        answer = max(answer, all_weight)
    print(answer)

Submission status: Runtime Error

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

def dfs(source, edge_index, connect, used):
    if used[source] or connect[source][edge_index][2] >= 0:
        return connect[source][edge_index][2]
    used[source] = 1
    this_edge = connect[source][edge_index]
    this_edge[2] = this_edge[1]
    dest = this_edge[0]
    for i, (next_dest, weight, all_weight) in enumerate(connect[dest]):
        if next_dest != source:
            if connect[dest][i][2] < 0:
                this_edge[2] = max(this_edge[2], dfs(dest, i, connect) + this_edge[1], used)
            else:
                this_edge[2] = max(this_edge[2], connect[dest][i][2] + this_edge[1])
    return this_edge[2]

v_num = int(input())
connect = defaultdict(list)
for _ in range(v_num - 1):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight, -1])
    connect[v2].append([v1, weight, -1])
for v in range(v_num):
    for i, (next_dest, weight, all_weight) in enumerate(connect[v]):
        if connect[v][i][2] < 0:
            used = [0 for n in range(v_num)]
            connect[v][i][2] = dfs(v, i, connect, used)
for v in range(v_num):
    answer = 0
    for i, (next_dest, weight, all_weight) in enumerate(connect[v]):
        answer = max(answer, all_weight)
    print(answer)

Submission status: Runtime Error

Solution code:
# for undirected graph

from collections import defaultdict
import sys
sys.setrecursionlimit(200000)

def dfs(source, edge_index, connect, used):
    if connect[source][edge_index][3] or connect[source][edge_index][2] >= 0:
        return connect[source][edge_index][2]
    connect[source][edge_index][3] = 1
    this_edge = connect[source][edge_index]
    this_edge[2] = this_edge[1]
    dest = this_edge[0]
    rev_i = this_edge[4]
    for i, (next_dest, weight, all_weight, f, rev_i) in enumerate(connect[dest]):
        if next_dest != source:
            if connect[dest][i][2] < 0:
                this_edge[2] = max(this_edge[2], dfs(dest, i, connect, used) + this_edge[1])
                connect[dist][rev_i][2] = this_edge[2]
            else:
                this_edge[2] = max(this_edge[2], connect[dest][i][2] + this_edge[1])
                connect[dist][rev_i][2] = this_edge[2]
    return this_edge[2]

v_num = int(input())
connect = defaultdict(list)
for _ in range(v_num - 1):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight, -1, 0, len(connect[v2])])
    connect[v2].append([v1, weight, -1, 0, len(connect[v1]) - 1])
for v in range(v_num):
    for i, (next_dest, weight, all_weight, f, rev_i) in enumerate(connect[v]):
        if connect[v][i][2] < 0:
            used = [0 for n in range(v_num)]
            connect[v][i][2] = dfs(v, i, connect, used)
            connect[next_dest][rev_i][2] = connect[v][i][2]
for v in range(v_num):
    answer = 0
    for i, (next_dest, weight, all_weight, f) in enumerate(connect[v]):
        answer = max(answer, all_weight)
    print(answer)

Submission status: Runtime Error

Solution code:
# for undirected graph

from collections import defaultdict
import sys
sys.setrecursionlimit(200000)

def dfs(source, edge_index, connect):
    if connect[source][edge_index][3] or connect[source][edge_index][2] >= 0:
        return connect[source][edge_index][2]
    connect[source][edge_index][3] = 1
    this_edge = connect[source][edge_index]
    this_edge[2] = this_edge[1]
    dest = this_edge[0]
    rev_i = this_edge[4]
    for i, (next_dest, weight, all_weight, f, rev_i) in enumerate(connect[dest]):
        if next_dest != source:
            if connect[dest][i][2] < 0:
                this_edge[2] = max(this_edge[2], dfs(dest, i, connect) + this_edge[1])
                # connect[dest][rev_i][2] = this_edge[2]
            else:
                this_edge[2] = max(this_edge[2], connect[dest][i][2] + this_edge[1])
                # connect[dest][rev_i][2] = this_edge[2]
    return this_edge[2]

v_num = int(input())
connect = defaultdict(list)
for _ in range(v_num - 1):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight, -1, 0, len(connect[v2])])
    connect[v2].append([v1, weight, -1, 0, len(connect[v1]) - 1])
for v in range(v_num):
    for i, (next_dest, weight, all_weight, f, rev_i) in enumerate(connect[v]):
        if connect[v][i][2] < 0 and connect[next_dest][rev_i] < 0:
            connect[v][i][2] = dfs(v, i, connect)
            # connect[next_dest][rev_i][2] = connect[v][i][2]
        else:
            connect[v][i][2] = max(connect[next_dest][rev_i], connect[v][i][2])
for v in range(v_num):
    answer = 0
    for i, (next_dest, weight, all_weight, f, rev) in enumerate(connect[v]):
        answer = max(answer, all_weight)
    print(answer)

Submission status: Runtime Error

Solution code:
# for undirected graph

from collections import defaultdict
import sys
sys.setrecursionlimit(200000)

def dfs(source, edge_index, connect):
    if connect[source][edge_index][3] or connect[source][edge_index][2] >= 0:
        return connect[source][edge_index][2]
    connect[source][edge_index][3] = 1
    this_edge = connect[source][edge_index]
    this_edge[2] = this_edge[1]
    dest = this_edge[0]
    rev_i = this_edge[4]
    for i, (next_dest, weight, all_weight, f, rev_i) in enumerate(connect[dest]):
        if next_dest != source:
            if connect[dest][i][2] < 0:
                this_edge[2] = max(this_edge[2], dfs(dest, i, connect) + this_edge[1])
                # connect[dest][rev_i][2] = this_edge[2]
            else:
                this_edge[2] = max(this_edge[2], connect[dest][i][2] + this_edge[1])
                # connect[dest][rev_i][2] = this_edge[2]
    return this_edge[2]

v_num = int(input())
connect = defaultdict(list)
for _ in range(v_num - 1):
    v1, v2, weight = (int(n) for n in input().split(" "))
    connect[v1].append([v2, weight, -1, 0, len(connect[v2])])
    connect[v2].append([v1, weight, -1, 0, len(connect[v1]) - 1])
for v in range(v_num):
    for i, (next_dest, weight, all_weight, f, rev_i) in enumerate(connect[v]):
        if connect[v][i][2] < 0:
            connect[v][i][2] = dfs(v, i, connect)
            # connect[next_dest][rev_i][2] = connect[v][i][2]
        else:
            connect[v][i][2] = max(connect[next_dest][rev_i], connect[v][i][2])
for v in range(v_num):
    answer = 0
    for i, (next_dest, weight, all_weight, f, rev) in enumerate(connect[v]):
        answer = max(answer, all_weight)
    print(answer)