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  s 1  t 1  w 1  s 2  t 2  w 2 : s n-1  t n-1  w n-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. s i and t i represent end-points of the i -th edge (undirected) and w i 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 ≤ w i ≤ 1,000  Sample Input 1 4
0 1 2
1 2 1
1 3 3 Sample Output 1 5
3
4
5

Solution (Python):



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

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

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

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

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

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

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

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

Solution (Python):

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


if __name__ == "__main__":
    solve()

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

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

Solution (Python):
def tree_height(T, w):
    N = len(T)
    
    downward = [0] * N 
    upward = [-1] * N 
    height = [-1] * N
    def dfs1(r):
        nonlocal downward
        stack = [(r, -1, 0)] 
        while stack:
            v, p, st = stack.pop()
            if st == 0: 
                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: 
                    if p != -1:
                        downward[p] = max(downward[p], downward[v] + w[p][v])
            elif st == 1: 
                continue
            else: 
                if p != -1:
                    downward[p] = max(downward[p], downward[v] + w[p][v])
    
    def dfs2(r):
        nonlocal upward, height
        stack = [(r, -1, 0)] 
        while stack:
            v, p, st = stack.pop()
            if p == -1:
                upward[v] = 0
                height[v] = max(upward[v], downward[v])
            if st == 0: 
                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: 
                continue
            else: 
                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')

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

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

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