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 = [[int(i) for i in input().split()] for _ in range(N-1)]
PX = [[int(j) for j 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)
    
counters = [0] * (N+1)
for p,x in PX:
    counters[p] += x
    
def dfs(v,parent,add):
    counters[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,counters[v])

dfs(1,0,0)

ans = ' '.join(map(str,counters[1:]))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, Q=map(int, input().split())
import sys
sys.setrecursionlimit(10**6)
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)

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

ans=[0]*N
def dfs(start, pre, preval):
  addval=preval+add[start]
  ans[start]+=addval
  for next_node in tree[start]:
    if next_node==pre:
      continue
    dfs(next_node, start,addval)
dfs(0,-1,0)  
for a in ans:
  print(a, end=" ")

Submission status: Time Limit Exceeded

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

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

    edge = [[] for _ in range(N)]
    for i in ab:
        edge[i[0]-1].append(i[1]-1)
        edge[i[1]-1].append(i[0]-1)
    cnt = [0]*N
    for i in px:
        cnt[i[0]-1] += i[1]

    stk = []
    visited = set()
    stk.append(0)

    def dfs(v, par):
        if v>0:
            cnt[v] += cnt[par]
        for i in edge[v]:
            if i!=par:
                dfs(i, v)

    dfs(0, -1)

    # while len(stk):
    #     print(stk, visited)
    #     v = stk.pop()
    #     if not v in visited:
    #         visited.add(v)
    #     if v>0:
    #         cnt[v] += cnt[par]
    #     for i in edge[v]:
    #         if not i in visited:
    #             stk.append(i)
    #     par = v

    print(*cnt)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

    edge = [[False]*N for _ in range(N)]
    for i in ab:
        edge[i[0]-1][i[1]-1] = True
        edge[i[1]-1][i[0]-1] = True
    cnt = [0]*N
    for i in px:
        cnt[i[0]-1] += i[1]

    stk = []
    visited = set()
    stk.append(0)
    par = -1
    while len(stk):
        v = stk.pop()
        if not v in visited:
            visited.add(v)
            if v>0:
                cnt[v] += cnt[par]
        for j in range(N):
            if edge[v][j] and j!=par and not j in visited:
                stk.append(j)
        par = v

    print(*cnt)

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n,q = [int(i) for i in input().split()]
 
def find(x):
    if par[x][0] < 0:
        return x
    else:
        px = find(par[x][0])
        par[x][0] = px
        return px

def unite(x,y):      
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x][0] > par[y][0]:
            x,y = y,x
        par[x][0] += par[y][0]
        par[y][0] = x
        return True

memo = [True]*n
par = [[-1,0,i] for i in range(n)]
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1)
  if memo[a-1] and memo[b-1]:
      par[b-1][1] += 1
  elif memo[b-1] and not memo[a-1]:
    par[b-1][1] += 1+par[a-1][1]
  elif memo[a-1] and not memo[b-1]:
    par[a-1][1] += 1+par[b-1][1]
  memo[a-1] = False
  memo[b-1] = False
  
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

from operator import itemgetter
par = sorted(par,key=itemgetter(1))
par = sorted(par,key=itemgetter(0))
#print(par)
cnt = 0
for i in range(1,n):
  if par[i][0] >= 0 and par[i][1]==1:
    chk[par[i][2]] += chk[par[i][0]]
    cnt = 0
  if par[i][0] >= 0 and par[i][1]>=2:
    if par[i][0] == par[i-1][0] and par[i][1] > par[i-1][1]:
      chk[par[i][2]] += chk[par[i-1][2]]
      cnt = 0
    if par[i][0] == par[i-1][0] and par[i][1] == par[i-1][1]:
      cnt += 1
      chk[par[i][2]] += chk[par[i-1-cnt][2]]
      
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Time Limit Exceeded

Solution code:
n,q = [int(i) for i in input().split()]

def find(x):
    if par[x][0] < 0:
        return x
    else:
        px = find(par[x][0])
        par[x][0] = px
        return px

def unite(x,y):      
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x][0] > par[y][0]:
            x,y = y,x
        par[x][0] += par[y][0]
        par[y][0] = x
        return True

memo = [True]*n
par = [[-1,0,i] for i in range(n)]
for i in range(n-1):
  a,b = [int(i) for i in input().split()]
  unite(a-1,b-1)
  if memo[a-1] and memo[b-1]:
      par[b-1][1] += 1
  elif memo[b-1] and not memo[a-1]:
    par[b-1][1] += 1+par[a-1][1]
  elif memo[a-1] and not memo[b-1]:
    par[a-1][1] += 1+par[b-1][1]
  memo[a-1] = False
  memo[b-1] = False
  
chk = [0]*n
for i in range(q):
  p,x = [int(i) for i in input().split()]
  chk[p-1] += x

from operator import itemgetter
par = sorted(par,key=itemgetter(1))
par = sorted(par,key=itemgetter(0))
#print(par)
cnt = 0
for i in range(1,n):
  if par[i][0] >= 0 and par[i][1]==1:
    chk[par[i][2]] += chk[par[i][0]]
    cnt = 0
  if par[i][0] >= 0 and par[i][1]>=2:
    if par[i][0] == par[i-1][0] and par[i][1] > par[i-1][1]:
      chk[par[i][2]] += chk[par[i-1][2]]
      cnt = 0
    if par[i][0] == par[i-1][0] and par[i][1] == par[i-1][1]:
      cnt += 1
      chk[par[i][2]] += chk[par[i-1-cnt][2]]
      
chk = list(map(str,chk))
print(' '.join(chk))

Submission status: Time Limit Exceeded

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

def dfs(now, prev=-1):
    for nx in g[now]:
        if nx==prev:
            continue
        p[nx] += p[now]
        dfs(nx, now)
dfs(0)
print(*p)

Submission status: Time Limit Exceeded

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

for _ in range(n-1):
    a,b = map(int,input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
    
for _ in range(q):
    a,b = map(int,input().split())
    a -= 1
    point[a] += b
    
def dfs(now, prev = -1):
    for next in tree[now]:
        if next == prev:
            continue
        point[next] += point[now]
        
        dfs(next, now)
        
dfs(0)
print(*point)

Submission status: Time Limit Exceeded

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

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

cnt = [0 for i in range(N+1)]
seen = [0 for i in range(N+1)]

def dfs(G,p):
  for v in G[p]:
    if seen[v] == 0:
      seen[v] = 1
      cnt[v] = cnt[p] + lo[v]
      dfs(G,v)
    else:
      continue

###探索
cnt[1] = lo[1]
seen[1] = 1
dfs(G,1)
###
print(*cnt[1:])

Submission status: Time Limit Exceeded

Solution code:
I=lambda:map(int,input().split());
n,q=I();
r=[0]*n;
e=[[]for _ in range(n)];
exec("a,b=I();e[a-1]+=b-1,;e[b-1]+=a-1,;"*(n-1));
exec("q,x=I();r[q-1]+=x;"*q);
y=[0]+[1]*n;
s=[0]
while s:
  p=s.pop();
  for c in e[p]:
    exec("y[c]=0;r[c]+=r[p];s+=c,;"*y[c])
print(*r)

Submission status: Time Limit Exceeded

Solution code:
I=lambda:map(int,input().split());n,q=I();r=[0]*n;e=[[]for _ in range(n)];exec("a,b=I();e[a-1]+=b-1,;e[b-1]+=a-1,;"*(n-1));exec("q,x=I();r[q-1]+=x;"*q);y=[0]+[1]*n;s=[0]
while s:
 p=s.pop();[exec("y[c]=0;r[c]+=r[p];s+=c,;"*y[c]) for c in e[p]]
print(*r)

Submission status: Time Limit Exceeded

Solution code:
I=lambda:map(int,input().split());n,q=I();r=[0]*n;e=[[]for _ in range(n)];exec("a,b=I();e[a-1]+=b-1,;e[b-1]+=a-1,;"*(n-1));exec("q,x=I();r[q-1]+=x;"*q);y=[0]+[1]*n;s=[0]
while s:
 p=s.pop();[exec("y[c]=0;r[c]+=r[p];s+=c,;"*y[c]) for c in e[p]]
print(*r)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**9)


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

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

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

    def dfs(v: int):
        nonlocal visited
        nonlocal cnt
        if all(visited):
            print(*cnt)
            sys.exit()
        for n in edges[v]:
            if visited[n]:
                continue
            visited[n] = True
            cnt[n] += cnt[v]
            dfs(n)
        return

    dfs(0)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def resolve():
    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):
        for i in graph[v]:
            if i == parent:
                continue
            value[i] += value[v]
            dfs(i, v)

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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

def resolve():
    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):
        for i in graph[v]:
            if i == parent:
                continue
            value[i] += value[v]
            dfs(i, v)

    dfs(1, 0)
    return print(*value[1:])

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,q = map(int,input().split())
ki = [[]for _ in range(n)]
def dfs(now,last ,add):
    for next in ki[now]:
        if next == last:continue
        cnt[next] += add 
        dfs(next,now,cnt[next])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
n,q = map(int,input().split())
ki = [[]for _ in range(n)]
def dfs(now,last = -1):
    for next in ki[now]:
        if next == last:continue
        cnt[next] += cnt[now]
        dfs(next,now)

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

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)
for _ in range(n-1):
    a,b = map(int,input().split())
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)

from collections import defaultdict
dicp = defaultdict(int)

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


ansl = [0 for i in range(n)]
used = [0 for i in range(n)]
quu = [0]
used[0] = 1
ansl[0] = dicp[0]
while quu:
    k = quu.pop()
    for p in dic[k]:
        if used[p] == 0:
            quu.append(p)
            used[p] = 1
            ansl[p] = ansl[k] + dicp[p]



for a in ansl:
    print(a)

Submission status: Time Limit Exceeded

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

n,q = map(int,input().split())
from collections import defaultdict
dic = defaultdict(list)
for _ in range(n-1):
    a,b = map(int,input().split())
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)

from collections import defaultdict
dicp = defaultdict(int)

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


ansl = [0 for i in range(n)]
used = [0 for i in range(n)]
def dfs(pos, point):
    point += dicp[pos]
    used[pos] = 1
    ansl[pos] = point
    for p in dic[pos]:
        if used[p] == 0:
            dfs(p, point)

dfs(0, 0)

for a in ansl:
    print(a)

Submission status: Time Limit Exceeded

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

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

cnt=[0]*(N+1)
for el in px:
    cnt[el[0]]+=el[1]
#print(cnt)


lst=[[] for _ in range(N+1)]
for el in ab:
    lst[el[0]].append(el[1])
    lst[el[1]].append(el[0])
#print(lst)

seen = [False] * (N + 1)
def dfs(n):
    seen[n] = True
    for child in lst[n]:
        if seen[child] == False:
            cnt[child]+=cnt[n]
            dfs(child)

dfs(1)
#print(cnt)
print(' '.join(list(map(str, cnt[1:]))))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
#points=[tuple(map(int,input().split())) for _ in range(Q)]
score=[0]*N
for i in range(Q):
    point,sc=map(int,input().split())
    score[point-1]=score[point-1]+sc
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
v=0
d=deque()
d.append(v)
for i in range(N):
    dirtree[i]=tuple(dirtree[i])
dirtree=tuple(dirtree)
score=tuple(score)
#print(dirtree)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[tuple(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
#print(dirtree)
points=tuple(points)
for i in range(Q):
    score[points[i][0]-1]=score[points[i][0]-1]+points[i][1]
#print(score)
v=0
d=deque()
d.append(v)
for i in range(N):
    dirtree[i]=tuple(dirtree[i])
dirtree=tuple(dirtree)
score=tuple(score)
#print(dirtree)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[list(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
#print(dirtree)
for i in range(Q):
    score[points[i][0]-1]=score[points[i][0]-1]+points[i][1]
#print(score)
v=0
d=deque()
d.append(v)
for i in range(N):
    dirtree[i]=tuple(dirtree[i])
dirtree=tuple(dirtree)
#print(dirtree)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[list(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
#print(dirtree)
for i in range(Q):
    score[points[i][0]-1]=score[points[i][0]-1]+points[i][1]
#print(score)
v=0
d=deque()
d.append(v)
dirtree=tuple(dirtree)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def dfs(G,s,p):
    for nv in G[s]:
        if(nv==p):
            continue
        Count[nv]+=Count[s]
        dfs(G,nv,s)
    
N,Q=map(int,input().split())
Count=[0]*N
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
for i in range(Q):
    p,x=map(int,input().split())
    Count[p-1]+=x
dfs(G,0,-1)
print(*Count)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[list(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
ans=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input(
#print(dirtree)
for i in range(Q):
    score[points[i][0]-1]=score[points[i][0]-1]+points[i][1]
#print(score)
v=0
d=deque()
d.append(v)
ans[0]=score[0]
while len(d)!=0:
    v=d.popleft()
    for j in dirtree[v]:
        ans[j]=ans[v]+score[j]
        d.append(j)
    #input()
    #print(ans)
print(*ans,sep=" ")

Submission status: Time Limit Exceeded

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

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

def update(v, p):
    for next in tree[v]:
        if next == p:
            continue
        counter[next] += counter[v]
        update(next, v)

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

for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
update(0, -1)
print(" ".join(map(str, counter)))

Submission status: Time Limit Exceeded

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

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

def update(v, p):
    for next in tree[v]:
        if next == v:
            continue
        counter[next] += counter[v]
        update(next, v)
    
tree = [[] for _ in range(N)]
counter = [0] * N

for _ in range(N-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
for _ in range(Q):
    p, x = map(int, input().split())
    counter[p-1] += x
update(0, -1)
print(" ".join(map(str, counter)))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,Q=map(int,input().split())
nondirtree=[[] for _ in range(N)]
dirtree=[[] for _ in range(N)]
rootflag=[0]*N
rootflag[0]=1
for i in range(N-1):
    a,b=map(int,input().split())
    nondirtree[a-1].append(b-1)
    nondirtree[b - 1].append(a - 1)
points=[list(map(int,input().split())) for _ in range(Q)]
#print(points)
v=0
d=deque()
d.append(v)
seen=[0]*N
seen[0]=1
score=[0]*N
while len(d)!=0:
    v=d.popleft()
    for j in nondirtree[v]:
        if seen[j]==0:
            dirtree[v].append(j)
            seen[j]=1
            d.append(j)
    #print(d,seen,dirtree)
    #input()
for i in range(Q):
    d=deque()
    v=points[i][0]-1
    d.append(v)
    while len(d)!=0:
        v=d.popleft()
        score[v]=score[v]+points[i][1]
        for j in dirtree[v]:
            d.append(j)
        #input()
print(*score,sep=" ")

Submission status: Time Limit Exceeded

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

def dfs(G,v,p):
    if v != p and p != -1:
        counter[v]+=counter[p]

    for next in G[v]:
        if next == p:
            continue
        dfs(G,next,v)
    

N,Q = map(int, input().split())
counter = [0]*N
G = [[] for _ in range(N)]

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

#print(subtree)
for _ in range(Q):
    p,x = map(int, input().split())
    p-=1
    counter[p]+=x
dfs(G,0,-1)
counter = map(str,counter)
print(' '.join(counter))

Submission status: Time Limit Exceeded

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

def dfs(G,v,p):
    for next in G[v]:
        if next == p:
            continue
        dfs(G,next,v)
    
    for c in G[v]:
        if c == p:
            continue
        subtree[v].append(c)
        subtree[v]+=subtree[c]

N,Q = map(int, input().split())
counter = [0]*N
G = [[] for _ in range(N)]

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

subtree = [[] for _ in range(N)]
dfs(G,0,-1)
#print(subtree)
for _ in range(Q):
    p,x = map(int, input().split())
    p-=1
    counter[p]+=x
    for i in subtree[p]:
        counter[i]+=x
counter = map(str,counter)
print(' '.join(counter))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
V = [[] for _ in range(N)]
X = [0 for _ in range(N)]

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

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x
# p親、n現在、s合計
def dfs(p, n):
    for i in V[n]:
        if i == p:
            continue
        X[i] += X[n] 
        dfs(n, i)
dfs(-1,0)
print(*X)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
V = [[] for _ in range(N)]
X = [0 for _ in range(N)]

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

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x
# p親、n現在、s合計
def dfs(p, n):
    for i in V[n]:
        if i == p:
            continue
        else:
            X[i] += X[n] 
            dfs(n, i)
dfs(-1,0)
print(*X)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
V = [[] for _ in range(N)]
X = [0 for _ in range(N)]

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

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x
# p親、n現在、s合計
def dfs(p, n):
    for i in V[n]:
        if i == p:
            continue
        else:
            X[i] += X[n] 
            dfs(n, i)
dfs(-1,0)
for i in range(N):
    print(X[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
V = [[] for _ in range(N)]
X = [0 for _ in range(N)]

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

for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x
# p親、n現在、s合計
def dfs(p, n, s):
    X[n] += s
    for i in V[n]:
        if i == p:
            continue
        else:
            dfs(n, i, X[n])
dfs(-1,0,0)
for i in range(N):
    print(X[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys

n, q = map(int, input().split())
sys.setrecursionlimit(2 * (10 ** 5))

adj_list = [[] for _ in range(n + 1)]

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

val = [0] * (n + 1)
visited = [False] * (n + 1)

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


def dfs(val, adj_list, visited, cur, prev):
    if prev != -1:
        val[cur] += val[prev]

    visited[cur] = True

    for next in adj_list[cur]:
        if visited[next] is False:
            dfs(val, adj_list, visited, next, cur)


dfs(val, adj_list, visited, 1, -1)

for i in range(n):
    print(val[i + 1], end="")
    if i != n - 1:
        print(" ", end="")
    else:
        print()

Submission status: Time Limit Exceeded

Solution code:
import sys

n, q = map(int, input().split())
sys.setrecursionlimit(2 * (10 ** 5))

adj_list = [[] for _ in range(n + 1)]

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

val = [0] * (n + 1)
visited = [False] * (n + 1)

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


def dfs(val, adj_list, visited, cur, prev):
    if prev != -1:
        val[cur] += val[prev]

    visited[cur] = True

    for next in adj_list[cur]:
        if visited[next] is False:
            dfs(val, adj_list, visited, next, cur)


dfs(val, adj_list, visited, 1, -1)

for i in range(n):
    print(val[i + 1], end="")
    if i != n - 1:
        print(" ", end="")
    else:
        print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
n,q = map(int, input().split())
edge = [[] for _ in range(n)]
counter = [0]*n
for _ in range(n-1):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
for _ in range(q):
    a, b = map(int, input().split())
    counter[a-1] += b
def dfs(start, prev=-1):
    for i in edge[start]:
        if i == prev: continue
        counter[i] += counter[start]
        dfs(i, start)
dfs(0)
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
stdin=sys.stdin

ns=lambda:input().rstrip()
ni=lambda:int(input().rstrip())
nm=lambda:map(int,input().split())
nl=lambda:list(map(int,input().split()))

N,Q=nm()
AB=[nl() for i in range(N-1)]
PQ=[nl() for i in range(Q)]
root=[[] for i in range(N)]
N_val=[0]*N
ans_val=[0]*N
d=[0]*N

def bfs():
  que=deque([])
  que.append(0)
  while que:
    p=que.popleft()
    for i in root[p]:
       if(d[i]==0):
         ans_val[i]=ans_val[p]+N_val[i]
         que.append(i)
         d[i]=1
      
def dfs(x,d,s):
  for i in root[x]:
    if(d[i]==0):
      s+=N_val[i]
      ans_val[i]=s
      d[i]=1
      dfs(i,d,s)
      s-=N_val[i]
      

for i in range(N-1):
  root[AB[i][0]-1]+=[AB[i][1]-1]
  root[AB[i][1]-1]+=[AB[i][0]-1]
  
for i in range(Q):
  N_val[PQ[i][0]-1]+=PQ[i][1]

  
ans_val[0]=N_val[0]
d[0]=1
#dfs(0,d,N_val[0])
bfs()
print(*ans_val)

Submission status: Time Limit Exceeded

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


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

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

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

    counter = [-1] * n

    def calculate(p, i, v):
        total = operations[i] + v
        for c in edges[i]:
            if c != p:
                calculate(i, c, total)
        counter[i] = total

    calculate(-1, 0, 0)
    print(*counter)


main()