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(1000000)
input = sys.stdin.buffer.readline
def inp():
    return map(int,input().split())
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = inp()
    e[a-1].append(b-1)
    e[b-1].append(a-1)

p = [0] * n
for _ in range(q):
    pp, x = inp()
    p[pp - 1] += x


def dfs(i=0, r=-1):
    for j in e[i]:
        if j != r:
            p[j] += p[i]
            dfs(j, i)
dfs()

print(*p)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.buffer.readline
def inp():
    return map(int,input().split())
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = inp()
    e[a-1].append(b-1)
    e[b-1].append(a-1)

p = [0] * n
for _ in range(q):
    pp, x = inp()
    p[pp - 1] += x


def dfs(i=0, r=-1):
    for j in e[i]:
        if j != r:
            p[j] += p[i]
            dfs(j, i)
dfs()

print(*list(map(str,p)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.buffer.readline
def inp():
    return map(int,input().split())
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = inp()
    e[a-1].append(b-1)
    e[b-1].append(a-1)

p = [0] * n
for _ in range(q):
    pp, x = inp()
    p[pp - 1] += x


def dfs(i=0, r=-1):
    for j in e[i]:
        if j != r:
            p[j] += p[i]
            dfs(j, i)
dfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.buffer.readline
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

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


def dfs(i=0, r=-1):
    for j in e[i]:
        if j != r:
            p[j] += p[i]
            dfs(j, i)
dfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.buffer.readline
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

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


def dfs(i=0, r=-1):
    if r!=-1:
        p[i] += p[r]
    for j in e[i]:
        if j != r:
            dfs(j, i)
dfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

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


def dfs(i=0, r=-1):
    if r!=-1:
        p[i] += p[r]
    for j in e[i]:
        if j != r:
            dfs(j, i)
dfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

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


def dfs(i=0, r=-1):
    if r!=-1:
        p[i] += p[r]
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)
dfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, q = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

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


def dfs(i=0, r=-1, po=0):
    p[i] += po
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i,p[i])
dfs()

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
#グラフの連結成分を調べる
def Graph(ab):
    G=[[] for i in range(n)]
    for a,b in ab:
        G[a-1].append(b)
        G[b-1].append(a)
    return G
from collections import deque
def dfs(G,v,p):
    q=deque()
    q.append((v,p))
    log=[False]*n
    log[v-1]=True
    while q:
        V,P=q[-1]
        for new_v in G[V-1]:
            if new_v==P:continue
            if log[new_v-1]:continue
            log[new_v-1]=True
            score[new_v-1]+=score[V-1]
            q.append((new_v,V))
            break
        else:
            q.pop()


n,q=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n-1)]

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

G=Graph(ab)
#print(G,score,sep='\n')
dfs(G,1,-1)
print(*score)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

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


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

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

print(" ".join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

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


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

cur(1)
print(" ".join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


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

cur(1)
print(" ".join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

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

def cur(x):
    for p in neighbor[x]:
        par=parent[x]
        if p!=par:
            parent[p]=x
            ans[p]+=ans[x]
            cur(p)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)

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

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

cur(1)
print(" ".join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

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


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

cur(1)
print(" ".join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

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


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

cur(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


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

cur(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

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

def cur(x):
    for p in neighbor[x]:
        if p!=parent[x]:
            parent[p]=x
            ans[p]+=ans[x]
            cur(p)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)

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

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

cur(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())

table = [[False for i in range(n)] for j in range(n)]

for i in range(n-1):
    before, after = map(int, input().split())
    table[before-1][after-1] = True
    table[after-1][before-1] = True

scores = [0 for i in range(n)]
for i in range(q):
    node, score = map(int, input().split())
    scores[node-1] += score

ans = [0 for i in range(n)]
def dfs(frm, cur, score):
    score += scores[cur]
    ans[cur] += score

    for i in range(n):
        if table[cur][i] == True and i != frm:
            dfs(cur, i, score)

dfs(-1, 0, 0)

print(*ans)

Submission status: Time Limit Exceeded

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

table = [[False for i in range(n)] for j in range(n)]

for i in range(n-1):
    before, after = map(int, input().split())
    table[before-1][after-1] = True
    table[after-1][before-1] = True

scores = [0 for i in range(n)]
for i in range(q):
    node, score = map(int, input().split())
    scores[node-1] += score

ans = [0 for i in range(n)]
def dfs(frm, cur, score):
    score += scores[cur]
    ans[cur] += score

    for i in range(n):
        if table[cur][i] == True and i != frm:
            dfs(cur, i, score)

dfs(-1, 0, 0)

print(*ans)

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in range(len(neighbor[x])):
        p=neighbor[x][i]
        if p==parent[x]: continue
        parent[p]=x
        ans[p]+=ans[x]
        cur(p)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)

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

cur(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in dd[x]:
        if dd[x][i]==-1: continue
        dd[i][x]=-1
        ans[i]+=ans[x]
        cur(i)

n,q=map(int,input().split())
dd=collections.defaultdict(dict)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    dd[a][b]=1
    dd[b][a]=1

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

cur(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in dd[x]:
        dd[i].remove(x)
        ans[i]+=ans[x]
        cur(i)

n,q=map(int,input().split())
dd=collections.defaultdict(list)
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    dd[a].append(b)
    dd[b].append(a)

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

cur(1)
print(*ans[1:])

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in neighbor[x]:
        if i==parent[x]: continue
        parent[i]=x
        ans[i]+=ans[x]
        cur(i)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)

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

cur(1)
print(" ".join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

n,q=map(int,input().split())
neighbor=[set()  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].add(b)
    neighbor[b].add(a)


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

cur(1)
print(" ".join(map(str,ans[1:])))

Submission status: Time Limit Exceeded

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

def cur(x):
    for i in neighbor[x]:
        ans[i]+=ans[x]
        neighbor[i].remove(x)
        cur(i)

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
parent=[-1]*(n+1)
ans=[0]*(n+1)
for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


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

cur(1)
for i in range(1,n):
    print(ans[i],end=" ")
print(ans[n])

Submission status: Time Limit Exceeded

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

points = [0 for _ in range(N)]
for i in range(Q):
  p, x = map(int, input().split())
  points[p-1] += x
  
def dfs(v, pv):
  for nv in G[v]:
    if nv != pv:
      points[nv] += points[v]
      dfs(nv, v)

dfs(0, 0)
print(*points)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
  a, b = map(int,input().split())
  G[a-1].append(b-1)
  G[b-1].append(a-1)
# points = [0 for _ in range(n)]
points = [0]*N
for i in range(Q):
  p, x = map(int, input().split())
  points[p-1] += x
  
def dfs(v, pv):
  for nv in G[v]:
    if nv != pv:
      points[nv] += points[v]
      dfs(nv, v)

dfs(0, 0)
print(*points)

Submission status: Time Limit Exceeded

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

points = [0]*N
for i in range(Q):
  p, x = map(int, input().split())
  points[p-1] += x
  
def dfs(v, pv):
  global points
  for nv in G[v]:
    if nv != pv:
      points[nv] += points[v]
      dfs(nv, v)

dfs(0, 0)
print(*points)

Submission status: Time Limit Exceeded

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

def dfs(v, pv):
    global P

    for nv in G[v]:
        if nv != pv:
            P[nv] += P[v]
            dfs(nv, v)

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

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


dfs(0, 0)
print(*P)

Submission status: Time Limit Exceeded

Solution code:
# Author: cr4zjh0bp
# Created: Tue Mar 17 19:50:06 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

sys.setrecursionlimit(10 ** 6)

n, q = na()
ab = nan(n - 1)
px = nan(q)

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

cnt = [0 for _ in range(n)]
for i in range(q):
    p, x = px[i]
    p -= 1
    cnt[p] += x

def dfs(i, p, s):
    x = s + cnt[i]
    cnt[i] = x
    for j in tree[i]:
        if j == p:
            continue
        dfs(j, i, x)

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

Submission status: Time Limit Exceeded

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

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

e = [list(map(int, input().split())) for _ in range(n-1)]
cm = [list(map(int, input().split())) for _ in range(q)]
parent = [-1]*n
child = [[]]*n
counter = [0]*n

for i, v in cm:
  counter[i-1] += v

parent[0] = 0
for a, b in e:
  parent[b-1] = a-1
  child[a-1] += [b-1]

cum_counter = [0]*n
def check(i, cum_cnt):
  cum_cnt += counter[i]
  cum_counter[i] = cum_cnt
  if len(child[i])>0:
    for c in child[i]:
      check(c, cum_cnt)

check(0, 0)
print(*cum_counter)

Submission status: Time Limit Exceeded

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

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

edges = [[] for _ in range(n)]
cnt = [0 for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
    
for _ in range(q):
    p, x = map(int, input().split())
    cnt[p-1] += x
    
def dfs(frm, cur):
    for to in edges[cur]:
        if to != frm:
            cnt[to] += cnt[cur]
            dfs(cur, to)
dfs(-1, 0)          
print(*cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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


def dfs(i=0, r=-1, po=0):
    p[i] += po
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i,p[i])
dfs()

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

Submission status: Time Limit Exceeded

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

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

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


def dfs(i=0, r=-1, po=0):
    p[i] += po
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i,p[i])
dfs()

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

Submission status: Time Limit Exceeded

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

n, q = map(int, readline().split())
G = defaultdict(list)
for _ in range(n-1):
    a, b = map(int, readline().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
count = [0] * n
for _ in range(q):
    p, x = map(int, readline().split())
    count[p-1] += x


def dfs(root, x):
    ans[root] = count[root] + x
    for i in G[root]:
        if ans[i] == -1:
            dfs(i, ans[root])


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
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)]
E = [[] for i in range(N+1)]
for i in range(N-1):
    E[ab[i][0]].append(ab[i][1])
    E[ab[i][1]].append(ab[i][0])

d = [0]*(N+1)
visit = [0]*(N+1)
for i in range(Q):
    d[px[i][0]]+=px[i][1]
def bfs(s):
    q = deque([s])
    while q:
        v = q.pop()
        visit[v] = 1
        for j in E[v]:
            if(visit[j] == 1):
                continue
            q.append(j)
            d[j] += d[v]
            
bfs(1)
for i in range(1,N+1):
    print(d[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
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)
ans = [0]*N
for i in range(Q) :
    pi, xi = map(int,input().split())
    ans[pi-1] += xi

def dfs(n) :
    visited[n] = 1
    for i in G[n] :
        if visited[i] == 1 :
            continue
        ans[i] += ans[n]
        dfs(i)

visited = [0]*N
dfs(0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
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)
ans = [0]*N
for i in range(Q) :
    pi, xi = map(int,input().split())
    ans[pi-1] += xi

def dfs(n) :
    visited[n] = 1
    for i in G[n] :
        if visited[i] == 1 :
            continue
        ans[i] += ans[n]
        dfs(i)

visited = [0]*N
dfs(0)

print(*ans, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
 
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
#n = int(input())
n,q = [int(i) for i in readline().split()]
 
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 
add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x
 
ans = [0]*n
#ans[0] = add[0]
 
def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)
 
dfs(0,-1,0)
 
#print(add)
 
print(*ans)

Submission status: Time Limit Exceeded

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

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

g = [[] for _ in range(n)]
c = [0] * n
visited = [False] * n

#根に近い順に累積和
def dfs(i):
    visited[i] = True
    for j in g[i]:
        if visited[j] == True:
            continue
        c[j]+=c[i]
        dfs(j)

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

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

dfs(0)
print(*c)

Submission status: Time Limit Exceeded

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

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

g = [[] for _ in range(n)]
c = [0] * n
visited = [False] * n

#根に近い順に累積和
def dfs(i):
    visited[i] = True
    for j in g[i]:
        if visited[j] == True:
            continue
        c[j]+=c[i]
        dfs(j)

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

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

dfs(0)
print(*c)

Submission status: Time Limit Exceeded

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

g = [[] for _ in range(n)]
c = [0] * n
visited = [False] * n

#根に近い順に累積和
def dfs(i):
    visited[i] = True
    for j in g[i]:
        if visited[j] == True:
            continue
        c[j]+=c[i]
        dfs(j)

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

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

dfs(0)
print(*c)

Submission status: Time Limit Exceeded

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

def dfs(parent: int, i: int) -> None:
    for _p in g[i]:
        if _p == parent:
            continue
        else:
            counter[_p] += counter[i]
            dfs(i, _p)

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

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

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

    counter[p-1] += x

dfs(-1, 0)

print(*counter)

Submission status: Time Limit Exceeded

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

def dfs(parent: int, i: int) -> None:
    counter[i] += counter[parent]

    for _p in g[i]:
        if _p == parent:
            continue
        dfs(i, _p)

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

    g[a].append(b)
    g[b].append(a)

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

    counter[p] += x

dfs(0, 1)

print(*counter[1:n+1])

Submission status: Time Limit Exceeded

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

def dfs(parent: int, i: int) -> None:
    counter[i] += counter[parent]

    for _p in t[i]:
        if _p == parent:
            continue
        dfs(i, _p)

n, q = map(int, input().split())
t = {}
for _ in range(n-1):
    a, b = map(int, input().split())
    t.setdefault(a, [])
    t.setdefault(b, [])

    t[a].append(b)
    t[b].append(a)

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

    counter[p] += x

dfs(0, 1)

print(*counter[1:n+1])

Submission status: Time Limit Exceeded

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

t = {}
counter = [0]*(2*10**5+1)

def dfs(parent: int, i: int) -> None:
    counter[i] += counter[parent]

    for _p in t[i]:
        if _p == parent:
            continue
        dfs(i, _p)

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

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

        t[a].append(b)
        t[b].append(a)

    for _ in range(q):
        p, x = map(int, input().split())

        counter[p] += x

    dfs(0, 1)

    print(*counter[1:n+1])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

t = {}
counter = [0]*(2*10**6+1)

def dfs(parent: int, i: int) -> None:
    counter[i] += counter[parent]

    for _p in t[i]:
        if _p == parent:
            continue
        dfs(i, _p)

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

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

        t[a].append(b)
        t[b].append(a)

    for _ in range(q):
        p, x = map(int, input().split())

        counter[p] += x

    dfs(0, 1)

    counter.pop(0)
    print(*counter[:n])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

t = {}

def dfs(parent: int, i: int, counter: list) -> None:
    counter[i] += counter[parent]

    for _p in t[i]:
        if _p == parent:
            continue
        dfs(i, _p, counter)

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

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

        t[a].append(b)
        t[b].append(a)

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

        counter[p] += x

    dfs(0, 1, counter)

    counter.pop(0)
    print(*counter)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def dfs(parent: int, i: int, t: dict, counter: list) -> None:
    counter[i] += counter[parent]

    for _p in t[i]:
        if _p == parent:
            continue
        dfs(i, _p, t, counter)

def main():
    n, q = map(int, input().split())
    t = {}
    for _ in range(n-1):
        a, b = map(int, input().split())
        t.setdefault(a, [])
        t.setdefault(b, [])

        t[a].append(b)
        t[b].append(a)

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

        counter[p] += x

    dfs(0, 1, t, counter)

    counter.pop(0)
    print(*counter)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

N, Q = map(int, input().split())
info = [[] for _ in range(N)]
ans = [0 for _ in range(N)]
check = [True for _ in range(N)]

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


def plus(n, val):
    ans[n] += val
    check[n] = False
    for i in info[n]:
        if check[i]:
            plus(i, val + Query[i])


Query = [0 for _ in range(N)]
for _ in range(Q):
    p, x = map(int, input().split())
    Query[p - 1] += x
plus(0, Query[0])
ans = list(map(str, ans))
print(" ".join(ans))