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

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

res = [0] * (n+1)
neighbor = [[] for _ in range(n+1)]
for edge in ab_lst:
    neighbor[edge[0]].append(edge[1])

root_value = [0] * (n+1)
for px in px_lst:
    root_value[px[0]] += px[1]
    
def dfs(root, value):
    res[root] += value
    if neighbor[root] != []:
        for i in neighbor[root]:
            dfs(i, value + root_value[i])

dfs(1, root_value[1])
            
for i in res[1:]:
    print(i, end=" ")

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
node=[0 for i in range(n)]
tree=[]
for i in range(n-1):
    tree.append(list(map(int,input().split())))
def counter(p,x,cnt):
    for i in range(n-1):
        if tree[i][0]==p:
            if cnt[tree[i][1]-1]!=1:
                node[tree[i][1]-1]+=x
                cnt[tree[i][1]-1]=1
                counter(tree[i][1],x,cnt)
            else:
                continue
        
        
for j in range(q):
    cnt=[0 for i in range(n)]
    p,x=map(int,input().split())
    cnt[p-1]=1
    node[p-1]+=x
    counter(p,x,cnt)

for i in range(n):
    node[i]=str(node[i])
print(' '.join(node))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab=sorted(ab, key=lambda x:x[0])
pq=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for p,q in pq:
	res[p-1]+=q
for a,b in ab:
	res[b-1]+=res[a-1]
ans=[str(t) for t in res]
print(" ".join(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200010)

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

G = [[] for k in range(N+1)]

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

kyori = [0 for k in range(N+1)]

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

def dfs(now, dist):
    for tsugi in G[now]:
        if kyori[tsugi] <= 0:
            kyori[tsugi] = -kyori[tsugi]
            kyori[tsugi] += dist
            dfs(tsugi, kyori[tsugi])
kyori[1] = -kyori[1]
dfs(1,kyori[1])

print(*kyori[1:], sep = " ")

Submission status: Time Limit Exceeded

Solution code:
import sys

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


def dfs(cur, pls):
    pls += to_add[cur]
    ans[cur] = pls
    for u in e[cur]:
        if visited[u]:
            continue
        visited[u] = True
        dfs(u, pls)


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

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

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

ans = [0] * n
visited = [False] * n
visited[0] = True

dfs(0, 0)

print(*ans)

Submission status: Time Limit Exceeded

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

n, q = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

cost = [0] * n

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

ans = [-1] * n
ans.append(0)

def dfs(frm, n):
    ans[n] = ans[frm] + cost[n]
    for to in edge[n]:
        if ans[to] != -1:
            continue
        dfs(n, to)

dfs(-1, 0)
print(" ".join([str(item) for item in ans[:-1]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N,Q = map(int,input().split())
T = [[] for i in range(N+1)]
V = [0]*(N+1)
for _ in range(N-1):
    a,b = map(int,input().split())
    T[a].append(b)
    T[b].append(a)
for _ in range(Q):
    p,x = map(int,input().split())
    V[p]+=x
def f(v,p):
    global T,V
    for c in T[v]:
        if c==p:continue
        V[c]+=V[v]
        f(c,v)
f(1,0)
print(*V[1:])

Submission status: Time Limit Exceeded

Solution code:
n,q=[int(i) for i in input().split()]
g={}
val=[0]*n
for i in range(n-1):
  a,b=[int(i) for i in input().split()]
  if a-1 in g:g[a-1].append(b-1)
  else:g[a-1]=[b-1,]
for i in range(q):
  a,b=[int(i) for i in input().split()]
  val[a-1]+=b
stack=[]
stack.append(0)
while(len(stack)>0):
  p=stack.pop()
  if p in g:
    for i in g[p]:
      val[i]=val[i]+val[p]
      stack.append(i)
for i in val:print(i,end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]
PX = [list(map(int,input().split())) for _ in [0]*Q]

E = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)

P = [-1]*N
P[0] = 0
q = [0]
while q:
    i = q.pop()
    for j in E[i]:
        if P[j]!=-1: continue
        P[j] = i
        q.append(j)
P[0] = -1

V = [0]*N
for p,x in PX:
    p-=1
    V[p] += x

q = [0]
while q:
    i = q.pop()
    for j in E[i]:
        if j==P[i] : continue
        V[j] += V[i]
        q.append(j)

print(*V)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

class Node():
    def __init__(self, val):
        self.val = val
        self.counter = 0
        self.child = []

if __name__ == '__main__':

    def inorder(node, val):
        if node is None:
            return
        node.counter += val
        for child in node.child:
            inorder(child,val)

    n,q = [int(i) for i in input().split()]
    a = [[int(i) for i in input().split()] for _ in range(n-1)]
    p = [[int(i) for i in input().split()] for _ in range(q)]
    nodes = {}
    for i in range(1,n+1):
        temp = Node(i)
        nodes[i] = temp
    for A,B in a:
        nodes[A].child.append(nodes[B])
    for P,X in p:
        inorder(nodes[P],X)
    ans = ""
    for i in range(1,n+1):
        ans += str(nodes[i].counter) + " "
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
tree = []
for _ in range(n + 1):
    tree.append(set())
for _ in range(n - 1):
    a, b = map(int, input().split())
    tree[a].add(b)
    tree[b].add(a)
used = [0] * (n + 1)
used[1] = 1
par = [0] * (n + 1)
S = [1]
while S:
    v = S.pop()
    for u in tree[v]:
        if used[u] == 0:
            used[u] = 1
            S.append(u)
            par[u] = v
hans = [0] * (n + 1)
for _ in range(q):
    p, x = map(int, input().split())
    hans[p] += x
ans = []
for v in range(1, n + 1):
    c = 0
    while v != 1:
        c += hans[v]
        v = par[v]
    ans.append(c + hans[1])
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(300000)
input = sys.stdin.readline

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

alls = [[] for _ in range(N + 1)]


def chase(node):
    ret = [node]
    for c in children[node]:
        ret.extend(chase(c))
    alls[node] = ret
    return ret


chase(1)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


N, Q = list(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)]


class Tree():
    def __init__(self, v):
        self.parent = None
        self.v = v
        self.x = 0
        self.memo = None

    def add(self, x):
        self.x += x

    def calc(self):
        if self.v == 1:
            return self.x
        if self.memo is not None:
            return self.memo

        tmp = self.parent.calc()
        self.memo = tmp + self.x
        return self.memo



trees = {i: Tree(i) for i in range(1, N + 1)}

for a,b in ab:
    trees[b].parent = trees[a]

for p,x in px:
    trees[p].add(x)

ans = []
for i in range(1,N+1):
    ans.append(trees[i].calc())

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

Submission status: Time Limit Exceeded

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

def main():
    def dfs(i,oi=-1,s=0):
        ans[i]=s+d[i]
        for ki in to[i]:
            if ki==oi:continue
            dfs(ki,i,s+d[i])

    n,q=map(int, input().split())
    to=defaultdict(list)
    d=[0]*n
    ans=[0]*n
    for _ in range(n-1):
        a,b=map(int, input().split())
        a-=1
        b-=1
        to[a].append(b)
        to[b].append(a)
    for _ in range(q):
        p, x = map(int, input().split())
        d[p-1]+=x
    dfs(0)
    print(*ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque
dd = defaultdict(list)
pq = defaultdict(int)

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

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

for _ in range(Q):
    p,q = map(int, input().split())
    pq[p] += q
    
answer = [0]*N
queue = deque()
visited = {}
visited[1] = 1
queue.append(1)

while queue != deque():
    tmp = queue.popleft()
    answer[tmp-1] += pq[tmp]
    for i in dd[tmp]:
        if not i in visited:
            visited[i] = 1
            queue.append(i)
            answer[i-1] += answer[tmp-1]
            
print(*answer)

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(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)]

class Tree:
  C = {}
  N, D = None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def exe(s):
    L = [-1] * N
    A = [0] * N
    for p, x in px:
      p -= 1
      A[p] += x
    S = [0]
    while S != []:
      t = S.pop()
      L[t] = 1
      for i in s.C[t]:
        if L[i] == -1:
          A[i] += A[t]
          S.append(i)
    for i in range(N):
      print(A[i], end = " ")

  

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.setC(a, b)

T.exe()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

L = [[] for i in range(N)]
for i in range(N-1) :
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    L[u].append(v)
    L[v].append(u)

par = [-1]*N

cnt = [0]*N

q = deque([0])
while len(q) :
    u = q.popleft()
    for v in L[u] :
        if v == par[u] :
            continue
        par[v] = u
        q.append(v)

for i in range(Q) :
    p,x = map(int,input().split())
    p -= 1
    q = deque([p])
    while len(q) :
        u = q.popleft()
        cnt[u] += x
        for v in L[u] :
            if v != par[u] :
                q.append(v)

print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)


## input
N,Q = map(int, input().split())
cnt = [0 for _ in range(N)]
route = defaultdict(lambda:set([]))
for _ in range(N-1):
  a,b = map(int, input().split())
  route[a-1].add(b-1)
  route[b-1].add(a-1)
for _ in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x

## solve
def dfs(p,q):
  for r in route[q]:
    if p != r:
      cnt[r] += cnt[q]
      dfs(q,r)

dfs(-1,0)
print(" ".join([str(c) for c in cnt]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
N,Q = map(int,input().split())
e = [ [ ] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    e[a-1].append(b-1)

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

ansl = [0 for i in range(N)]

def dfs(x,c):
    c += d[x]
    ansl[x] = c
    for v in e[x]:
        dfs(v,c)

dfs(0,0)
print(" ".join(map(str,ansl)))

Submission status: Time Limit Exceeded

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

n, q = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(list)
ans = [0 for i in range(n+1)]
for i in range(n-1):
  a, b = list(map(int, input().split()))
  d[a].append(b)
dd = defaultdict(int)
for i in range(q):
  p, x = list(map(int, input().split()))
  dd[p] += x

def dfs(x, cnt):
  ans[x] += cnt
  for next_ in d[x]:
    dfs(next_, cnt+dd[next_])

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

Submission status: Time Limit Exceeded

Solution code:
'''
date +%Y.%m.%d

题解先咕着。
'''
import sys

def intinput():
    return [int(i) for i in input().split()]

n, q = intinput()
G = [[] for i in range(n + 1)]
a = [0 for i in range(n + 1)]
sys.setrecursionlimit(n + 100)

def dfs(u, fa):
    for v in G[u]:
        if v != fa:
            a[v] += a[u]
            dfs(v, u)

for i in range(n - 1):
    u, v = intinput()
    G[u].append(v)
    G[v].append(u)

for i in range(q):
    u, x = intinput()
    a[u] += x

dfs(1, 0)

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

Submission status: Time Limit Exceeded

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

n, q = [int(item) for item in input().split()]
edge = [[] for _ in range(n)]
for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

cost = [0] * n

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

ans = [-1] * n
ans.append(0)

def dfs(frm, n):
    ans[n] = ans[frm] + cost[n]
    for to in edge[n]:
        if ans[to] != -1:
            continue
        dfs(n, to)

dfs(-1, 0)
print(" ".join([str(item) for item in ans[:-1]]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)


def dfs(s, prev):
    global g, cost
    for t in g[s]:
        if t == prev:
            continue
        cost[t] += cost[s]
        dfs(t, s)


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


dfs(0, -1)
print(*cost, sep=' ')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, Q = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

D = [0] * N
C = [0] * N

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


def dfs(u, p, k):
    D[u] += k

    for w in G[u]:
        if w == p:
            continue
        k += C[w]
        dfs(w, u, k)
        k -= C[w]


dfs(0, -1, C[0])
print(*D)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)
p, x = (
    zip(*(map(int, input().split()) for _ in range(Q))) if Q else
    ((), ())
)


G = [[] for _ in range(N + 1)]
for X, Y in zip(a, b):
    G[X].append(Y)
    G[Y].append(X)


def tree(G, r):
    p = [i for i in range(len(G))]
    c = [[]for _ in range(len(G))]
    q = []
    q.append(r)
    while q:
        i = q.pop()
        for j in G[i]:
            if j != p[i]:
                p[j] = i
                c[i].append(j)
                q.append(j)
    return p, c


par, c = tree(G, 1)
counts = [0 for _ in range(N + 1)]
for P, X in zip(p, x):
    counts[P] += X
dp = [0 for _ in range(N + 1)]
q = []
q.append(1)
while q:
    i = q.pop()
    dp[i] = counts[i]
    for j in c[i]:
        q.append(j)
        counts[j] += dp[i]
ans = ' '.join(
    str(dp[i])
    for i in range(1, N + 1)
)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(n-1)]
pq=[list(map(int,input().split())) for _ in range(m)]
ab=sorted(ab, key=lambda x:x[0])
pq=sorted(pq, key=lambda x:x[0])

res=[0 for _ in range(n)]
for p,q in pq:
	res[p-1]+=q
for a,b in ab:
	res[b-1]+=res[a-1]
res=[str(t) for t in res]
print(" ".join(res))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200005)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ps = [0] * n
for i in range(q):
    p, x = na()
    p -= 1
    ps[p] += x

ans = [0] * n

def dfs(cur, pre, g, curv):
    global ps, ans
    curv += ps[cur]
    ans[cur] = curv
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, curv)

dfs(0, -1, g, 0)

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

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(500000)
N, Q = map(int, input().split())
E = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
C = [0] * (N+1)
for _ in range(Q):
    p, x = map(int, input().split())
    C[p] += x

Ans = [0] * (N+1)
def dfs(v, p, a):
    global ans
    a += C[v]
    Ans[v] = a
    for u in E[v]:
        if u!=p:
            dfs(u, v, a)
dfs(1, 0, 0)
print(" ".join(map(str, Ans[1:])))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N,Q=map(int,input().split())
L=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    L[a].append(b)
    L[b].append(a)
CL=[0]*N
for _ in range(Q):
    p,x=map(int,input().split())
    CL[p-1]+=x

AL=[0]*N
ed=[0]*N
def dfs(val, now):
    ed[now]=1
    val+=CL[now]
    AL[now]=val
    for p in L[now]:
        if ed[p]==0:
            dfs(val,p)
dfs(0,0)
print(" ".join(map(str,AL)))

Submission status: Time Limit Exceeded

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

ab = []
for i in range(N-1):
    a, b = map(int, input().split())
    ab.append((a, b))
ab = sorted(ab, key=lambda x: (x[0], x[1]))

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

for i in range(N-1):
    a, b = ab[i]
    P[b-1] += P[a-1]

print(*P)

Submission status: Time Limit Exceeded

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

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

def dfs1(x, p):
	for v in adj[x]:
		if v != p:
			par[v] = x
			dfs1(v, x)
	return

dfs1(0, -1)

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

ans = [0 for _ in range(n)]

def dfs2(x, c):
	ans[x] = c + queries[x]
	for v in adj[x]:
		if v != par[x]:
			dfs2(v, ans[x])
	return

dfs2(0, 0)

print(*ans)

Submission status: Time Limit Exceeded

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

def solve():
    N, Q = map(int, input().split())
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        A, B = map(int, input().split())
        A, B = A-1, B-1
        adjL[A].append(B)
        adjL[B].append(A)

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

    useds = [False] * N
    def dfs(vNow, x):
        useds[vNow] = True
        anss[vNow] += x
        for v2 in adjL[vNow]:
            if not useds[v2]:
                dfs(v2, anss[vNow])

    dfs(0, 0)

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

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())

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

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

def dfs(v, p):
    for u in edge[v]:
        if u != p:
            imos[u] += imos[v]
            dfs(u, v)

dfs(0, -1)
print(' '.join([str(x) for x in imos]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
from itertools import *

N, Q = map(int, input().split())
es = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    es[a].append(b)
cnt = [0] * (N+1)
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p] += x
def EulerTour(v, p, c):
    for u in es[v]:
        if u != p:
            EulerTour(u, v, c+cnt[v])
    cnt[v] += c
EulerTour(1, 0, 0)
print(*cnt[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,Q = inpl()

lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1,b-1
    lines[a].add(b)
    lines[b].add(a)

adds = [0]*N
for _ in range(Q):
    p,x = inpl()
    adds[p-1] += x

visited = [False]*N
ans = [0]*N

def dfs(x,cnt):
    global visited
    global ans

    visited[x] = True
    cnt += adds[x]
    ans[x] = cnt
    for t in lines[x]:
        if not visited[t]:
            dfs(t,cnt)


dfs(0,0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)
par = [-1 for _ in range(n)]

def dfs1(x, p):
	for v in adj[x]:
		if v != p:
			par[v] = x
			dfs1(v, x)
	return

dfs1(0, -1)

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

ans = [0 for _ in range(n)]

def dfs2(x, c):
	ans[x] = c + queries[x]
	for v in adj[x]:
		if v != par[x]:
			dfs2(v, ans[x])
	return

dfs2(0, 0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
a, b = (
    zip(*(map(int, input().split()) for _ in range(N - 1))) if N - 1 else
    ((), ())
)
p, x = (
    zip(*(map(int, input().split()) for _ in range(Q))) if Q else
    ((), ())
)


G = [set() for _ in range(N + 1)]
for X, Y in zip(a, b):
    G[X].add(Y)
    G[Y].add(X)


def tree(G, r):
    p = [i for i in range(len(G))]
    c = [set() for _ in range(len(G))]
    q = []
    c[r] = G[r]
    q.append(r)
    while q:
        i = q.pop()
        for j in G[i]:
            if j != p[i]:
                p[j] = i
                c[j] = G[j] - {i}
                q.append(j)
    return p, c


par, c = tree(G, 1)
counts = [0 for _ in range(N + 1)]
for P, X in zip(p, x):
    counts[P] += X
dp = [0 for _ in range(N + 1)]
q = []
q.append(1)
while q:
    i = q.pop()
    dp[i] = counts[i]
    for j in c[i]:
        q.append(j)
        counts[j] += dp[i]
ans = ' '.join(
    str(dp[i])
    for i in range(1, N + 1)
)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200005)

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, q = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    a, b = na()
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

ps = [0] * n
for i in range(q):
    p, x = na()
    p -= 1
    ps[p] += x

ans = [0] * n

def dfs(cur, pre, g, curv):
    global ps, ans
    curv += ps[cur]
    ans[cur] = curv
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, curv)

dfs(0, -1, g, 0)

for x in ans:
    sys.stdout.write(str(x) + " ")

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].append(B)
    adjL[B].append(A)

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

useds = [False] * N
def dfs(vNow, x):
    useds[vNow] = True
    anss[vNow] += x
    for v2 in adjL[vNow]:
        if not useds[v2]:
            dfs(v2, anss[vNow])

dfs(0, 0)

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

Submission status: Time Limit Exceeded

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

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

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

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

dfs(0, -1)
print(' '.join([str(x) for x in imos]))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,Q = inpl()

lines = defaultdict(set)
for _ in range(N-1):
    a,b = inpl()
    a,b = a-1,b-1
    lines[a].add(b)
    lines[b].add(a)

adds = [0]*N
for _ in range(Q):
    p,x = inpl()
    adds[p-1] += x

visited = [False]*N
ans = [0]*N

def dfs(x,cnt):
    global visited
    global ans

    if visited[x]:
        return
    else:
        visited[x] = True
        cnt += adds[x]
        ans[x] = cnt
        for t in lines[x]:
            dfs(t,cnt)


dfs(0,0)

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

Submission status: Time Limit Exceeded

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

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

class RangeAddQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        # 初期値
        self.data = [0]*(2*self.n0-1)

    def update(self, l,r,v):
        l += self.n0
        r += self.n0
        while l < r:
            if r&1:
                r -= 1
                self.data[r-1] += v
            if l&1:
                self.data[l-1] += v
                l += 1
            l >>=1
            r >>=1

    def query(self, i):
        i += self.n0-1
        res = 0
        while i+1:
            if self.data[i]:
                res += self.data[i]
            # (i-1)//2
            i = ~-i//2
        return res

label = [-1]*n
cnt = [0]
def dfs(i):
    if label[i] != -1:
        return
    label[i] = cnt[0]
    cnt[0] += 1
    for to in G[i]:
        dfs(to)

dfs(0)

nG = [[] for i in range(n)]
for i in range(n):
    for j in G[i]:
        nG[label[i]].append(label[j])

pos = [0]*n
cnt = [0]
vis = [False]*n
def dfs2(v):
    if vis[v]:
        return
    vis[v] = True
    order = cnt[0]
    cnt[0] += 1
    for to in nG[v]:
        dfs2(to)
    pos[order] = cnt[0]

dfs2(0)

RAQ = RangeAddQuery(n)

ans = []
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    v = label[p]
    RAQ.update(v, pos[v], x)

ans = [0]*n
for i in range(n):
    v = label[i]
    b = RAQ.query(v)
    ans[i] = b

print(*ans)