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:
# 20/5/28
import sys
sys.setrecursionlimit(3 * 10 ** 5)

def bfs(root):
    global AL, cnt, visited
    visited[root] = True
    for v in AL[root]:
        if not visited[v]:
            cnt[v] += cnt[root]
            bfs(v)

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

cnt = [0] * (N + 1)
for j in range(Q):
    p, x = [int(x) for x in input().split()]
    cnt[p] += x

visited = [False] * (N + 1)
bfs(1)
s = " ".join(map(str, cnt[1:]))
print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,q = map(int,input().split())
tree = [[] for _ in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
ans = [0]*n
for i in range(q):
    p,x = map(int,input().split())
    ans[p-1] += x
done = [0]*n
def dfs(now,m):
    done[now] = 1
    ans[now] += m
    for i in tree[now]:
        if not done[i]:
            dfs(i,ans[now])
dfs(0,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

class Node(object):
    def __init__(self, num):
        self.num = num
        self.adjacency_list = []
        self.values = 0
        self.visited = False

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

node = [Node(num=i) for i in range(N)]

for i in range(N - 1): # 0 ~ N-2
#     exec("a"+str(ab[i][0])+".adjacency_list.append("+str(ab[i][1])+")")#a>b
#     exec("a"+str(ab[i][1])+".adjacency_list.append("+str(ab[i][0])+")")#b>a
    node[ab[i][1]-1].adjacency_list.append(ab[i][0]-1)
    node[ab[i][0]-1].adjacency_list.append(ab[i][1]-1)
    #append使った

for i in range(Q):
    node[px[i][0]-1].values +=px[i][1]

def dfs138(parent, n, val_p): #children is list
    node[n].values += val_p #parent kara keisyou
    val_n = node[n].values #val_n toshite syotoku
    adj = node[n].adjacency_list
    for i in adj:
        if(i != parent):
            dfs138(n, i, val_n) #val_nを流す
#finish

dfs138([],0,0)

output = []
for n in range(N):
    val_n = node[n].values
    output.append(val_n)
print(' '.join([str(i) for i in output]))

Submission status: Time Limit Exceeded

Solution code:
import copy

class Node(object):
    def __init__(self, num):
        self.num = num
        self.adjacency_list = []
        self.values = 0
        self.visited = False

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

node = [Node(num=i) for i in range(N)]

for i in range(N - 1): # 0 ~ N-2
#     exec("a"+str(ab[i][0])+".adjacency_list.append("+str(ab[i][1])+")")#a>b
#     exec("a"+str(ab[i][1])+".adjacency_list.append("+str(ab[i][0])+")")#b>a
    node[ab[i][1]-1].adjacency_list.append(ab[i][0]-1)
    node[ab[i][0]-1].adjacency_list.append(ab[i][1]-1)
    #append使った

for i in range(Q):
    node[px[i][0]-1].values +=px[i][1]

def dfs138(parent, n, val_p): #children is list
    global node
    node[n].values += val_p #parent kara keisyou
    val_n = node[n].values #val_n toshite syotoku
    adj = node[n].adjacency_list
    children = adj.copy()
    if parent in adj:
        children.remove(parent)
    for i in children:
        dfs138(n, i, val_n) #val_nを流す
#finish

dfs138([],0,0)

output = []
for n in range(N):
    val_n = node[n].values
    output.append(val_n)
print(' '.join([str(i) for i in output]))

Submission status: Time Limit Exceeded

Solution code:
import copy

class Node(object):
    def __init__(self, num):
        self.num = num
        self.adjacency_list = []
        self.values = 0
        self.visited = False

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


for i in range(1, N + 1):
    exec("a"+str(i)+" = Node("+str(i)+")")

for i in range(N - 1): # 0 ~ N-2
    exec("a"+str(ab[i][0])+".adjacency_list.append("+str(ab[i][1])+")")#a>b
    exec("a"+str(ab[i][1])+".adjacency_list.append("+str(ab[i][0])+")")#b>a
    #append使った

for i in range(Q):
    exec("a" + str(px[i][0]) + ".values +=" + str(px[i][1]) )

def dfs138(parent, n, val_p): #children is list
    exec("global a" + str(n))
    exec("a" + str(n) + ".values += " + str(val_p))#parent kara keisyou
    val_n = eval("a" + str(n) + ".values") #val_n toshite syotoku
    adj = eval("a" + str(n) + ".adjacency_list")
    children = adj.copy()
    if parent in adj:
        children.remove(parent)
    for i in children:
        dfs138(n, i, val_n) #val_nを流す
#finish

dfs138([],1,0)

output = []
for n in range(1, N + 1):
    val_n = eval("a" + str(n) + ".values")
    output.append(val_n)
print(' '.join([str(i) for i in output]))

Submission status: Time Limit Exceeded

Solution code:

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
# import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n,q=n1()
AB=n3(n-1)
PX=n3(q)

d={i:[] for i in range(1,n+1)}
for a,b in AB:
    d[a].append(b)
    d[b].append(a)

ans=[0]*(n+1)
for p,x in PX:
    ans[p]+=x

q=deque([1])
c=[False]*(n+1)
c[1]=True
while len(q)>0:
    i=q.popleft()
    for j in d[i]:
        if c[j]==False:
            ans[j]+=ans[i]
            c[j]=True
            q.append(j)

print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200001)

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

edge = [[] for i in range(N)]
ans = [0] * N
query = [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 q in range(Q):
    p, x = map(int, input().split())
    query[p-1] += x

is_visited = [False] * N

def dfs(cur, q):
    is_visited[cur] = True
    q = q + query[cur]
    ans[cur] += q

    for next in edge[cur]:
        if is_visited[next]:
            continue
        dfs(next, q)

dfs(0, 0)

print(*ans)

Submission status: Time Limit Exceeded

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

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

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

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

ans=[0 for _ in range(N)]
visited=[False]*N
def c(i,p):
    if visited[i]:
        return 
    visited[i]=True
    w=f[i]+p
    ans[i]=w
    ch=graph[i]
    for x in ch:
        c(x,w)

c(0,0)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque,defaultdict

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

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

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

visited=[False]*(N+1)
q=deque([])
q.append([1,0])
res=[0 for i in range(N+1)]
while q:
    i,c = q.pop()
    if visited[i]:
        continue
    visited[i]=True
    ch=g[i]
    w=c+f[i]
    res[i]=w
    for u in ch:
        q.appendleft([u,w])

print(*res[1:])

Submission status: Time Limit Exceeded

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

N,Q=map(int,input().split())
graph=[[] for _ in range(N)]
for _ 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 _ in range(Q):
    p,x=map(int,input().split())
    p-=1
    ans[p]+=x

used=[False]*N
def solve(x):
    used[x]=True
    for y in graph[x]:
        if used[y]:
            continue
        ans[y]+=ans[x]
        solve(y)

for i in range(N):
    solve(i)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

def main():
  input = sys.stdin.buffer.readline
  read = sys.stdin.buffer.read
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())
  ABPX = list(map(int, read().split()))
  AB = iter(ABPX[:N+N-2])
  PX = iter(ABPX[N+N-2:])

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = {}
  shown = set()

  for a, b in zip(AB, AB):
    a -= 1
    b -= 1
    # parents[b] = a
    # childrens[a].add(b)
    relations.setdefault(a, [])
    relations.setdefault(b, [])
    relations[a].append(b)
    relations[b].append(a)

  def f(parent, relations, parents, childrens):
    shown.add(parent)
    for c in relations[parent]:
      if c not in shown:
        parents[c] = parent
        childrens[parent].add(c)
        f(c, relations, parents, childrens)

  f(0, relations, parents, childrens)
  points = {}
  result = [0] * N

  for p, x in zip(PX, PX):
    p -= 1
    points.setdefault(p, 0)
    points[p] += x

  def solve(idx, parents, childrens, points, result):
    # print(idx)
    if idx in points:
      result[idx] += points[idx]
    if parents[idx] is not None:
      result[idx] += result[parents[idx]]
    for child in childrens[idx]:
      solve(child, parents, childrens, points, result)
      
  solve(0, parents, childrens, points, result)
  print(*result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 9)

def main():
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = {}
  shown = set()

  for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # parents[b] = a
    # childrens[a].add(b)
    relations.setdefault(a, [])
    relations.setdefault(b, [])
    relations[a].append(b)
    relations[b].append(a)

  def f(parent, relations, parents, childrens):
    shown.add(parent)
    for c in relations[parent]:
      if c not in shown:
        parents[c] = parent
        childrens[parent].add(c)
        f(c, relations, parents, childrens)

  f(0, relations, parents, childrens)
  points = {}
  result = [0] * N

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

  def solve(idx, parents, childrens, points, result):
    # print(idx)
    if idx in points:
      result[idx] += points[idx]
    if parents[idx] is not None:
      result[idx] += result[parents[idx]]
    for child in childrens[idx]:
      solve(child, parents, childrens, points, result)
      
  solve(0, parents, childrens, points, result)
  print(*result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import resource

input = sys.stdin.readline

sys.setrecursionlimit(10 ** 9)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def main():
  # Nがノードの数, Qが操作回数
  N, Q = map(int, input().split())

  parents = [None] * N
  childrens = [set() for _ in range(N)]
  relations = {}
  shown = set()

  for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    # parents[b] = a
    # childrens[a].add(b)
    relations.setdefault(a, [])
    relations.setdefault(b, [])
    relations[a].append(b)
    relations[b].append(a)

  def f(parent, relations, parents, childrens):
    shown.add(parent)
    for c in relations[parent]:
      if c not in shown:
        parents[c] = parent
        childrens[parent].add(c)
        f(c, relations, parents, childrens)

  f(0, relations, parents, childrens)
  points = {}
  result = [0] * N

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

  def solve(idx, parents, childrens, points, result):
    # print(idx)
    if idx in points:
      result[idx] += points[idx]
    if parents[idx] is not None:
      result[idx] += result[parents[idx]]
    for child in childrens[idx]:
      solve(child, parents, childrens, points, result)
      
  solve(0, parents, childrens, points, result)
  print(*result)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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)

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

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

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


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter, deque

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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)

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

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

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


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

# Nがノードの数, Qが操作回数
N, Q = map(int, input().split())

parents = [None] * N
childrens = [set() for _ in range(N)]
relations = [set() for _ in range(N)]
shown = set()

for _ in range(N - 1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  # parents[b] = a
  # childrens[a].add(b)
  relations[a].add(b)
  relations[b].add(a)

def f(parent):
  global relations, parents, childrens
  shown.add(parent)
  for c in relations[parent]:
    if c not in shown:
      parents[c] = parent
      childrens[parent].add(c)
      f(c)

f(0)
points = {}
result = [0] * N

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

def solve(idx):
  global parents, childrens, points, result
  # print(idx)
  if idx in points:
    result[idx] += points[idx]
  if parents[idx] is not None:
    result[idx] += result[parents[idx]]
  for child in childrens[idx]:
    solve(child)
    

solve(0)
print(*result)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global ans
    ans[p] = ans[pre] + sums[p]
    for ki in L[p]:
        if pre==ki:
            continue    
        dfs(ki,p)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global L,ans,sums
    ans[p] = ans[pre] + sums[p]

    for ki in L[p]:
        if pre==ki:
            continue    
        dfs(ki,p)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global L,ans,sums
    ans[p] = ans[pre] + sums[p]
    for i in range(len(L[p])):
        if pre==L[p][i]:
            continue    
        dfs(L[p][i],p)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()[:-1]

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global L,ans,sums
    ans[p] = ans[pre] + sums[p]
    for i in range(len(L[p])):
        if pre!=L[p][i]:
            dfs(L[p][i],p)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

L = []
sums = []
ans = []

def main():
    global L,ans,sums
    N,Q= map(int, input().split())
    ans = [0]*(N+1)
    sums = [0]*(N+1)
    L=[]
    [L.append([])for _ in range(N+1)]
    for _ in range(N-1):
        A,B = map(int, input().split())
        L[A].append(B)
        L[B].append(A)
    for _ in range(Q):
        p,x = map(int, input().split())
        sums[p]+=x
    dfs(1,0)

    print(*ans[1:N+1])


def dfs(p,pre):
    global L,ans,sums
    ans[p] = ans[pre] + sums[p]
    for i in range(len(L[p])):
        if pre!=L[p][i]:
            dfs(L[p][i],p)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

N,Q = map(int,input().split())
dist = {i:[] for i in range(1,N+1)}
oya = [-1 for i in range(N+1)]
oya[1] = 0

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

kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      oya[t] = a

ans = [0 for i in range(N+1)]
for q in range(Q):
  a,b = map(int,input().split())
  ans[a] += b
  
kouho = deque([1])
sumi = [0 for i in range(N+1)]

while len(kouho) > 0:
  a = kouho.popleft()
  sumi[a] += 1
  for t in dist[a]:
    if sumi[t] != 0:
      continue
    else:
      kouho.append(t)
      p = oya[t]
      ans[t] += ans[p]
      
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int, input().split())
G=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
X=[0]*N
for i in range(Q):
    p,x=map(int, input().split())
    X[p-1]+=x
que=[(0,-1)]
while que:
    now, pre=que.pop(0)
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

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

Submission status: Time Limit Exceeded

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

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

que=[(0,-1)]

while len(que)>0:
    now, pre=que.pop(0)
    for nex in G[now]:
        if nex==pre:
            continue
        else:
            X[nex]+=X[now]
            que.append((nex,now))

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

Submission status: Time Limit Exceeded

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

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

que=[0]
done=[-1]*N
while len(que)>0:
    now=que.pop(0)
    done[now]=1
    for nex in G[now]:
        if done[nex]==1:
            continue
        else:
            X[nex]+=X[now]
            que.append(nex)

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

Submission status: Time Limit Exceeded

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

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

que=[0]
done=[-1]*N
while len(que)>0:
    t=que.pop(0)
    now=t
    done[now]=1
    for nex in G[now]:
        if done[nex]!=-1:
            continue
        else:
            X[nex]+=X[now]
            que.append(nex)

print(*X)

Submission status: Time Limit Exceeded

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

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

que=[(0,X[0])]
done=[-1]*N
while len(que)>0:
    t=que.pop(0)
    now, count=t
    X[now]=count
    done[now]=1
    for nex in G[now]:
        if done[nex]!=-1:
            continue
        else:
            que.append((nex, count+X[nex]))

print(*X)

Submission status: Time Limit Exceeded

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

N,Q = map(int,input().split())
node = [[]for i in range(0,N+1,1)]
for i in range(0,N-1,1):
    a,b = map(int,input().split())
    node[a].append(b)
    node[b].append(a)
node_score = [0]*(N+1)#スコア
for i in range(0,Q,1):
    p,x = map(int,input().split())
    node_score[p] += x

ans = [0]*(N+1)
def bfs(n,preN):
    ans[n] = ans[preN]+node_score[n]
    for to in node[n]:
        if to != preN:
            bfs(to,n)
bfs(1,0)
print(" ".join(list(map(str,ans[1:N+1]))))

Submission status: Time Limit Exceeded

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

N,Q = map(int,input().split())
node = [[]for i in range(0,N+1,1)]
for i in range(0,N-1,1):
    a,b = map(int,input().split())
    node[a].append(b)
    node[b].append(a)
node_score = [0]*(N+1)#スコア
for i in range(0,Q,1):
    p,x = map(int,input().split())
    node_score[p] += x

ans = [0]*(N+1)
def bfs(n,preN):
    ans[n] = ans[preN]+node_score[n]
    for to in node[n]:
        if to != preN:
            bfs(to,n)
bfs(1,0)
print(" ".join(list(map(str,ans[1:N+1]))))

Submission status: Time Limit Exceeded

Solution code:
#input()を速い方にしないとTLEになる

import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
input = sys.stdin.readline

def dfs(v,p): #点vについての処理。p：vの親
    if (p != -1): res[v] += res[p]
    
    for e in edges[v]:
        if (e == p): continue
        dfs(e,v)
#--------------------------------
N, Q = map(int, input().split())
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

res = [0]*(N+1) #点数リスト
for i in range(Q): #点数リストに初期値を格納
    p,x = map(int, input().split())
    res[p] += x

dfs(1,-1)
print(*res[1:])

Submission status: Time Limit Exceeded

Solution code:
#input()を速い方にしないとTLEになる

import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限
input = sys.stdin.readline

def dfs(v,p): #点vについての処理。p：vの親
    if (p != -1): res[v] += res[p]
    
    for e in edges[v]:
        if (e == p): continue
        dfs(e,v)
#--------------------------------
N, Q = map(int, input().split())
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

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

res = [0]*(N+1) #点数リスト
for i in range(Q): #点数リストに初期値を格納
    p,x = px[i]
    res[p] += x

dfs(1,-1)
print(*res[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の呼び出し制限

def dfs(v,p): #点vについての処理。p：vの親
    if (p != -1): res[v] += res[p]
    
    for e in edges[v]:
        if (e == p): continue
        dfs(e,v)
#--------------------------------
N, Q = map(int, input().split())
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)
#print(edges)
px = [list(map(int, input().split())) for _ in range(Q)]

res = [0]*(N+1) #点数リスト
for i in range(Q): #点数リストに初期値を格納
    p,x = px[i]
    res[p] += x

dfs(1,-1)
print(*res[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
# input = sys.stdin.readline

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

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2*10**5)

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for _ 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 _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(now, parent, add):
    if parent != -1:
        ans[now] += add
    for i in graph[now]:
        if i != parent:
            dfs(i, now, ans[now])

dfs(0, -1, 0)
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2*10**5)

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

def dfs(now, parent):
    if parent != 0:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i != parent:
            dfs(i, now)

dfs(1, 0)
print(' '.join(map(str, ans[1:])))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2*10**5)

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for _ 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 _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i != parent:
            dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2*10**5)

n, q = map(int, input().split())
graph = {i: set() for i in range(n+1)}
for _ in range(n-1):
    a, b = map(int, input().split())
    graph[a].add(b)
    graph[b].add(a)
ans = [0] * (n+1)
for _ in range(q):
    p, x = map(int, input().split())
    ans[p] += x

def dfs(now, parent):
    if parent != 0:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i != parent:
            dfs(i, now)

dfs(1, 0)
print(' '.join(map(str, ans[1:])))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2*10**5)

n, q = map(int, input().split())
graph = {i: set() for i in range(n)}
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].add(b)
    graph[b].add(a)
ans = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i != parent:
            dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
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, point):
    # 現在いる頂点vの親までの値をpointとする
    value[v] += point
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x, v, value[v])


dfs(1, 0, 0)

res = ' '.join(map(str, value[1:]))
print(res)