Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

data1 = getInputListInt()
n = data1[0]
q = data1[1]

data2 = getSomeInputListInt(n-1)

data3 = getSomeInputListInt(q)

ans = np.zeros(n)

for i in range(len(data3)):
    ans[data3[i][0]-1] += data3[i][1]

treeList = [[] for _ in range(n)]

for i in range(len(data2)):
    treeList[data2[i][0]-1].append(data2[i][1]-1)
    treeList[data2[i][1]-1].append(data2[i][0]-1)

def treeTrace(crnt, prnt):
    for i in range(len(treeList[crnt])):
        if prnt == treeList[crnt][i]:
            continue
        ans[treeList[crnt][i]] += ans[crnt]

        treeTrace(treeList[crnt][i], crnt)

treeTrace(0, -1)

for s in ans:
    print(int(s), end =" ")

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics

sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

data1 = getInputListInt()
n = data1[0]
q = data1[1]

data2 = getSomeInputListInt(n-1)

data3 = getSomeInputListInt(q)

ans = np.zeros(n)

for i in range(len(data3)):
    ans[data3[i][0]-1] += data3[i][1]

treeList = [[] for _ in range(n)]

for i in range(len(data2)):
    treeList[data2[i][0]-1].append(data2[i][1]-1)
    treeList[data2[i][1]-1].append(data2[i][0]-1)

def treeTrace(crnt, prnt):
    for i in range(len(treeList[crnt])):
        if prnt == treeList[crnt][i]:
            continue
        ans[treeList[crnt][i]] += ans[crnt]

        treeTrace(treeList[crnt][i], crnt)

treeTrace(0, -1)

for s in ans:
    print(int(s), end =" ")

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce
import statistics


# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

data1 = getInputListInt()
n = data1[0]
q = data1[1]

data2 = getSomeInputListInt(n-1)

data3 = getSomeInputListInt(q)

ans = np.zeros(n)

for i in range(len(data3)):
    ans[data3[i][0]-1] += data3[i][1]

treeList = [[] for _ in range(n)]

for i in range(len(data2)):
    treeList[data2[i][0]-1].append(data2[i][1]-1)
    treeList[data2[i][1]-1].append(data2[i][0]-1)

def treeTrace(crnt, prnt):
    for i in range(len(treeList[crnt])):
        if prnt == treeList[crnt][i]:
            continue
        ans[treeList[crnt][i]] += ans[crnt]

        treeTrace(treeList[crnt][i], crnt)

treeTrace(0, -1)

for s in ans:
    print(int(s), end =" ")

Submission status: Time Limit Exceeded

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

# from collections import defaultdict
def dfs(node_i):
    is_visited[node_i] = 1
    for bi in tree[node_i]:
        if is_visited[bi]:
            continue
        tree_x[bi] += tree_x[node_i]
        dfs(bi)

N, Q = map(int, input().split())
tree = [[] for i in range(N)]
# tree = defaultdict(list)
tree_x = [0]*N
is_visited = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    am1 = a-1
    bm1 = b-1
    tree[bm1].append(am1)
    tree[am1].append(bm1)

# print(tree)
for q in range(Q):
    p, x = map(int, input().split())
    tree_x[p-1] += x

dfs(0)

print(' '.join(map(str, tree_x)))

Submission status: Time Limit Exceeded

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

from collections import defaultdict
def dfs(node_i):
    is_visited[node_i] = 1
    for bi in tree[node_i]:
        if is_visited[bi]:
            continue
        tree_x[bi] += tree_x[node_i]
        dfs(bi)

N, Q = map(int, input().split())
# tree = [[] for i in range(N)]
tree = defaultdict(list)
tree_x = [0 for i in range(N)]
is_visited = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    am1 = a-1
    bm1 = b-1
    tree[bm1].append(am1)
    tree[am1].append(bm1)

# print(tree)
for q in range(Q):
    p, x = map(int, input().split())
    tree_x[p-1] += x

dfs(0)

print(' '.join(map(str, tree_x)))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import defaultdict
d = defaultdict(int)
for i in range(q):
    tmp = list(map(int,input().split()))
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = {0}
Q = deque()
Q.append([0,0])
while Q:
    node= Q.popleft()
    finish.add(node[0])

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if nxt in finish:
            pass
        else:
            Q.append([nxt,val])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import defaultdict
d = defaultdict(int)
for i in range(q):
    tmp = list(map(int,input().split()))
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = {0}
Q = deque()
Q.append([0,0])
while Q:
    node= Q.popleft()
    finish.add(node[0])

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if not nxt in finish:
            Q.append([nxt,val])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import defaultdict
d = defaultdict(int)
p=[]
for i in range(q):
    tmp = list(map(int,input().split()))
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = [False]*n
Q = deque()
Q.append([0,0])

while Q:
    node= Q.popleft()
    finish[node[0]]=True

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if not finish[nxt]:
            Q.append([nxt,val])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
link = [[] for _ in range(n)]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

p=[]
for i in range(q):
    tmp = list(map(int,input().split()))
    p.append(tmp)

from collections import defaultdict
d = defaultdict(int)

for tmp in p:
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = [False]*n
Q = deque()
Q.append([0,0])

while Q:
    node= Q.popleft()
    finish[node[0]]=True

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if not finish[nxt]:
            Q.append([nxt,val])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
a=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    a.append(tmp)

p=[]
for i in range(q):
    tmp = list(map(int,input().split()))
    p.append(tmp)

link = [[] for _ in range(n)]

for tmp in a:
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import defaultdict
d = defaultdict(int)

for tmp in p:
    d[tmp[0]-1]+=tmp[1]

from collections import deque
ans =[0]*n
finish  = [False]*n
Q = deque()
Q.append([0,0])

while Q:
    node= Q.popleft()
    finish[node[0]]=True

    val = node[1] + d[node[0]]
    ans[node[0]]+=val

    for nxt in link[node[0]]:
        if not finish[nxt]:
            Q.append([nxt,val])

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = map(int, input().split())

    values = [0] * N
    links = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        links[a - 1].append(b - 1)
        links[b - 1].append(a - 1)
    for _ in range(Q):
        p, x = map(int, input().split())
        values[p - 1] += x

    s = [(0, -1)]
    while s:
        i, p = s.pop(0)
        for j in links[i]:
            if j == p:
                continue
            values[j] += values[i]
            s.append((j, i))
    print(*values)

main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

values = [0] * N
links = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    links[a - 1].append(b - 1)
    links[b - 1].append(a - 1)
for _ in range(Q):
    p, x = map(int, input().split())
    values[p - 1] += x

s = [(0, -1)]
while s:
    i, p = s.pop(0)
    for j in links[i]:
        if j == p:
            continue
        values[j] += values[i]
        s.append((j, i))
print(*values)

Submission status: Time Limit Exceeded

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


def main():
    def dfs(now, prev=-1):
        for next in edge[now]:
            if next == prev:
                continue
            score[next] += score[now]
            dfs(next, now)

    N, Q = map(int, input().split())
    edge = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        edge[u].append(v)
        edge[v].append(u)
    p = []
    x = []
    score = [0] * (N+1)
    for _ in range(Q):
        p, x = map(int, input().split())
        score[p] += x
    dfs(1)
    print(*score[1:])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
from itertools import groupby
sys.setrecursionlimit(10**6) 
n,q = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(n-1)]
lin = [list(map(int,stdin.readline().rstrip().split())) for _ in range(q)]

kazu = [[]for _ in range(n)]
point = [0]*n

for i in range(n-1):
    kazu[li[i][0]-1].append(li[i][1]-1)
    kazu[li[i][1]-1].append(li[i][0]-1)
for i in range(q):
    point[lin[i][0]-1] += lin[i][1]

def dfs(now,before):
    for i in (kazu[now]):
        if i == before:
            continue
        point[i] += point[now]
        dfs(i,now)
dfs(0,-1)
print(*point)

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
G = [[] for _ in range(n)]
S = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    S[p - 1] += x

ans = [-1] * n

def dfs(v, cnt):
    ans[v] = cnt + S[v]
    for i in G[v]:
        if ans[i] == -1: dfs(i, cnt + S[v])

dfs(0, 0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

N, Q=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(N-1)]
px=[list(map(int, input().split())) for _ in range(Q)]
to=[[] for _ in range(N)]
co=[0 for _ in range(N)]

for a, b in ab:
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for p, x in px:
    p-=1
    co[p]+=x

def dfs(v, p=-1):
    for u in to[v]:
        if u==p:
            continue
        co[u]+=co[v]
        dfs(u, v)

dfs(0)
print(*co)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

N, Q=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(N-1)]
px=[list(map(int, input().split())) for _ in range(Q)]
to=[[] for _ in range(N)]
co=[0 for _ in range(N)]

for a, b in ab:
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for p, x in px:
    p-=1
    co[p]+=x

def dfs(v, p=-1):
    for u in to[v]:
        if u==p:
            continue
        co[u]+=co[v]
        dfs(u, v)

dfs(0)
print(*co)

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc138/tasks/abc138_d
# 下に数を最初に合計してから深さ優先探索なり、幅優先探索なりで下にカウンターを伝播させていけば良い。
# 累積和の木構造バージョン


import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


# 再帰の上限を緩和する(引数は適当)
import sys
sys.setrecursionlimit(1 << 25)
from collections import defaultdict

N, Q = read_ints()
child = defaultdict(lambda: [])  # ノード0は存在しない
score = [0] * (N + 1)
for _ in range(N - 1):
    a, b = read_ints()
    child[a].append(b)
    child[b].append(a)
for _ in range(Q):
    p, x = read_ints()
    score[p] += x

# 木を走査しながらscoreを合計していく
ans = [0] * (N + 1)


def dfs(p, u, s):  # ノードuの親pにおけるスコアs
    s += score[u]
    ans[u] = s
    for c in child[u]:
        if p == c:
            continue
        dfs(u, c, s)


dfs(-1, 1, 0)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

n, q = map(int, input().split())

tree = defaultdict(lambda: [])
for _ in range(n - 1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

count = defaultdict(lambda: 0)
for _ in range(q):
    p, x = map(int, input().split())
    count[p] += x

ret = [0] * n
q = deque(maxlen=n)
q.append((1, 1))
while len(q) > 0:
    f, c = q.popleft()
    ret[c - 1] = count[c] + ret[f - 1]
    for n in tree[c]:
        if n != f:
            q.append((c, n))

print(*ret)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

d = ' '
n, q = map(int, input().split(d))

tree = defaultdict(lambda: [])
for _ in range(n - 1):
    a, b = map(int, input().split(d))
    tree[a].append(b)
    tree[b].append(a)

count = defaultdict(lambda: 0)
for _ in range(q):
    p, x = map(int, input().split(d))
    count[p] += x

ret = [0] * n
q = deque(maxlen=n)
q.append((1, 1))
while len(q) > 0:
    f, c = q.popleft()
    ret[c - 1] = count[c] + ret[f - 1]
    for n in tree[c]:
        if n != f:
            q.append((c, n))

print(*ret)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
from collections import defaultdict

def solve(n, q, AB, PX):
    count = defaultdict(int)
    for p, x in PX:
        count[p] += x

    tree = defaultdict(lambda: [])
    for a, b in AB:
        tree[a].append(b)
        tree[b].append(a)

    ret = [0] * n
    q = Queue()
    q.put((0, 1, count[1]))
    while not q.empty():
        f, c, x = q.get()
        count[c] += count[f]
        ret[c - 1] = count[c]
        for n in tree[c]:
            if n != f:
                q.put((c, n, count[c]))

    return ret

_n, _q = map(int, input().split())
_AB = [list(map(int, input().split())) for _ in range(_n - 1)]
_PX = [list(map(int, input().split())) for _ in range(_q)]
print(*solve(_n, _q, _AB, _PX))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8 
# Your code here!
import sys 
sys.setrecursionlimit(100000000)

N,Q=map(int,input().split()) 

l=[[i] for i in range(N)] 

#print(l) 
def dfs(num,point,visited): 
    visited[num]=1 
    point+=plus[num] 
    
    ans[num]=point 
    while l[num][-1]!=num: 
        temp=l[num].pop(-1) 
        if visited[temp]==0: 
            dfs(temp,point,visited) 
            
    return 0 

for _ in range(N-1): 
    a,b=map(int,input().split()) 
    l[a-1].append(b-1) 
    l[b-1].append(a-1) 
    
ans=[0]*N 
plus=[0]*N 

for _ in range(Q): 
    p,x=map(int,input().split()) 
    plus[p-1]+=x 

dfs(0,0,[0]*N) 

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, q = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

ans = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def DFS(node, p_node=-1):
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        ans[c_node] += ans[node]
        DFS(c_node, node)

sys.setrecursionlimit(2*n)
DFS(0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

N, Q = list(map(int, input().split()))
E = {}

# change limit for deep tree (recursion)
sys.setrecursionlimit(int(2e5+10))

for i in range(N-1):
  a,b = list(map(int, input().split()))
  a,b = a-1,b-1 # 1-indexed -> 0-indexed
  if a not in E:
    E[a] = [b]
  else:
    E[a].append(b)
  if b not in E:
    E[b] = [a]
  else:
    E[b].append(a)

P = [0] * N
for i in range(Q):
  a,b= list(map(int, input().split()))
  P[a-1] += b # 1-indexed -> 0-indexed
  
#print(E)
#print(P)

visited = [False for i in range(N)]
d = deque()

d.append(0)
while len(d) > 0:
  parent = d.pop()
  visited[parent] = True
  
  next_point = E[parent]
  
  for child in next_point:
    if visited[child]:
      continue
    P[child] += P[parent]
    d.append(child)
  
print(" ".join(list(map(str,P))))

Submission status: Time Limit Exceeded

Solution code:
import sys
n, q = map(int, input().split())
graph = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

query = []
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    query.append((p, x))

def DFS(node, p_node=-1):
    childs = [node]
    for c_node in graph[node]:
        if c_node==p_node:
            continue
        childs.extend(DFS(c_node, node))
    p_tree[node] = childs
    return childs

sys.setrecursionlimit(2*n)
p_tree = [None]*n
DFS(0)
ans = [0]*n
for p, x in query:
    for i in p_tree[p]:
        ans[i] += x
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

n, q = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(n - 1)]
values = [list(map(int, input().strip().split())) for _ in range(q)]


edge_dict = defaultdict(list)
value_dict = defaultdict(int)
total_value_dict = defaultdict(int)
visited = [False] * n

for a, b in edges:
    edge_dict[a].append(b)
    edge_dict[b].append(a)

for p, x in values:
    value_dict[p] += x

qu = deque([1])
total_value_dict[1] = value_dict[1]
visited[0] = True

while len(qu) > 0:
    node = qu.popleft()
    next_nodes = filter(lambda m: not visited[m - 1], edge_dict[node])
    for m in next_nodes:
        total_value_dict[m] = total_value_dict[node] + value_dict[m]
        visited[m - 1] = True
        qu.append(m)

print(' '.join([str(total_value_dict[i]) for i in range(1, n + 1)]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, q = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(n - 1)]
values = [list(map(int, input().strip().split())) for _ in range(q)]


edge_dict = defaultdict(list)
value_dict = defaultdict(int)
total_value_dict = defaultdict(int)
visited = [False] * n

for a, b in edges:
    edge_dict[a].append(b)
    edge_dict[b].append(a)

for p, x in values:
    value_dict[p] += x

queue = [1]
total_value_dict[1] = value_dict[1]
visited[0] = True

while len(queue) > 0:
    node = queue.pop(0)
    next_nodes = filter(lambda m: not visited[m - 1], edge_dict[node])
    for m in next_nodes:
        total_value_dict[m] = total_value_dict[node] + value_dict[m]
        visited[m - 1] = True
        queue.append(m)

print(' '.join([str(total_value_dict[i]) for i in range(1, n + 1)]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, q = map(int, input().strip().split())
edges = [list(map(int, input().strip().split())) for _ in range(n - 1)]
values = [list(map(int, input().strip().split())) for _ in range(q)]


edge_dict = defaultdict(list)
value_dict = defaultdict(int)
total_value_dict = defaultdict(int)
visited = [False] * n

for a, b in edges:
    edge_dict[a].append(b)
    edge_dict[b].append(a)

for p, x in values:
    value_dict[p] += x

queue = [1]
total_value_dict[1] = value_dict[1]
visited[0] = True

while len(queue) > 0:
    node = queue.pop(0)
    next_nodes = filter(lambda m: not visited[m - 1], edge_dict[node])
    for m in next_nodes:
        total_value_dict[m] = total_value_dict[node] + value_dict[m]
        visited[m - 1] = True
        queue.append(m)


for i in range(1, n + 1):
    end = '\n' if i == n else ' '
    print(total_value_dict[i], end=end)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())
to = [[] for _ in range(n)]
ans = [0]*n

for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

for i in range(q): 
    p,x = map(int,input().split())
    p -= 1
    ans[p] += x

def dfs(v,p):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u,v)

dfs(0,0)
for a in ans: print(a)

Submission status: Time Limit Exceeded

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

def input():
  return sys.stdin.readline()[:-1]

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])

Submission status: Time Limit Exceeded

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

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  temp = v[p]
  for i in temp:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [set() for _ in range(n)]
c = [0]*(n)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a-1].add(b-1)
  v[b-1].add(a-1)

for _ in range(q):
  p, x = map(int, input().split())
  c[p-1] += x

def addcount(p, prev, prec):
  c[p] += prec
  for i in v[p]:
    if i == prev:
      continue
    addcount(i, p, c[p])
  return None

addcount(0, 0, 0)
  
print(*c)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [set() for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].add(b)
  v[b].add(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev, prec):
  c[p] += prec
  for i in v[p]:
    if i == prev:
      continue
    addcount(i, p, c[p])
  return None
addcount(1, 0, 0)
  
print(*c[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [set() for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].add(b)
  v[b].add(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i == prev:
      continue
    c[i] += c[p]
    addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [set() for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].add(b)
  v[b].add(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  v[p].remove(prev)
  for i in v[p]:
    c[i] += c[p]
    addcount(i, p)
  return None
v[1].add(0)
addcount(1, 0)
  
print(' '.join(str(i) for i in c[1:]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [set() for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].add(b)
  v[b].add(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(' '.join(str(i) for i in c[1:]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

counter = defaultdict(lambda: 0)
parent_dict = defaultdict(lambda: 0)  # 親ノード
rank_dict = defaultdict(lambda: 0)  # 根からの距離

for p, x in px:
    counter[p] += x

# 根からの距離(after test用)
ab = sorted(ab)
for a, b in ab:
    if a == 1:
        rank_dict[b] = 1
        parent_dict[b] = 1
    else:
        if rank_dict[a] != 0 and rank_dict[b] == 0:
            rank_dict[b] = rank_dict[a] + 1
            parent_dict[b] = a
        elif rank_dict[a] == 0 and rank_dict[b] != 0:
            rank_dict[a] = rank_dict[b] + 1
            parent_dict[a] = b

rank_sorted = sorted(rank_dict.items(), key=lambda x: x[1])
for k, v in rank_sorted:
    counter[k] += counter[parent_dict[k]]

ans = []
for i in range(1, N+1):
    ans.append(counter[i])
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]

counter = defaultdict(lambda: 0)
parent_dict = defaultdict(lambda: 0)  # 親ノード
rank_dict = defaultdict(lambda: 0)  # 根からの距離

for p, x in px:
    counter[p] += x

# 根からの距離(after test用)
ab = sorted(ab)
for a, b in ab:
    if a == 1:
        rank_dict[b] = 1
        parent_dict[b] = 1
    else:
        if rank_dict[a] != 0 and rank_dict[b] == 0:
            rank_dict[b] = rank_dict[a] + 1
            parent_dict[b] = a
        elif rank_dict[a] == 0 and rank_dict[b] != 0:
            rank_dict[a] = rank_dict[b] + 1
            parent_dict[a] = b

rank_sorted = sorted(rank_dict.items(), key=lambda x: x[1])
for k, v in rank_sorted:
    counter[k] += counter[parent_dict[k]]

ans = []
for i in range(1, N+1):
    ans.append(counter[i])
print(" ".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q = map(int,input().split())
ab = [[] for i in range(N)]
for i in range(N-1):
    a,b = list(map(int,input().split()))
    a -= 1
    b -= 1
    ab[a].append(b)
    ab[b].append(a)
px = [0 for i in range(N)]
for i in range(Q):
    p,x = list(map(int,input().split()))
    px[p-1] += x
que = deque()
alr = []
alr.append(0)
que.append(0)
while que:
    q = que.popleft()
    sumq = px[q]
    for i in ab[q]:
        if i in alr:
            continue
        else:
            que.append(i)
            alr.append(i)
            px[i] += sumq
print(*px)