Problem:


Score : 800 points

Problem Statement

Snuke Festival 2017 will be held in a tree with N vertices numbered 1,2, ...,N.
The i-th edge connects Vertex a_i and b_i, and has joyfulness c_i.

The staff is Snuke and N-1 black cats.
Snuke will set up the headquarters in some vertex, and from there he will deploy a cat to each of the other N-1 vertices.

For each vertex, calculate the niceness when the headquarters are set up in that vertex.
The niceness when the headquarters are set up in Vertex i is calculated as follows:

Let X=0.

For each integer j between 1 and N (inclusive) except i, do the following:

Add c to X, where c is the smallest joyfulness of an edge on the path from Vertex i to Vertex j.

The niceness is the final value of X.

Constraints

1 \leq N \leq 10^{5}

1 \leq a_i,b_i \leq N

1 \leq c_i \leq 10^{9}

The given graph is a tree.

All input values are integers.

Partial Scores

In the test set worth 200 points, N \leq 1000.

In the test set worth 200 points, c_i \leq 2.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}

Output

Print N lines. The i-th line must contain the niceness when the headquarters are set up in Vertex i.

Sample Input 1

3
1 2 10
2 3 20

Sample Output 1

20
30
30

The figure below shows the case when headquarters are set up in each of the vertices 1, 2 and 3.

The number on top of an edge denotes the joyfulness of the edge, and the number below an vertex denotes the smallest joyfulness of an edge on the path from the headquarters to that vertex.

Sample Input 2

15
6 3 2
13 3 1
1 13 2
7 1 2
8 1 1
2 8 2
2 12 2
5 2 2
2 11 2
10 2 2
10 9 1
9 14 2
4 14 1
11 15 2

Sample Output 2

16
20
15
14
20
15
16
20
15
20
20
20
16
15
20

Sample Input 3

19
19 14 48
11 19 23
17 14 30
7 11 15
2 19 15
2 18 21
19 10 43
12 11 25
3 11 4
5 19 50
4 11 19
9 12 29
14 13 3
14 6 12
14 15 14
5 1 6
8 18 13
7 16 14

Sample Output 3

103
237
71
263
370
193
231
207
299
358
295
299
54
368
220
220
319
237
370



Sample input:
3
1 2 10
2 3 20


Sample output:
20
30
30

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)

def solve():
    n = int(sys.stdin.readline())
    adj = [[] for i in range(n + 1)]

    dp = [dict() for i in range(n + 1)]
    cnt = [dict() for i in range(n + 1)]

    for i in range(n - 1):
        ai, bi, ci = map(int, sys.stdin.readline().split())

        if ci > 2:
            return

        adj[ai].append((bi, ci))
        adj[bi].append((ai, ci))

    def cnt_node(v, p):
        if p in cnt[v]:
            return cnt[v][p]

        cnt[v][p] = 1

        for (u, c) in adj[v]:
            if u == p:
                continue

            cnt[v][p] += cnt_node(u, v)

        return cnt[v][p]

    def dfs(v, p):
        if p in dp[v]:
            return dp[v][p]

        dp[v][p] = 0

        for (u, c) in adj[v]:
            if u == p:
                continue

            if c == 1:
                dp[v][p] += cnt_node(u, v)
            else:
                dp[v][p] += dfs(u, v) + 2

        return dp[v][p]

    for i in range(1, n + 1):
        # print(dp)
        # print(cnt)
        ans = dfs(i, -1)
        print(ans)



if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))

if N <= 1000:
    def dfs(u, p, co):
        res = co
        for v, c in G[u]:
            if v == p:
                continue
            res += dfs(v, u, min(co, c))
        return res
    for i in range(N):
        INF = 10**18
        print(dfs(i, -1, INF) - INF)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))

memo = {}
def dfs(u, p, co):
    if (u, p, co) in memo:
        return memo[u, p, co]
    res = co
    for v, c in G[u]:
        if v == p:
            continue
        res += dfs(v, u, min(co, c))
    memo[u, p, co] = res
    return res
for i in range(N):
    INF = 10**18
    print(dfs(i, -1, INF) - INF)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class UnionFind:
    def __init__(self, N):
        self.root = list(range(N + 1))

    def __getitem__(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def merge(self, x, y):
        x = self[x]
        y = self[y]
        if x == y:
            return
        # 番号の大きい頂点を根にする
        if x < y:
            x, y = y, x
        self.root[y] = x

N = int(readline())
m = map(int, read().split())
ABC = sorted(zip(m, m, m), key=itemgetter(2), reverse=True)

uf = UnionFind(N + N)
parent = [0] * (N + N)
value = [0] * (N + N)
for n, (a, b, c) in enumerate(ABC, N + 1):
    ra = uf[a]
    rb = uf[b]
    parent[ra] = n
    parent[rb] = n
    value[n] = c
    uf.merge(ra, n)
    uf.merge(rb, n)

size = [0] + [1] * N + [0] * (N - 1)
for n in range(N + N):
    p = parent[n]
    size[p] += size[n]

for n in range(N + N):
    p = parent[n]
    value[n] = 0
    if not p:
        continue
    value[n] = value[p] * (size[p] - size[n])
for n in range(N + N - 2, 0, -1):
    p = parent[n]
    value[n] += value[p]

print('\n'.join(map(str, value[1:N + 1])))

Submission status: Runtime Error

Solution code:
import sys

def solve():
    n = int(sys.stdin.readline())
    adj = [[] for i in range(n + 1)]

    dp = [dict() for i in range(n + 1)]
    cnt = [dict() for i in range(n + 1)]

    for i in range(n - 1):
        ai, bi, ci = map(int, sys.stdin.readline().split())

        if ci > 2:
            return

        adj[ai].append((bi, ci))
        adj[bi].append((ai, ci))

    def cnt_node(v, p):
        if p in cnt[v]:
            return cnt[v][p]

        cnt[v][p] = 1

        for (u, c) in adj[v]:
            if u == p:
                continue

            cnt[v][p] += cnt_node(u, v)

        return cnt[v][p]

    def dfs(v, p):
        if p in dp[v]:
            return dp[v][p]

        dp[v][p] = 0

        for (u, c) in adj[v]:
            if u == p:
                continue

            if c == 1:
                dp[v][p] += cnt_node(u, v)
            else:
                dp[v][p] += dfs(u, v) + 2

        return dp[v][p]

    for i in range(1, n + 1):
        # print(dp)
        # print(cnt)
        ans = dfs(i, -1)
        print(ans)



if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for i in range(N)]
mc = 100
for i in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
    mc = min(c, mc)

if N <= 1000:
    memo = {}
    def dfs(u, p, co):
        if (u, p, co) in memo:
            return memo[u, p, co]
        res = co
        for v, c in G[u]:
            if v == p:
                continue
            res += dfs(v, u, min(co, c))
        memo[u, p, co] = res
        return res
    for i in range(N):
        INF = 10**18
        print(dfs(i, -1, INF) - INF)
elif mc <= 2:
    used = [0]*N
    gu = 0
    g = [-1]
    def dfs(u, p):
        used[u] = gu
        res = 1
        for v, c in G[u]:
            if v == p:
                continue
            if c == 2:
                res += dfs(v, u)
        return res
    for i in range(N):
        if not used[i]:
            gu += 1
            nn = dfs(i, -1)-1
            g.append(nn)
        else:
            nn = g[used[i]]
        print(N + nn - 1)
else:
    exit(1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for i in range(N)]
mc = 100
for i in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
    mc = min(c, mc)

if N <= 1000:
    memo = {}
    def dfs(u, p, co):
        if (u, p, co) in memo:
            return memo[u, p, co]
        res = co
        for v, c in G[u]:
            if v == p:
                continue
            res += dfs(v, u, min(co, c))
        memo[u, p, co] = res
        return res
    for i in range(N):
        INF = 10**18
        print(dfs(i, -1, INF) - INF)
elif mc <= 2:
    used = [0]*N
    gu = 0
    g = [-1]
    def dfs(u, p):
        used[u] = gu
        res = 1
        for v, c in G[u]:
            if v == p:
                continue
            if c == 2:
                res += dfs(v, u)
        return res
    for i in range(N):
        if not used[i]:
            gu += 1
            nn = dfs(i, -1)
            g.append(nn)
        else:
            nn = g[used[i]]
        print(N + nn)
else:
    exit(1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for i in range(N)]
mc = 100
for i in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
    mc = min(c, mc)

if N <= 1000:
    memo = {}
    def dfs(u, p, co):
        if (u, p, co) in memo:
            return memo[u, p, co]
        res = co
        for v, c in G[u]:
            if v == p:
                continue
            res += dfs(v, u, min(co, c))
        memo[u, p, co] = res
        return res
    for i in range(N):
        INF = 10**18
        print(dfs(i, -1, INF) - INF)
elif mc <= 2:
    used = [0]*N
    gu = 0
    g = [-1]
    def dfs(u, p):
        used[u] = gu
        res = 1
        for v, c in G[v]:
            if v == p:
                continue
            if c == 2:
                res += dfs(v, u)
        return res
    for i in range(N):
        if not used[i]:
            gu += 1
            nn = dfs(i, -1)
            g.append(nn)
        else:
            nn = g[used[i]]
        print(N + nn)
else:
    exit(1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for i in range(N)]
mc = 100
for i in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
    mc = min(c, mc)

if N <= 1000:
    memo = {}
    def dfs(u, p, co):
        if (u, p, co) in memo:
            return memo[u, p, co]
        res = co
        for v, c in G[u]:
            if v == p:
                continue
            res += dfs(v, u, min(co, c))
        memo[u, p, co] = res
        return res
    for i in range(N):
        INF = 10**18
        print(dfs(i, -1, INF) - INF)
elif mc <= 2:
    used = [0]*N
    gu = 0
    g = [-1]
    def dfs(u, p):
        used[i] = gu
        res = 1
        for v, c in G[v]:
            if v == p:
                continue
            if c == 2:
                res += dfs(v, u)
        return res
    for i in range(N):
        if not used[i]:
            gu += 1
            nn = dfs(i, -1)
            g.append(nn)
        else:
            nn = g[used[i]]
        print(N + nn)
else:
    exit(1)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for i in range(N)]
mc = 100
for i in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))
    mc = min(c, mc)

if N <= 1000:
    memo = {}
    def dfs(u, p, co):
        if (u, p, co) in memo:
            return memo[u, p, co]
        res = co
        for v, c in G[u]:
            if v == p:
                continue
            res += dfs(v, u, min(co, c))
        memo[u, p, co] = res
        return res
    for i in range(N):
        INF = 10**18
        print(dfs(i, -1, INF) - INF)
elif mc <= 2:
    used = [0]*N
    gu = 0
    g = [-1]
    def dfs(u, p):
        used[i] = gu
        res = 1
        for v, c in G[v]:
            if c == 2:
                res += dfs(v, u)
        return res
    for i in range(N):
        if not used[i]:
            gu += 1
            nn = dfs(i, -1)
            g.append(nn)
        else:
            nn = g[used[i]]
        print(N + nn)
else:
    exit(1)

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for i in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    G[a-1].append((b-1, c))
    G[b-1].append((a-1, c))

memo = {}
def dfs(u, p, co):
    if (u, p, co) in memo:
        return memo[u, p, co]
    res = co
    for v, c in G[u]:
        if v == p:
            continue
        res += dfs(v, u, min(co, c))
    memo[u, p, co] = res
    return res
for i in range(N):
    INF = 10**18
    print(dfs(i, -1, INF) - INF)