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 sys
sys.setrecursionlimit(10 ** 6)

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

edges = [[] for _ in range(N)]

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

counter = [0] * N
checked = [False] * N

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

def process(root):
    checked[root] = True
    for e in edges[root]:
        if checked[e] == False:
            counter[e] += counter[root]
            process(e)

process(0)

print(" ".join(map(str, counter)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

class Node(object):

    def __init__(self, id, person_id=None, children_id=[]):
        self.id = id
        self.person_id = person_id
        self.children_id = children_id
        self.counter = 0


# 標準入力とadj_dictの構築
N, Q = map(int, input().split())

adj_dict = defaultdict(list)
for i in range(N-1):
    ai, bi = map(int, input().split())
    adj_dict[ai].append(bi)
    adj_dict[bi].append(ai)


# グラフの構築
cur_id = 1
cur_node = Node(id=cur_id,
                person_id=None,
                children_id=[])
node_dict = {cur_id:cur_node}
open_list = deque()
open_list.append(cur_id)
while True:
    if len(open_list) == 0:
        break
    cur_id = open_list.pop()
    cur_node = node_dict[cur_id]
    adj_list = adj_dict[cur_id]
    for adj_id in adj_list:
        if adj_id != cur_node.person_id:
            cur_node.children_id.append(adj_id)
            open_list.append(adj_id)
            adj_node = Node(id=adj_id,
                            person_id=cur_id,
                            children_id=[])
            node_dict[adj_id] = adj_node

# 操作jを1つのnodeに対してのみ行う
cur_node = node_dict[1]
p, x = [], []
for i in range(Q):
    pi, xi = map(int, input().split())
    node = node_dict[pi]
    node.counter += xi

# 親ノードから天下り的に加算していく
cur_id = 1
open_list = deque()
open_list.append(cur_id)
while True:
    if len(open_list) == 0:
        break
    cur_id = open_list.pop()
    cur_node = node_dict[cur_id]
    if cur_node.person_id != None:
        cur_node.counter += node_dict[cur_node.person_id].counter
    for child_id in cur_node.children_id:
        open_list.append(child_id)

# 出力
res = []
for id in range(1, N+1):
    res.append(node_dict[id].counter)

print(*res)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

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

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

d = deque()
d.append(1)
chked = []
while d:
    stat = d.pop()
    chked.append(stat)
    for v in t[stat]:
        if v not in chked:
            d.append(v)
            cnt[v] += cnt[stat]

print(*cnt[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]


class Node:
    def __init__(self, val):
        self.val = val
        self.child_list = []
        self.cnt = 0

class my_tree:
    def __init__(self, tree_list):
        self.node_list = []

        for i in range(N):
            self.node_list.append(Node(i+1))

        for a, b in tree_list:
            a, b = int(a), int(b)

            child_node = self.node_list[b-1]
            parent_node = self.node_list[a-1]
            self.node_list[a-1].child_list.append(child_node)
            self.node_list[b-1].child_list.append(parent_node)
        
    def adding(self, query_list):
        for a, data in query_list:
            a, data = int(a), int(data)
            self.node_list[a-1].cnt += data

        stack = deque([self.node_list[0]])
        parent_node_list = [self.node_list[0]]*(N + 1)

        while True:
            v = stack.pop()
            for child in v.child_list:
                if child != parent_node_list[v.val -1]:
                    child.cnt += v.cnt
                    parent_node_list[child.val -1] = v
                    stack.append(child)
            
            if not stack:
                break


ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(item) for item in input().split()]

tree_list = [input().split() for j in range(1, N)]
query_list = [input().split() for k in range(Q)]


class Node:
    def __init__(self, val):
        self.val = val
        self.child_list = []
        self.cnt = 0

class my_tree:
    def __init__(self, tree_list):
        self.node_list = []

        for i in range(N):
            self.node_list.append(Node(i+1))

        for a, b in tree_list:
            a, b = int(a), int(b)

            child_node = self.node_list[b-1]
            parent_node = self.node_list[a-1]
            self.node_list[a-1].child_list.append(child_node)
            self.node_list[b-1].child_list.append(parent_node)
        
    def adding(self, query_list):
        for a, data in query_list:
            a, data = int(a), int(data)
            self.node_list[a-1].cnt += data

        stack = [self.node_list[0]]
        parent_node_list = [self.node_list[0]]*(N + 1)

        while True:
            v = stack.pop()
            for child in v.child_list:
                if child != parent_node_list[v.val -1]:
                    child.cnt += v.cnt
                    parent_node_list[child.val -1] = v
                    stack.append(child)
            
            if len(stack) == 0:
                break


ins = my_tree(tree_list)
ins.adding(query_list)
print(*[node.cnt for node in ins.node_list])

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    n, q = map(int, input().split())
    g = [[] for i in range(n+1)]
    point = [0 for i in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    for i in range(q):
        p, x = map(int, input().split())
        point[p] += x

    q = deque([[1,0]])
    for j in range(n):
        now = q.pop()
        point[now[0]] += point[now[1]]
        for i in g[now[0]]:
            if i==now[1]:
                continue
            q.append([i,now[0]])
    for i in range(1, n+1):
        print(point[i], end='')
        if i!=n:
            print(' ', end='')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    n, q = map(int, input().split())
    g = [[] for i in range(n+1)]
    point = [0 for i in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    for i in range(q):
        p, x = map(int, input().split())
        point[p] += x

    q = deque([[1,0]])
    q_append = q.append
    q_pop = q.pop
    for j in range(n):
        now = q_pop()
        point[now[0]] += point[now[1]]
        for i in range(len(g[now[0]])):
            if g[now[0]][i]==now[1]:
                continue
            q_append([g[now[0]][i],now[0]])
    for i in range(1, n+1):
        print(point[i], end='')
        if i!=n:
            print(' ', end='')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    n, q = map(int, input().split())
    g = [[] for i in range(n+1)]
    point = [0 for i in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    for i in range(q):
        p, x = map(int, input().split())
        point[p] += x

    q = deque([[1,0]])
    for j in range(n):
        now = q.pop()
        point[now[0]] += point[now[1]]
        for i in range(len(g[now[0]])):
            if g[now[0]][i]==now[1]:
                continue
            q.append([g[now[0]][i],now[0]])
    for i in range(1, n+1):
        print(point[i], end='')
        if i!=n:
            print(' ', end='')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, q = map(int, input().split())
g = [[] for i in range(n+1)]
point = [0 for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    point[p] += x

q = deque([[1,0]])
for j in range(n):
    now = q.pop()
    point[now[0]] += point[now[1]]
    for i in range(len(g[now[0]])):
        if g[now[0]][i]==now[1]:
            continue
        q.append([g[now[0]][i],now[0]])
for i in range(1, n+1):
    print(point[i], end='')
    if i!=n:
        print(' ', end='')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, q = map(int, input().split())
g = [[] for i in range(n+1)]
point = [0 for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    point[p] += x

q = deque([[1,0]])
while len(q)!=0:
    now = q.pop()
    point[now[0]] += point[now[1]]
    for i in range(len(g[now[0]])):
        if g[now[0]][i]==now[1]:
            continue
        q.append([g[now[0]][i],now[0]])

for i in range(1, n+1):
    print(point[i], end='')
    if i!=n:
        print(' ', end='')

Submission status: Time Limit Exceeded

Solution code:
import heapq
n, q = map(int, input().split())
g = [[] for i in range(n+1)]
point = [0 for i in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)
for i in range(q):
    p, x = map(int, input().split())
    point[p] += x

q = [[1,0]]
heapq.heapify(q)
while len(q)!=0:
    now = heapq.heappop(q)
    point[now[0]] += point[now[1]]
    for i in range(len(g[now[0]])):
        if g[now[0]][i]==now[1]:
            continue
        heapq.heappush(q,[g[now[0]][i],now[0]])

for i in range(1, n+1):
    print(point[i], end='')
    if i!=n:
        print(' ', end='')
print('')

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
L = [0]*n
ans = [0]*n
par = [i for i in range(n)]
for i in range(n-1):
    s,t = map(int,input().split())
    par[t-1] = s-1
for i in range(q):
    s,t = map(int,input().split())
    L[s-1] += t
for i in range(n):
    x = n-i-1
    px = x
    while px != 0:
        ans[x] += L[px]
        px = par[px]
for i in range(n):
    ans[i] += L[0]
print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
import math
import heapq
import bisect

MOD = 10**9+7

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

node = [0]*N
edge = [[] for _ in range(N)]
color = [0]*N

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

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

stack = [0]
while stack:
    s = stack.pop(0)
    color[s] = 1
    for t in edge[s]:
        if color[t]==0:
            stack.append(t)
            node[t] += node[s]
    color[s]=2

for n in node:
    print(n)

Submission status: Time Limit Exceeded

Solution code:
#coding: utf-8
import sys
import math
import heapq
import bisect

sys.setrecursionlimit(200000)
MOD = 10**9+7

def dfs(x,node,edge,color):
    color[x]=1
    for i in edge[x]:
        if color[i]==0:
            node[i]+=node[x]
            dfs(i,node,edge,color)
    color[x]=2

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

node = [0]*N
edge = [[] for _ in range(N)]
color = [0]*N

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

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

dfs(0,node,edge,color)

for n in node:
    print(n)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
n,q=map(int,input().split())
A=[[] for i in range(n)]
node=[0]*n

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

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


def calculate(num,pre=-1):
    for i in A[num]:
        if i==pre:continue
        node[i] +=node[num]
        calculate(i,num)


calculate(0)
print(*node)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())
A=[[] for i in range(n)]
node=[0]*n

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

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


def calculate(num,pre=-1):
    for i in A[num]:
        if i==pre:continue
        node[i] +=node[num]
        calculate(i,num)


calculate(0)
print(*node)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

p=[-1]*(n+1)
p[1]=0
chi=[[] for _ in range(n+1)]
q=queue.Queue()
q.put(1)

#while not q.empty():
for _ in range(n-1):
    t=q.get()
    for x in v[t]:
        if(p[x]==-1):
            chi[t].append(x)
            p[x]=t
            q.put(x)

s=[0]*(n+1)
for i in range(qq):
    ver,poi=map(int,input().split())
    s[ver]+=poi

q.put(1)
#while not q.empty():
for _ in range(n):
    t=q.get()
    for x in chi[t]:
        s[x]+=s[t]
        q.put(x)
for i in range(1,n+1):
    print(s[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import queue
n,qq=map(int,input().split())
v=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    v[a].append(b)
    v[b].append(a)

p=[-1]*(n+1)
p[1]=0
chi=[[] for _ in range(n+1)]
q=queue.Queue()
q.put(1)
while not q.empty():
    t=q.get()
    for x in v[t]:
        if(p[x]==-1):
            chi[t].append(x)
            p[x]=t
            q.put(x)
"""
for i in range(1,n+1):
    print(p[i],chi[i])
    """
s=[0]*(n+1)
for i in range(qq):
    ver,poi=map(int,input().split())
    s[ver]+=poi
    
q.put(1)
while not q.empty():
    t=q.get()
    for x in chi[t]:
        s[x]+=s[t]
        q.put(x)
for i in range(1,n+1):
    print(s[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
import queue
n,qq=map(int,input().split())
v=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    v[a].append(b)
    v[b].append(a)

p=[-1]*(n+1)
p[1]=0
chi=[[] for _ in range(n+1)]
q=queue.Queue()
q.put(1)
while not q.empty():
    t=q.get()
    for x in v[t]:
        if(p[x]==-1):
            chi[t].append(x)
            p[x]=t
            q.put(x)
"""
for i in range(1,n+1):
    print(p[i],chi[i])
    """
s=[0]*(n+1)
for i in range(qq):
    ver,poi=map(int,input().split())
    s[ver]+=poi
    
q.put(1)
while not q.empty():
    t=q.get()
    for x in chi[t]:
        s[x]+=s[t]
        q.put(x)
for i in range(1,n+1):
    print(s[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
import collections


def main():
    n, q = map(int, input().split())

    # 頂点のリスト、ポイント、走査済みか
    graph = [[[], 0, False] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a-1][0].append(b-1)
        graph[b-1][0].append(a-1)

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

    queue = collections.deque([0])
    while queue:
        q = queue.pop()
        graph[q][2] = True
        for v in graph[q][0]:
            if graph[v][2]:
                continue
            graph[v][1] += graph[q][1]
            queue.append(v)

    for i in range(n):
        print(graph[i][1], end=' ')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())

    # 頂点のリスト、ポイント、走査済みか
    graph = [[[], 0, False] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a-1][0].append(b-1)
        graph[b-1][0].append(a-1)

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

    queue = [0]
    while queue:
        q = queue.pop()
        graph[q][2] = True
        for v in graph[q][0]:
            if graph[v][2]:
                continue
            graph[v][1] += graph[q][1]
            queue.append(v)

    for i in range(n):
        print(graph[i][1], end=' ')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q = map(int,input().split())
edge = [[]for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
tree = [0]*N
for i in range(Q):
    p,x = map(int,input().split())
    tree[p-1] += x
flag = [0]*N
flag[0] = 1
queue = deque([0])
while queue != deque([]):
    p = queue.popleft()
    for i in edge[p]:
        if flag[i] == 0:
            flag[i] = 1
            tree[i] += tree[p]
            queue.append(i)

for i in tree:
    print(i,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
from queue import *
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
dfs(1,0)
for i in range(1,n+1):
    print("{} ".format(tree_value[i]), end = "")

Submission status: Time Limit Exceeded

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

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

adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
"""
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
"""
used = [0 for i in range(n+1)]
que = Queue()
que.put(1)
while que.qsize() != 0:
    m = que.get()
    used[m] = 1
    for i in adjacent_list[m]:
        if not used[i]:
            tree_value[i] += tree_value[m]
            que.put(i)
for i in range(1,n+1):
    print("{} ".format(tree_value[i]), end = "")

Submission status: Time Limit Exceeded

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

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

adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
dfs(1,0)
for i in range(1,n+1):
    print("{} ".format(tree_value[i]), end = "")

Submission status: Time Limit Exceeded

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

n, q = list(map(int, input().split()))
adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
dfs(1,0)
for i in range(1,n+1):
    print(tree_value[i])

Submission status: Time Limit Exceeded

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

n, q = list(map(int, input().split()))
adjacent_list = [[] for i in range(n+1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
tree_value = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    tree_value[p] += x
searched = set()
def dfs(node, count):
    searched.add(node)
    tree_value[node] += count
    for i in adjacent_list[node]:
        if i not in searched:
            dfs(i, tree_value[node])
dfs(1,0)
for i in range(1,n+1):
    print(tree_value[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N, Q = map(int, input().split())
 
AB = [[int(x) for x in input().split()] for _ in range(N-1)] 
PX = [[int(x) for x in input().split()] for _ in range(Q)] 
 
graph = [[] for _ in range(N+1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)
 
value = [0] * (N+1)
for p, x in PX:
    value[p] +=x
 
def dfs(v, parent, add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x, v, value[v])
 
dfs(1, 0, 0)
ans = ' '.join(map(str,value[1:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

tally = [0 for i in range(N+1)]
for i in range(Q):
    p, x = map(int, input().split())
    tally[p] += x

count = [0 for i in range(N + 1)]
visited = [False for i in range(N+1)]
def dfs(root, curCount):
    visited[root] = True
    curCount += tally[root]
    count[root] = curCount
    for neighbour in edges[root]:
        if visited[neighbour]: continue
        dfs(neighbour, curCount)

dfs(1, 0)

print(*count[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,Q=map(int,input().split())
out=[set() for i in range(N+1)];out[0]=None # 頂点は1-initial
for j in range(N-1):
    a,b=map(int,input().split())
    out[a].add(b)
    out[b].add(a)
# print(out) #DB

a=[0 for i in range(N+1)];a[0]=None

for k in range(Q):
    p,x=map(int,input().split())
    a[p]+=x

# print(a) #DB
r=[False for i in range(N+1)];r[0]=None
q=deque()
q.append(1);r[1]=True
while q:
    u=q.popleft()
    for v in out[u]:
        if not r[v]:
            a[v]+=a[u]
            q.append(v)
            r[v]=True
            # print(q) #DB

print(*a[1:])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import deque
    N, Q = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    cost = [0]*N
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    for _ in range(Q):
        p, x = (int(i) for i in input().split())
        cost[p-1] += x
    G_color = ['WHITE' for _ in range(len(G))]
    G_parent = ['NIL' for _ in range(len(G))]

    def bfs(s):
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_parent[v] = u
                    Q.append(v)
            G_color[u] = 'BLACK'

    def dfs(v):
        seen = [False] * N
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v] or next_v == G_parent[u]:
                    continue
                seen[next_v] = True
                todo.append(next_v)
                cost[next_v] += cost[G_parent[next_v]]
                break
            else:
                todo.pop()

    bfs(0)
    dfs(0)
    print(*cost)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    from collections import deque
    N, Q = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    cost = [0]*N
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    G_color = ['WHITE' for _ in range(len(G))]
    G_parent = ['NIL' for _ in range(len(G))]

    def bfs(s):
        G_color[s] = 'GRAY'
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_parent[v] = u
                    Q.append(v)
            G_color[u] = 'BLACK'

    def dfs(v, x):
        seen = [False] * N
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v] or next_v == G_parent[u]:
                    continue
                seen[next_v] = True
                todo.append(next_v)
                break
            else:
                w = todo.pop()
                cost[w] += x

    bfs(0)
    for _ in range(Q):
        p, x = (int(i) for i in input().split())
        dfs(p-1, x)
    print(*cost)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from collections import deque
    N, Q = (int(i) for i in input().split())
    G = [[] for _ in range(N)]
    cost = [0]*N
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    G_color = ['WHITE' for _ in range(len(G))]
    G_distance = [float('inf') for _ in range(len(G))]
    G_parent = ['NIL' for _ in range(len(G))]

    def bfs(s):
        """
        breadth-first search
        -----
        G_color: BLACK if visited, GRAY if discovered, but will
             visit, WHITE if not discovered
        G_distance: a distance from s to v when algorithm computed
        G_parent: a predecessor of v. NIL if it not exist
        """
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    Q.append(v)
            G_color[u] = 'BLACK'

    def dfs(v, x):
        seen = [False] * N
        todo = []
        seen[v] = True
        todo.append(v)
        while todo:
            u = todo[-1]
            for next_v in G[u]:
                if seen[next_v] or next_v == G_parent[u]:
                    continue
                seen[next_v] = True
                todo.append(next_v)
                break
            else:
                w = todo.pop()
                cost[w] += x

    bfs(0)
    for _ in range(Q):
        p, x = (int(i) for i in input().split())
        dfs(p-1, x)
    print(*cost)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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

dfs(0, -1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
G = [[]for i in range(N+1)]

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

stack = [1]
t = [False]*(N+1)
t[1] = True
while len(stack) > 0:
    a = stack.pop(0)
    for b in G[a]:
        if not t[b]:
            t[b] = True
            stack.append(b)
            C[b] += C[a]
C.pop(0)
print(*C)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
G = [[]for i in range(N+1)]

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

stack = [1]
list = []
while len(stack) > 0:
    a = stack.pop(0)
    list.append(a)
    for b in G[a]:
        G[b].remove(a)
        stack.append(b)
        C[b] += C[a]
C.pop(0)
print(*C)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
G = [[]for i in range(N+1)]

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

stack = [1]
list = []
while len(stack) > 0:
    a = stack.pop(0)
    list.append(a)
    for b in G[a]:
        if b not in list:
            stack.append(b)
            C[b] += C[a]
C.pop(0)
print(*C)