Problem:


Score : 800 points

Problem Statement

Snuke found a record of a tree with N vertices in ancient ruins.
The findings are as follows:

The vertices of the tree were numbered 1,2,...,N, and the edges were numbered 1,2,...,N-1.

Edge i connected Vertex a_i and b_i.

The length of each edge was an integer between 1 and 10^{18} (inclusive).

The sum of the shortest distances from Vertex i to Vertex 1,...,N was s_i.

From the information above, restore the length of each edge.
The input guarantees that it is possible to determine the lengths of the edges consistently with the record.
Furthermore, it can be proved that the length of each edge is uniquely determined in such a case.

Constraints

2 \leq N \leq 10^{5}

1 \leq a_i,b_i \leq N

1 \leq s_i \leq 10^{18}

The given graph is a tree.

All input values are integers.

It is possible to consistently restore the lengths of the edges.

In the restored graph, the length of each edge is an integer between 1 and 10^{18} (inclusive).

Partial Scores

In the test set worth 300 points, a_i = i, b_i = i+1.

In the test set worth 200 points, N \geq 3, a_i = 1, b_i = i+1.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}
s_1 s_2 ... s_{N}

Output

Print N-1 lines. The i-th line must contain the length of Edge i.

Sample Input 1

4
1 2
2 3
3 4
8 6 6 8

Sample Output 1

1
2
1

The given record corresponds to the tree shown below:

Sample Input 2

5
1 2
1 3
1 4
1 5
10 13 16 19 22

Sample Output 2

1
2
3
4

The given record corresponds to the tree shown below:

Sample Input 3

15
9 10
9 15
15 4
4 13
13 2
13 11
2 14
13 6
11 1
1 12
12 3
12 7
2 5
14 8
1154 890 2240 883 2047 2076 1590 1104 1726 1791 1091 1226 841 1000 901

Sample Output 3

5
75
2
6
7
50
10
95
9
8
78
28
89
8



Sample input:
4
1 2
2 3
3 4
8 6 6 8


Sample output:
1
2
1

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    ab = [sorted(list(map(int, input().split()))) for _ in [0]*(n-1)]
    s = list(map(int, input().split()))

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    dd = [[j, i] for i, j in enumerate(d)]
    dd.sort(key=lambda x: -x[0])
    dd = [j for i, j in dd]

    dp = [1]*n
    for i in dd:
        for j in g[i]:
            if d[j] > d[i]:
                dp[i] += dp[j]

    ans = []
    for a, b in ab:
        a -= 1
        b -= 1
        if d[a] > d[b]:
            a, b = b, a
        ay = dp[b]-1
        ax = n-2-ay
        if ax-ay == 0:
            ans.append(1j)
        else:
            ans.append(abs(s[a]-s[b])//abs(ax-ay))

    ab_dict = {(ab[i][0]-1, ab[i][1]-1): ans[i] for i in range(n-1)}

    if 1j in ans:
        cnt = 0
        for i in ans:
            if i == 1j:
                cnt += 1
        if cnt > 1:
            return
        p = ans.index(1j)
        q = [root]

        temp_1 = 0
        temp_2 = 0
        while q:
            qq = []
            while q:
                i = q.pop()
                for j in g[i]:
                    if d[j] > d[i]:
                        a, b = min(i, j), max(i, j)
                        temp = ab_dict[(a, b)]
                        if temp == 1j:
                            temp_2 = dp[j]
                        else:
                            temp_1 += dp[j]*temp
                        qq.append(j)
            q = qq

        ans[p] = (s[0]-temp_1)//temp_2

    for i in ans:
        print(i)


main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
data = list(map(int,read().split()))
A = data[:N+N-2:2]
B = data[1:N+N-2:2]
INF = 10 ** 18 + 100
S = [INF] + data[-N:]

graph = [[] for _ in range(N+1)]
for a,b in zip(A,B):
    graph[a].append(b)
    graph[b].append(a)

root = S.index(min(S))
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

subtree_size = [1] * (N+1)
for v in reversed(order):
    subtree_size[parent[v]] += subtree_size[v]

length = [0] * (N+1)
for v,p in zip(A,B):
    if parent[p] == v:
        v,p = p,v
    s = subtree_size[v]
    d = N - s - s
    length[v] = 0 if d == 0 else(S[v] - S[p]) // d

# 重心間以外は決まった。いったん、重心間を 0 として計算

dist = [0] * (N+1)
for v in order[1:]:
    p = parent[v]
    dist[v] = dist[p] + length[v]

d_root = sum(dist)
x = (S[root] - d_root) * 2 // N
answer = []
for v,p in zip(A,B):
    if parent[p] == v:
        v,p = p,v
    if length[v] == 0:
        length[v] = x
    answer.append(length[v])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N=int(input())
G=[[] for i in range(N)]
E=[]
ans=[0]*(N-1)
for i in range(N-1):
  a,b=map(int,input().split())
  G[a-1].append((b-1,i))
  G[b-1].append((a-1,i))
s=[int(i) for i in input().split()]
n=[0]*N
visited=[False]*N
def size(x):
  res=1
  visited[x]=True
  for i,e in G[x]:
    if visited[i]:
      continue
    res+=size(i)
    E.append((e,x,i))
  n[x]=res
  return res
size(0)
#print(n)
flag=0
E.sort()
for i in range(N-1):
  e,a,b=E[i]
  if 2*n[b]==N:
    flag=e+1
    continue
  ans[e]=abs((s[a]-s[b])//(2*n[b]-N))
#print(ans,flag)
#print(E)
if flag:
  A=s[0]
  for i in range(N-1):
    A-=n[E[i][2]]*ans[i]
  ans[flag-1]=A//n[E[flag-1][2]]
for i in range(N-1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    s = list(map(int, input().split()))

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    dd = [[j, i] for i, j in enumerate(d)]
    dd.sort(key=lambda x: -x[0])
    dd = [j for i, j in dd]

    dp = [1]*n
    for i in dd:
        for j in g[i]:
            if d[j] > d[i]:
                dp[i] += dp[j]

    ans = []
    for a, b in ab:
        a -= 1
        b -= 1
        if d[a] > d[b]:
            a, b = b, a
        ay = dp[b]-1
        ax = n-2-ay
        if ax-ay == 0:
            ans.append(1j)
        else:
            ans.append(abs(s[a]-s[b])//abs(ax-ay))

    ab_dict = {(ab[i][0]-1, ab[i][1]-1): ans[i] for i in range(n-1)}

    if 1j in ans:
        cnt = 0
        for i in ans:
            if i == 1j:
                cnt += 1
        if cnt > 1:
            return
        p = ans.index(1j)
        q = [root]

        temp_1 = 0
        temp_2 = 0
        while q:
            qq = []
            while q:
                i = q.pop()
                for j in g[i]:
                    if d[j] > d[i]:
                        a, b = min(i, j), max(i, j)
                        temp = ab_dict[(a, b)]
                        if temp == 1j:
                            temp_2 = dp[j]
                        else:
                            temp_1 += dp[j]*temp
                        qq.append(j)
            q = qq

        ans[p] = (s[0]-temp_1)//temp_2

    for i in ans:
        print(i)


main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    s = list(map(int, input().split()))

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    dd = [[j, i] for i, j in enumerate(d)]
    dd.sort(key=lambda x: -x[0])
    dd = [j for i, j in dd]

    dp = [1]*n
    for i in dd:
        for j in g[i]:
            if d[j] > d[i]:
                dp[i] += dp[j]

    ans = []
    for a, b in ab:
        a -= 1
        b -= 1
        if d[a] > d[b]:
            a, b = b, a
        ay = dp[b]-1
        ax = n-2-ay
        if ax-ay == 0:
            ans.append(1j)
        else:
            ans.append(abs(s[a]-s[b])//abs(ax-ay))

    ab_dict = {(ab[i][0]-1, ab[i][1]-1): ans[i] for i in range(n-1)}

    if 1j in ans:
        p = ans.index(1j)
        q = [root]

        temp_1 = 0
        temp_2 = 0
        while q:
            qq = []
            while q:
                i = q.pop()
                for j in g[i]:
                    if d[j] > d[i]:
                        a, b = min(i, j), max(i, j)
                        temp = ab_dict[(a, b)]
                        if temp == 1j:
                            temp_2 = dp[j]
                        else:
                            temp_1 += dp[j]*temp
                        qq.append(j)
            q = qq

        ans[p] = (s[0]-temp_1)//temp_2

    for i in ans:
        print(i)


main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    s = list(map(int, input().split()))

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    dd = [[j, i] for i, j in enumerate(d)]
    dd.sort(key=lambda x: -x[0])
    dd = [j for i, j in dd]

    dp = [1]*n
    for i in dd:
        for j in g[i]:
            if d[j] > d[i]:
                dp[i] += dp[j]

    ans = []
    for a, b in ab:
        a -= 1
        b -= 1
        if d[a] > d[b]:
            a, b = b, a
        ay = dp[b]-1
        ax = n-2-ay
        if ax-ay == 0:
            ans.append(1j)
        else:
            ans.append(abs(s[a]-s[b])//abs(ax-ay))

    ab_dict = {(ab[i][0]-1, ab[i][1]-1): ans[i] for i in range(n-1)}

    if 1j in ans:
        p = ans.index(1j)
        q = [root]

        temp = 0
        while q:
            qq = []
            while q:
                i = q.pop()
                for j in g[i]:
                    if d[j] > d[i]:
                        a, b = min(i, j), max(i, j)
                        temp += dp[j]*ab_dict[(a, b)]
                        qq.append(j)
            q = qq

        ans[p] = int((s[0]-temp.real)//temp.imag)

    for i in ans:
        print(i)


main()