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 itertools
# import math
import sys
sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque
# import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, Q = map(int, input().split())
# A = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
# A_B = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

edges = [list(map(int,input().split())) for _ in range(N - 1)]
tree = [[] for _ in range(N + 1)]

for edge in edges:
    tree[edge[0]].append([edge[1]])
    tree[edge[1]].append([edge[0]])

depth = [-1] * (N + 1)
depth[1] = 0
count = [0] * (N + 1)

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

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + 1
#             dfs(tree, l[0])
# dfs(tree, 1)
def dfs(tree, s):
    for l in tree[s]:
        if depth[l[0]] == -1:
            depth[l[0]] = 0
            count[l[0]] += count[s]
            dfs(tree, l[0])
dfs(tree, 1)


for i in count[1:]:
    print(i, end = ' ')

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr



# bfs
# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0

# d = deque()
# d.append(1)

# ans = [0] * (N + 1)
# while d:
#  v = d.popleft()
#  for i in tree[v]:
#    if depth[i] != -1:
#      continue
#    depth[i] = depth[v] + 1
#    ans[i] = v
#    d.append(i)

# # ans = depth[2:]
# print('Yes')
# print(*ans[2:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# import itertools
# import math
import sys
sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque
# import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, Q = map(int, input().split())
# A = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
# A_B = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

edges = [list(map(int,input().split())) for _ in range(N - 1)]
tree = [[] for _ in range(N + 1)]

for edge in edges:
    tree[edge[0]].append([edge[1]])
    tree[edge[1]].append([edge[0]])

depth = [-1] * (N + 1)
depth[1] = 0
count = [0] * (N + 1)

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

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + 1
#             dfs(tree, l[0])
# dfs(tree, 1)
def dfs(tree, s):
    for l in tree[s]:
        if depth[l[0]] == -1:
            depth[l[0]] = depth[s] + 1
            count[l[0]] += count[s]
            dfs(tree, l[0])
dfs(tree, 1)


for i in count[1:]:
    print(i, end = ' ')

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr



# bfs
# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0

# d = deque()
# d.append(1)

# ans = [0] * (N + 1)
# while d:
#  v = d.popleft()
#  for i in tree[v]:
#    if depth[i] != -1:
#      continue
#    depth[i] = depth[v] + 1
#    ans[i] = v
#    d.append(i)

# # ans = depth[2:]
# print('Yes')
# print(*ans[2:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# import itertools
# import math
import sys
sys.setrecursionlimit(500*500)
# import numpy as np
# from collections import deque
# import heapq

# N = int(input())
# S = input()
# n, *a = map(int, open(0))
N, Q = map(int, input().split())
# A = list(map(int, input().split()))
# A = list(map(lambda x: int(x)*(-1), input().split()))
# B = list(map(int, input().split()))
# A_B = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

edges = [list(map(int,input().split())) for _ in range(N - 1)]
tree = [[] for _ in range(N + 1)]

for edge in edges:
    tree[edge[0]].append([edge[1]])
    tree[edge[1]].append([edge[0]])

depth = [-1] * (N + 1)
depth[1] = 0

def dfs(tree, s):
    for l in tree[s]:
        if depth[l[0]] == -1:
            depth[l[0]] = depth[s] + 1
            dfs(tree, l[0])
dfs(tree, 1)

count = [0] * (N + 1)

def dfs2(tree, s, d, x):
    for l in tree[s]:
        if d < depth[l[0]]:
            count[l[0]] += x
            dfs2(tree, l[0], depth[l[0]], x)

for i in range(Q):
    p, x = map(int, input().split())
    count[p] += x
    dfs2(tree, p, depth[p], x)

for i in count[1:]:
    print(i, end = ' ')

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr




# tree = [[] for _ in range(N + 1)]
# edges = [list(map(int,input().split())) for _ in range(M)]

# for edge in edges:
#     tree[edge[0]].append(edge[1])
#     tree[edge[1]].append(edge[0])

# depth = [-1] * (N + 1)
# depth[1] = 0

# d = deque()
# d.append(1)

# ans = [0] * (N + 1)
# while d:
#  v = d.popleft()
#  for i in tree[v]:
#    if depth[i] != -1:
#      continue
#    depth[i] = depth[v] + 1
#    ans[i] = v
#    d.append(i)

# # ans = depth[2:]
# print('Yes')
# print(*ans[2:], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def perm(n,mod=None):
    ans = 1
    for i in range(1,n+1):
        ans *= i
        if mod!=None:
            ans %= mod
    return ans
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    return C

N,Q=mint()
node=[list() for _ in range(N+1)]
parent=[0]*(N+1)
parent[1]=-1
X=[0]*(N+1)
for _ in range(N-1):
    a,b=mint()
    node[a].append(b)
    node[b].append(a)
for _ in range(Q):
    p,x=mint()
    X[p]+=x
q=deque([1])
while len(q)>0:
    i=q.popleft()
    for j in node[i]:
        if parent[j]==0:
            parent[j]=i
            q.append(j)
ans=[]
for i in range(1,N+1):
    tmp=0
    while True:
        tmp+=X[i]
        i=parent[i]
        if i<0:
            break
    ans.append(tmp)
lprint(ans,' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n, q = map(int, input().split())
es = [[] for i in range(n)]
for i in range(n - 1):
   a, b = map(int, input().split())
   es[a - 1].append(b - 1)
   es[b - 1].append(a - 1)
use = [1] * n
cnt = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p - 1] += x


def dfs(v, c):
    k = c + cnt[v]
    cnt[v] = k
    use[v] = 0
    for i in es[v]:
        if use[i]:
            dfs(i, k)


dfs(0, 0)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import collections

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

c = [[] for _ in range(n)]
for a, b in ab:
    a, b = a-1, b-1
    c[a].append(b)
    c[b].append(a)

point = [0] * n
for p, x in px:
    point[p-1] += x

tree = [-1] * n
q = collections.deque()
q.append(0)
while q:
    v = q.pop()
    for i in c[v]:
        if i == tree[v]:
            continue
        tree[i] = v
        q.append(i)

p = set([p-1 for p, x in px])
ans = [0] * n
for i in p:
    q.append(i)
    while q:
        v = q.pop()
        ans[v] += point[i]
        for j in c[v]:
            if j == tree[v]:
                continue
            q.append(j)
print(' '.join(list(map(str, ans))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import numpy as np

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

link = [[] for _ in range(N)]
for i in range(N-1):
    link[A[i][0]-1].append(A[i][1]-1)
    link[A[i][1]-1].append(A[i][0]-1)

dist = [-1 for _ in range(N)]
ans = [0 for _ in range(N)]
parent = [0 for _ in range(N)]
dist[0] = 0
d = deque([0])
while d:
    now = d.popleft()
    for i in range(len(link[now])):
        if dist[link[now][i]] == -1:
            dist[link[now][i]] = now + 1
            d.append(link[now][i])
            parent[link[now][i]] = now

P.sort()
for i in range(Q):
    ans[P[i][0] - 1] += P[i][1]

arg_dist = list(np.argsort(np.array(dist)))
for i in range(N):
    if i != 0:
        ans[arg_dist[i]] = ans[arg_dist[i]] + ans[parent[arg_dist[i]]]

for i in range(N):
    if i != N - 1:
        print(ans[i], end=" ")
    else:
        print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
trees=[0 for _ in range(N)]
numbers=[]
for _ in range(N-1):
    a,b=map(int,input().split())
    numbers.append([a,b])
while numbers:
    number=numbers.pop(0)
    a=number[0]
    b=number[1]
    if a!=1 and trees[a-1]==0 and trees[b-1]==0:
        numbers.append([a,b])
    elif trees[b-1]==0:
        trees[b-1]=a
    else:
        trees[a-1]=b
answers=[0 for _ in range(N)]
for _ in range(Q):
    p,x=map(int,input().split())
    answers[p-1]+=x
answers_dict={}
for n in range(N):
    answers_dict[n]=trees[n]
sort_answers=sorted(answers_dict.items(), key=lambda x:x[1])
for n in range(N):
    num=sort_answers[n][0]
    if trees[num]==0:
        continue
    answers[num]+=answers[sort_answers[n][1]-1]
print(*answers)

Submission status: Time Limit Exceeded

Solution code:
# D - Ki TLE
import sys
sys.setrecursionlimit(10**6)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b が根と繋がっているとき
    else:
        G[b].append(a)
    if a == 0:
        root.add(b)

lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

seen = [False]*N
cnt = [0]*N
def dfs(v,point,seen):
    seen[v] = True# v を訪問済みにする
    cnt[v] += point
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        dfs(next_v,point,seen)

for p,x in lst:
    seenC = seen.copy()
    dfs(p,x,seenC)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
# D - Ki
import sys
sys.setrecursionlimit(10**6)
N,Q = map(int,input().split())

# 有向グラフ
G = [[] for _ in range(N)]
root = set()
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    if not(b in root):
        G[a].append(b)
    # b が根と繋がっているとき
    else:
        G[b].append(a)
    if a == 0:
        root.add(b)

lst = []
for _ in range(Q):
    P,X = map(int,input().split())
    P-=1
    lst.append((P,X))

seen = [False]*N
cnt = [0]*N
def dfs(v,point,seen):
    seen[v] = True# v を訪問済みにする
    cnt[v] += point
    # v から行ける各頂点 next_v について
    for next_v in G[v]:
        # next_v が探索済みならスルー
        if seen[next_v] == True:
             continue
        dfs(next_v,point,seen)

for p,x in lst:
    seenC = seen.copy()
    dfs(p,x,seenC)
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

n, q = map(int, input().split())
ab = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
add = [0]*n
for _ in range(q):
    pp, xx = map(int, input().split())
    add[pp-1] += xx


def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in ab[v]:
        if c == p:
            continue
        dfs(c, v, value)


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

Submission status: Time Limit Exceeded

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

stack=deque([0])
visited=[0]*n
visited[0]=1

while stack:
    cur=stack[-1]
    for i in tree[cur]:
        if visited[i]==0:
            cnt[i]+=cnt[cur]
            stack.append(i)
            visited[i]=1
            break
    else:
        stack.pop()

print(*cnt)

Submission status: Time Limit Exceeded

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

stack=deque([0])
visited=[0]*n
visited[0]=1

while stack:
    cur=stack[-1]
    for i in tree[cur]:
        if visited[i]==0:
            cnt[i]+=cnt[cur]
            stack.append(i)
            visited[i]=1
            break
    else:
        stack.pop()

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
input = sys.stdin.readline


def dfs(now):
    seen[now] = True
    for next in branch[now]:
        if seen[next] is False:
            score[next] += score[now]
            dfs(next)


N, Q = map(int, input().split())
branch = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    branch[a - 1].add(b - 1)
    branch[b - 1].add(a - 1)
score = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    score[p - 1] += x

seen = [False] * N
for i in range(N):
    if seen[i] is False:
        dfs(i)

print(*score)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
from sys import setrecursionlimit

setrecursionlimit(10 ** 8)


def dfs(now):
    seen[now] = True
    for next in branch[now]:
        if seen[next] is False:
            tree[now].append(next)
            dfs(next)
    return tree


N, Q = map(int, input().split())
branch = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    branch[a - 1].add(b - 1)
    branch[b - 1].add(a - 1)
operation = [list(map(int, input().split())) for _ in range(Q)]

seen = [False] * N
tree = [[] for _ in range(N)]
for i in range(N):
    if seen[i] is False:
        dfs(i)
lst = []
for i in range(N):
    res = []
    tmp_lst = deque([i])
    while tmp_lst:
        now = tmp_lst.pop()
        res.append(now)
        for next in tree[now]:
            tmp_lst.append(next)
    lst.append(res)

score = [0 for _ in range(N)]
for q in operation:
    root, pnt = q
    root -= 1
    for i in lst[root]:
        score[i] += pnt

for ans in score:
    print(ans, end=' ')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import deque
from sys import setrecursionlimit

setrecursionlimit(10 ** 8)


def dfs(now):
    seen[now] = True
    for next in branch[now]:
        if seen[next] is False:
            tree[now].append(next)
            dfs(next)
    return tree


N, Q = map(int, input().split())
branch = [set() for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    branch[a - 1].add(b - 1)
    branch[b - 1].add(a - 1)
operation = [list(map(int, input().split())) for _ in range(Q)]

seen = [False] * N
tree = [[] for _ in range(N)]
for i in range(N):
    if seen[i] is False:
        dfs(i)
score = [0 for _ in range(N)]
for q in operation:
    root, pnt = q
    root -= 1
    tmp_lst = deque([root])
    while tmp_lst:
        now = tmp_lst.pop()
        score[now] += pnt
        for next in tree[now]:
            tmp_lst.append(next)

for ans in score:
    print(ans, end=' ')

Submission status: Time Limit Exceeded

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

s=[-1 for i in range(n)]
sc=[0]
s[0]=0
while sc:
  nsc=[]
  for i in sc:
    s[i]+=ps[i]
    for j in e[i]:
      if s[j]==-1:
        nsc.append(j)
        s[j]=s[i]
  sc=nsc

r=""
for i in range(n):
  r+=str(s[i])+" "
print(r[:-1])

Submission status: Time Limit Exceeded

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

def solve():
    N, Q = map(int, input().split())
    graph = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        graph[a].append(b)
        graph[b].append(a)
    ans = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x
    def dfs(cur, pre):
        for to in graph[cur]:
            if to == pre:
                continue
            ans[to] += ans[cur]
            dfs(to, cur)
    dfs(0, -1)
    print(*ans)
    return

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)

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

graph = defaultdict(list)
for _ in range(n-1):
    p,c = list(map(int, input().split()))
    graph[p].append(c)
    graph[c].append(p)

counter = defaultdict(int)
for _ in range(q):
    i,c = list(map(int, input().split()))
    counter[i] += c

ans = [0] * (n + 1)
visit = [False] * (n + 1)
def dfs(node, total_counter):
    visit[node] = True
    total_counter += counter.get(node, 0)
    
    for child in graph[node]:
        if not visit[child]:
            dfs(child, total_counter)
    ans[node] = total_counter

dfs(1, 0)

print(*ans[1:])

Submission status: Time Limit Exceeded

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

adj_list = [[] for _ in range(N)]
counter = [0 for _ in range(N)]

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

def df(current, score, residual):
    residual = list(set(residual)-set([current]))
    next_nodes = adj_list[current]
    next_nodes = [node for node in next_nodes
            if node in residual]
    for node in next_nodes:
        counter[node]+=score
        df(node, counter[node], residual)

for _ in range(Q):
    p,x=map(int, input().split())
    counter[p-1]+=x
df(0, counter[0], list(range(N)))
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q = map(int,input().split())
from collections import deque
g = [[] for _ in range(n)]
fi = [0]*n
for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
ls = [list(map(int,input().split())) for _ in range(q)]
def bfs(u):
    q = deque([u])
    d = [None]*n
    d[u] = 0
    while q:
        v = q.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                q.append(i)
    return d
ans = 0
for j in range(q):
    di = list(map(lambda x,y:x-y,bfs(0),bfs(ls[j][0]-1)))
    for k in range(len(di)):
        if di[k] == bfs(0)[ls[j][0]-1]:
            fi[k] += ls[j][1]                           
print(*fi)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(400000)
n,q=map(int,input().split())
ans=[0]*(n+1) #答え
score=[0]*(n+1) #xの総和
g=[[] for _ 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 j in range(q):
    p,x=map(int,input().split())
    score[p]+=x

visited=[0]*(n+1)
def dfs(v):
    visited[v]+=1
    global ans
    ans[v]+=score[v]
    for i in range(len(g[v])):
        ans[g[v][i]]+=ans[v]
        dfs(g[v][i])
dfs(1)
print(" ".join(map(str, ans[1:])))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(400000)
n,q=map(int,input().split())
ans=[0]*(n+1) #答え
score=[0]*(n+1) #xの総和
g=[[] for _ 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 j in range(q):
    p,x=map(int,input().split())
    score[p]+=x

visited=set()
def dfs(v):
    visited.add(v)
    global ans
    ans[v]+=score[v]
    for i in range(len(g[v])):
        if not g[v][i] in visited:
            ans[g[v][i]]+=ans[v]
            dfs(g[v][i])
dfs(1)
ans_chr=""
for i in range(1,n+1):
    ans_chr=ans_chr+str(ans[i])+" "
print(ans_chr)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
# INF =  float("inf")
INF = 10**18
import bisect
import statistics
mod = 10**9+7
# mod = 998244353

## a, bを無向辺として，隣接リストを作成
N, Q = list(map(int, input().split()))
al = [[] for i in range(N)]

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a-1].append(b-1)
    al[b-1].append(a-1)

visited = [0 for i in range(N)]
seen = [0 for i in range(N)]
score = [0 for i in range(N)]

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

@functools.lru_cache(None)
def dfs_rec(u):
    visited[u] = 1
    for v in al[u]:
        if visited[v] == 0:
            score[v] += score[u]
            dfs_rec(v)

dfs_rec(0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline

def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))

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

#読み込み
N, Q = ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = mina(*ints())
    tree[a].append(b)
    tree[b].append(a)
cnt = [0] * N
for _ in range(Q):
    q, x = ints()
    cnt[q - 1] += x
cnt.append(0)  # -1アクセス用

#本処理
def dfs(u, p):  # uは現在のノード、pは親のノード
    cnt[u] += cnt[p]
    for nv in tree[u]:
        if nv == p:
            continue
        dfs(nv, u)
dfs(0, -1)
print(*cnt[:-1])

Submission status: Time Limit Exceeded

Solution code:
# 木上の累積和

import sys
from collections import defaultdict
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))


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


N, Q = ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = mina(*ints())
    tree[a].append(b)
    tree[b].append(a)
cnt = [0] * N
for _ in ra(Q):
    q, x = ints()
    cnt[q - 1] += x
cnt.append(0)  # -1アクセス用

# dfsでcntに木に沿った累積和をsetしていく


def dfs(u, p):  # uは現在のノード、pは親のノード
    cnt[u] += cnt[p]
    for nv in tree[u]:
        if nv == p:
            continue
        dfs(nv, u)


dfs(0, -1)

print(*cnt[:-1])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
lst=[[] for i in range(n)]
ans=[0]*n

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

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

Q=[0]

flag=[True]+[False]*(n-1)


while Q:
  v=Q.pop(0)
  flag[v]=True
  for i in lst[v]:
    if flag[i]:
      continue
    flag[i]=True
    ans[i]+=ans[v]
    Q.append(i)


print(' '.join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
lst=[[] for i in range(n)]
ans=[0]*n

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

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

Q=[0]

flag=[True]+[False]*(n-1)


while Q:
  v=Q.pop(0)
  flag[v]=True
  cnt=ans[v]
  for i in lst[v]:
    if flag[i]:
      continue
    else:
      flag[i]=True
      ans[i]+=cnt
      Q.append(i)


print(' '.join([str(i) for i in ans]))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
lst=[[] for i in range(n)]
ans=[0]*n

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

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

Q=[0]

flag=[True]+[False]*(n-1)


while Q:
  v=Q.pop(0)
  cnt=ans[v]
  for i in lst[v]:
    if flag[i]:
      continue
    else:
      flag[i]=True
      ans[i]+=cnt
      Q.append(i)

ans=[str(i) for i in ans]

print(' '.join(ans))

Submission status: Time Limit Exceeded

Solution code:
# n=int(input())
import sys
sys.setrecursionlimit(10**7)
n, q = map(int, input().split())
# vl=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
adjl = [[] for _ in range(n+1)]
for i in range(n-1):
    a, b = map(int, input().split())
    adjl[a].append(b)
    adjl[b].append(a)
c = [0 for _ in range(n+1)]
point = [0 for _ in range(n+1)]


def dfs(p, u, add):
    global point
    point[u] = c[u]+add
    for v in adjl[u]:
        if v == p:
            continue
        dfs(u, v, point[u])


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


dfs(0, 1, 0)
point.remove(0)
print(*point, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**7)
#累積和を木に拡張する
N, Q = map(int, input().split())

graph = [[] for i in range(N)]
score = [0 for _ in range(N)]

def dfs(now, prev):

    for adj in graph[now]:
        if adj == prev:
            continue
        score[adj] += score[now]
        dfs(adj, now)

    return

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

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

    score[p-1] += x

dfs(0, -1)

for p in score:
    print(p)