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

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():
        root = None
        q = [i for i in range(graph.v) if len(graph.adj(i)) == 1]
        visited = [True if i in q else False for i in range(graph.v)]
        while q:
            v, *q = q
            for e in graph.adj(v):
                w = e.other(v)
                if not visited[w]:
                    visited[w] = True
                    root = w
                    q.append(w)
        if root is None:
            raise ValueError('can not select a root node in graph')
        return root

    root = select_root()
    edge_to = [None] * graph.v
    dists = [[(0, i)] for i in range(graph.v)]
    stack = [root]
    while stack:
        v = stack.pop()
        for e in graph.adj(v):
            if e != edge_to[v]:
                w = e.other(v)
                if edge_to[w] is None:
                    edge_to[w] = e
                    stack.append(v)
                    stack.append(w)
                    break
        else:
            for e in graph.adj(v):
                if e != edge_to[v]:
                    w = e.other(v)
                    bisect.insort(dists[v], (dists[w][-1][0] + e.weight, w))

    hs = [d[-1][0] for d in dists]
    for i in range(graph.v):
        while i != root:
            e = edge_to[i]
            w = e.other(i)
            for v, weight in dists[w]:
                if v != i and weight + e.weight > hs[i]:
                    hs[i] = weight + e.weight
            i = w

    return hs


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

Solution code:
def solve(prev, r, n, dic):
    d = [0] * n
    md = 0
    t = r
    stack = []
    stack += [[prev, r, 0]]
    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[vtx] < d1 + cost:
                    d[vtx] = d1 + cost
                    if md < d[vtx]:
                        md = d[vtx]
                        t = vtx
    return d, t

dic = {}
line = input()
n = int(line)
for _ in range(1, n):
    line = input()
    s, t, w = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, w]]
    else:
        dic[s] += [[t, w]]
    if t not in dic:
        dic[t] = [[s, w]]
    else:
        dic[t] += [[s, w]]
d1, t1 = solve(-1, 0, n, dic)
d2, t2 = solve(-1, t1, n, dic)
d2[t1] = d2[t2]
print("\n".join(map(str,d2)))

Submission status: Wrong Answer

Solution code:
def solve(prev, r, n, dic):
    d = [0] * n
    md = 0
    t = r
    stack = []
    stack += [[prev, r, 0]]
    while stack:
        print(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[vtx] < d1 + cost:
                    d[vtx] = d1 + cost
                    if md < d[vtx]:
                        md = d[vtx]
                        t = vtx
    return d, t

dic = {}
line = input()
n = int(line)
for _ in range(1, n):
    line = input()
    s, t, w = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, w]]
    else:
        dic[s] += [[t, w]]
    if t not in dic:
        dic[t] = [[s, w]]
    else:
        dic[t] += [[s, w]]
d1, t1 = solve(-1, 0, n, dic)
d2, t2 = solve(-1, t1, n, dic)
d3, t3 = solve(-1, t2, n, dic)
print("\n".join(map(str, [max(a, b) for a, b in zip(d2, d3)] )))

Submission status: Wrong Answer

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)

    for i in postorder(g):
        if len(g[i]) == 0:
            continue
        for di, ti in g[i]:
            dp[i][ti] = di
            if g[ti]:
                dp[i][ti] += max(d for d, t in g[ti])
    height = [None] * n
    for i in preorder(g):
        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 preorder(g):
    dfs_stack = [0]
    while dfs_stack:
        u = dfs_stack.pop()
        yield(u)
        dfs_stack.extend(t for d, t in g[u])


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


main()

Submission status: Wrong Answer

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()) if dp[i] else 0
        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() if g else 0


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

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

if n > 2:
    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: Wrong Answer

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, used) + this_edge[1])
            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: Wrong Answer

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)
  lower = min(cost2)
  higher = max(cost2)
  for i in range(n):
    print(max(cost2[i] - lower, higher - cost2[i]))
main()

Submission status: Time Limit Exceeded

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):
    s = 0
    edge_to = [None] * graph.v
    dists = [[(0, i)] for i in range(graph.v)]
    stack = [s]
    while stack:
        v = stack.pop()
        for e in graph.adj(v):
            if e != edge_to[v]:
                w = e.other(v)
                if edge_to[w] is None:
                    edge_to[w] = e
                    stack.append(v)
                    stack.append(w)
                    break
        else:
            for e in graph.adj(v):
                if e != edge_to[v]:
                    w = e.other(v)
                    bisect.insort(dists[v], (dists[w][-1][0] + e.weight, w))

    hs = [d[-1][0] for d in dists]
    for i in range(graph.v):
        j = i
        weight = 0
        while j != s:
            e = edge_to[j]
            weight += e.weight
            w = e.other(j)
            for vw, v in dists[w]:
                if v != j and weight + vw > hs[i]:
                    hs[i] = weight + vw
            j = w

    return hs


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: Time Limit Exceeded

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

dic = {}
line = input()
n = int(line)
for _ in range(1, n):
    line = input()
    s, t, w = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, w]]
    else:
        dic[s] += [[t, w]]
    if t not in dic:
        dic[t] = [[s, w]]
    else:
        dic[t] += [[s, w]]
for t in range(0, n):
    r1, t1 = solve(-1, t, dic)
    print(r1)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict
#from io import StringIO
readline = stdin.readline
#readline = StringIO('''1''').readline
#readline = open('GRL_5_B-in10.txt').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])
        g[t].append([d, s])

    dp = defaultdict(dict)
    for i in postorder(g, n):
        for di, ti in g[i]:
            dp[i][ti] = di
            candidate = [v for k, v in dp[ti].items() if k != i]
            if candidate:
                dp[i][ti] += max(candidate)
    height = [None] * n
    for i in preorder(g, n):
        height[i] = max(dp[i].values()) if dp[i] else 0
        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)
    #for i in range(len(height)):
    #    if height[i]is not None:
    #        print(i,height[i])
    print('\n'.join(map(str, height)))


def preorder(g, n):
    visited = set()
    for i in range(n):
        if i in visited:
            continue
        dfs_stack = [(i, None)]
        while dfs_stack:
            u, prev = dfs_stack.pop()
            visited |= {u}
            yield(u)
            dfs_stack.extend((t, u) for d, t in g[u] if t != prev)


def postorder(g, n):
    visited = set()
    for i in range(n):
        if i in visited:
            continue
        parent_stack = []
        dfs_stack = [(i, None)]
        while dfs_stack:
            u, prev = dfs_stack.pop()
            visited |= {u}
            dfs_stack.extend((t, u) for d, t in g[u] if t != prev)
            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: Time Limit Exceeded

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

for i in range(n): 
    d = dijkstra(i)
    print(max(d))

Submission status: Time Limit Exceeded

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(v_num):
    for i, (next_dest, weight, all_weight) in enumerate(connect[v]):
        connect[v][i][2] = dfs(v, i, connect)
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: Time Limit Exceeded

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(v_num):
    for i, (next_dest, weight, all_weight) in enumerate(connect[v]):
        if connect[v][i][2] < 0:
            connect[v][i][2] = dfs(v, i, connect)
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: Time Limit Exceeded

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:
            if connect[dest][i][2] < 0:
                this_edge[2] = max(this_edge[2], dfs(dest, i, connect) + this_edge[1])
            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:
            connect[v][i][2] = dfs(v, i, connect)
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: Time Limit Exceeded

Solution code:
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]
    for i, (next_dest, weight, all_weight, f) 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])
            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, 0])
    connect[v2].append([v1, weight, -1, 0])
for v in range(v_num):
    for i, (next_dest, weight, all_weight, f) 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, f) in enumerate(connect[v]):
        answer = max(answer, all_weight)
    print(answer)

Submission status: Accepted

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)) < 2]
        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: Accepted

Solution code:
def solve(prev, r, n, dic):
    d = [0] * n
    md = 0
    t = r
    stack = []
    stack += [[prev, r, 0]]
    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[vtx] < d1 + cost:
                    d[vtx] = d1 + cost
                    if md < d[vtx]:
                        md = d[vtx]
                        t = vtx
    return d, t

dic = {}
line = input()
n = int(line)
for _ in range(1, n):
    line = input()
    s, t, w = list(map(int, line.split()))
    if s not in dic:
        dic[s] = [[t, w]]
    else:
        dic[s] += [[t, w]]
    if t not in dic:
        dic[t] = [[s, w]]
    else:
        dic[t] += [[s, w]]
d1, t1 = solve(-1, 0, n, dic)
d2, t2 = solve(-1, t1, n, dic)
d3, t3 = solve(-1, t2, n, dic)
print("\n".join(map(str, [max(a, b) for a, b in zip(d2, d3)] )))

Submission status: Accepted

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

#readline = open('GRL_5_B-in10.txt').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])
        g[t].append([d, s])

    dp = defaultdict(dict)
    for i in postorder(g, n):
        for di, ti in g[i]:
            dp[i][ti] = di
            candidate = [v for k, v in dp[ti].items() if k != i]
            if candidate:
                dp[i][ti] += max(candidate)
    height = [None] * n
    for i in preorder(g, n):
        import operator
        candidate = list(dp[i].items())
        candidate.sort(key=operator.itemgetter(1))
        height[i] = candidate[-1][1] if candidate else 0
        for d, t in g[i]:
            dp[t][i] = d
            if 1 < len(candidate):
                k = -1 if candidate[-1][0] != t else -2
                dp[t][i] += candidate[k][1]
    print('\n'.join(map(str, height)))


def postorder(g, n):
    visited = set()
    for i in range(n):
        if i in visited:
            continue
        parent_stack = []
        dfs_stack = [(i, None)]
        while dfs_stack:
            u, prev = dfs_stack.pop()
            visited |= {u}
            dfs_stack.extend((t, u) for d, t in g[u] if t != prev)
            while parent_stack and parent_stack[-1] != prev:
                yield parent_stack.pop()
            parent_stack.append(u)
        while parent_stack:
            yield parent_stack.pop()


def preorder(g, n):
    visited = set()
    for i in range(n):
        if i in visited:
            continue
        dfs_stack = [(i, None)]
        while dfs_stack:
            u, prev = dfs_stack.pop()
            visited |= {u}
            yield(u)
            dfs_stack.extend((t, u) for d, t in g[u] if t != prev)

main()

Submission status: Accepted

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

if n > 1:
    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: 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 max_dist(dist):
    return dist.items()[dist.values().index(max(dist.values()))]

def bfs(s):
    dist = {s: 0}
    deq.append(s)
    while deq:
        s = deq.popleft()
        for t, w in G[s]:
            if t in dist:
                continue
            dist[t] = dist[s] + w
            deq.append(t)
    return dist

u, co = max_dist(bfs(0))
v, co = max_dist(bfs(u))

dist1 = bfs(u); dist2 = bfs(v)
for i in xrange(n):
    print max(dist1[i], dist2[i])

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)
  max_ind2 = cost2.index(max(cost2))
  cost3 = func(max_ind2)
  for i in range(n):
    print(max(cost2[i], cost3[i]))
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(v,p):
    deg[v]=len(G[v])
    res=0
    dp[v]=[0]*deg[v]
    for i in range(deg[v]):
        nv,c=G[v][i]
        if nv==p:
            pi[v]=i
            continue
        dp[v][i]=dfs(nv,v)+c
        res=max(res,dp[v][i])

    return res
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][pi[v]]=res_p
        h[v]=max(dp[v])
    dpl=[0]*(deg[v]+1)
    dpr=[0]*(deg[v]+1)
    for i in range(deg[v]):
        dpl[i+1]=max(dpl[i],dp[v][i])
    for i in reversed(range(deg[v])):
        dpr[i]=max(dpr[i+1],dp[v][i])
    for i in range(deg[v]):
        nv,c=G[v][i]
        if nv==p:
            continue
        reroot(nv,max(dpl[i],dpr[i+1])+c,v)

n=int(input())
G=[[] for i in range(n)]
dp=[[] for i in range(n)]
deg=[0]*n
pi=[-1]*n

for i in range(n-1):
    s,t,w=map(int,input().split())
    G[s].append((t,w))
    G[t].append((s,w))
z=dfs(0,-1)
h=[0]*n
h[0]=z
reroot(0,0,-1)
print(*h,sep='\n')