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**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = [0] * N
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def get_connected_vertices(v):
    return all_connected_vertices[v]
    
def dfs(point, pre):
    connected_vertices = get_connected_vertices(point)
    children = [v for v in connected_vertices if v != pre]
    for c in children:
        counts[c-1] += counts[point-1]
        dfs(c, point)
    
dfs(1, -1)
    
print(*counts)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = [0] * N
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def get_connected_vertices(v):
    return all_connected_vertices[v]
    
visited_vertices = [] 
def dfs(point, pre):
    visited_vertices.append(point)
    connected_vertices = get_connected_vertices(point)
    children = [v for v in connected_vertices if v != pre]
    for c in children:
        counts[c-1] += counts[point-1]
        dfs(c, point)
    
dfs(1, -1)
res = ""
for c in counts:
    res += " " + str(c)
    
print(res[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = [0] * N
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def get_connected_vertices(v):
    return all_connected_vertices[v]
    
visited_vertices = [] 
def dfs(point):
    visited_vertices.append(point)
    connected_vertices = get_connected_vertices(point)
    children = [v for v in connected_vertices if v not in visited_vertices]
    for c in children:
        counts[c-1] += counts[point-1]
        dfs(c)
    
dfs(1)
res = ""
for c in counts:
    res += " " + str(c)
    
print(res[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6) #for deep recursion

N, Q = list(map(int, input().split()))
edges = [list(map(int, input().split())) for _ in range(N-1)]
counts = [0] * N
operations = [list(map(int, input().split())) for _ in range(Q)]

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
all_connected_vertices = {i: [] for i in range(1, 1+N)}
for a, b in edges:
    all_connected_vertices[a].append(b)
    all_connected_vertices[b].append(a)
    
def get_connected_vertices(v):
    res = all_connected_vertices[v]
    return list(set(res))    
    
visited_vertices = [] 
def dfs(point):
    visited_vertices.append(point)
    connected_vertices = get_connected_vertices(point)
    children = [v for v in connected_vertices if v not in visited_vertices]
    for c in children:
        counts[c-1] += counts[point-1]
        dfs(c)
    
dfs(1)
res = ""
for c in counts:
    res += " " + str(c)
    
print(res[1:])

Submission status: Time Limit Exceeded

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

counts = [0] * N
for op in operations:
    p, x = op
    counts[p-1] += x
    
def get_connected_vertices(v):
    res = []
    for e in edges:
        a, b = e
        if a == v:
            res.append(b)
        if b == v:
            res.append(a)
    return list(set(res))    
    
visited_vertices = [] 
def dfs(point):
    visited_vertices.append(point)
    connected_vertices = get_connected_vertices(point)
    children = [v for v in connected_vertices if v not in visited_vertices]
    for c in children:
        counts[c-1] += counts[point-1]
        dfs(c)
    
dfs(1)
res = ""
for c in counts:
    res += " " + str(c)
    
print(res[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
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)
    e[b-1].append(a-1)

ans = [0]*n

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

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

dfs()

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
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)
    e[b-1].append(a-1)

ans = [0]*n

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

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

dfs()

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
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)
    e[b-1].append(a-1)
ans = [0]*n
for i in range(q):
	p,x = map(int,input().split()) 
	ans[p-1] += x

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
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)
    e[b-1].append(a-1)
ans = [0]*n
for i in range(q):
	p,x = map(int,input().split()) 
	ans[p-1] += x

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
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)
    e[b-1].append(a-1)
    ans = [0]*n
for i in range(q):
    p,x = map(int,input().split()) 
    ans[p-1] += x

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

Submission status: Time Limit Exceeded

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

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

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

POINT = [0] * (N + 1)

for _ in range(Q):
    p, x = map(int, readline().split())
    POINT[p] += x


ans = [0] * (N+1)

STATE = [False] * (N+1)


def dfs(s, plus):
    p = POINT[s]
    pt = p + plus
    ans[s] += pt

    STATE[s] = True

    for v in PATH[s]:
        if STATE[v]:
            continue
        dfs(v, pt)


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

Submission status: Time Limit Exceeded

Solution code:
n,Q=map(int,input().split())
g=[[] for i 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)
depth=[-1]*n
depth[0]=0
q=[0]
while q:
  x=q.pop()
  for t in g[x]:
    if depth[t]==-1:
      depth[t]=depth[x]+1
      q.append(t)
cnt=[0]*n
for _ in range(Q):
  p,x=map(int,input().split())
  q=[p-1]
  while q:
    y=q.pop()
    cnt[y]+=x
    for t in g[y]:
      if depth[t]>depth[y]:
        q.append(t)
print(*cnt)

Submission status: Time Limit Exceeded

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

def main():
    n,q=map(int,input().split())
    G=[[] for i in range(n)] #隣接配列
    P=[0]*n #親のポイント
    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())
        p-=1
        P[p]+=x
    def dfs(s,p=-1):        
        for i in G[s]:
            if i==p:
                continue
            P[i]+=P[s]
            dfs(i,s)

    dfs(0)
    print(*P)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

def main():
    n,q=map(int,input().split())
    G=[[] for i in range(n)] #隣接配列
    P=[0]*n #親のポイント
    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())
        p-=1
        P[p]+=x
    def dfs(s,p=-1):        
        for i in G[s]:
            if i==p:
                continue
            P[i]+=P[s]
            dfs(i,s)

    dfs(0)
    print(*P)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def main():
    n,q=map(int,input().split())
    G=[[] for i in range(n)] #隣接配列
    P=[0]*n #親のポイント
    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())
        p-=1
        P[p]+=x
    def dfs(s,p=-1):        
        for i in G[s]:
            if i!=p:
                P[i]+=P[s]
                dfs(i,s)

    dfs(0)
    print(*P)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n,q=map(int,input().split())
G=[[] for i in range(n)] #隣接配列
P=[0]*n #親のポイント
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())
    p-=1
    P[p]+=x
    

def dfs(s,p=-1):        
    for i in G[s]:
        if i!=p:
            P[i]+=P[s]
            dfs(i,s)

dfs(0)
print(*P)

Submission status: Time Limit Exceeded

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

n,q=map(int,input().split())
G=[[] for i in range(n)] #隣接配列
P=[0]*n #根のポイント
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())
    p-=1
    P[p]+=x
    

def dfs(s,p=-1,cnt=0):
    cnt+=P[s]
    P[s]=cnt
    for i in G[s]:
        if i!=p:
            dfs(i,s,cnt)

dfs(0)
print(*P)

Submission status: Time Limit Exceeded

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

n,q=map(int,input().split())
G=[[] for i in range(n)] #隣接配列
P=[0]*n #根のポイント
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())
    p-=1
    P[p]+=x
    

def dfs(s,p=-1,cnt=0):
    cnt+=P[s]
    P[s]=cnt
    for i in G[s]:
        if i!=p:
            dfs(i,s,cnt)

dfs(0)
print(*P,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,q=map(int,input().split())
G=[[] for i in range(n)] #隣接配列
P=[0]*n #根のポイント
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())
    p-=1
    P[p]+=x
    

def dfs(s,p=-1,cnt=0):
    cnt+=P[s]
    P[s]=cnt
    for i in G[s]:
        if i!=p:
            dfs(i,s,cnt)

dfs(0)
print(*P,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,q=map(int,input().split())
G=[[] for i in range(n)] #隣接配列
P=[0]*n #根のポイント
A=[0]*n #こたえ
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())
    p-=1
    P[p]+=x
    

def dfs(s,p=-1,cnt=0):
    cnt+=P[s]
    A[s]=cnt
    for i in G[s]:
        if i!=p:
            dfs(i,s,cnt)

dfs(0)
print(*A,sep=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

n,q=map(int,input().split())
G=[[] for i in range(n)] #隣接配列
P=[0]*n #根のポイント
A=[0]*n #こたえ
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())
    p-=1
    P[p]+=x
    

def dfs(s,p=-1,cnt=0):
    cnt+=P[s]
    A[s]=cnt
    for i in G[s]:
        if i!=p:
            dfs(i,s,cnt)

dfs(0)
for a in A:
    print(a,end=" ")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def find_desc(done, v=1):
    global desc, rels
    for d in rels[v]:
        if d in done:
            continue
        done.append(d)
        desc[v].add(d)
        find_desc(done, d)


N, Q = map(int, input().split())
rels = [None] + [set() for _ in range(N)]
for _ in range(N - 1):
    ai, bi = map(int, input().split())
    rels[ai].add(bi)
    rels[bi].add(ai)

desc = [None] + [set() for _ in range(N)]
find_desc([1], 1)

counter = [None] + [0] * N
for _ in range(Q):
    pi, xi = map(int, input().split())
    counter[pi] += xi
for p in range(1, N + 1):
    for d in desc[p]:
        counter[d] += counter[p]

print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def find_desc(done, rels, v=1):
    global desc
    for d in rels[v]:
        if d in done:
            continue
        done.append(d)
        desc[v].add(d)
        find_desc(done, rels, d)


def inc(p, x):
    global counter, desc
    counter[p] += x
    for d in desc[p]:
        inc(d, x)


N, Q = map(int, input().split())
rels = [None] + [set() for _ in range(N)]
for _ in range(N - 1):
    ai, bi = map(int, input().split())
    rels[ai].add(bi)
    rels[bi].add(ai)

desc = [None] + [set() for _ in range(N)]
find_desc([1], rels)
counter = [0] * len(rels)
for _ in range(Q):
    pi, xi = map(int, input().split())
    inc(pi, xi)

print(*counter[1:])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


class CountTree:
    def __init__(self, relations):
        self.relations = relations
        self.desc = [set() for _ in range(len(relations))]
        self._find_desc([1])
        self.counter = [0] * len(relations)

    def _find_desc(self, done, v=1):
        for desc in self.relations[v]:
            if desc in done:
                continue
            done.append(desc)
            self.desc[v].add(desc)
            self._find_desc(done, desc)

    def inc(self, p, x):
        self.counter[p] += x
        for d in self.desc[p]:
            self.inc(d, x)

    def p_cnt(self):
        print(*self.counter[1:])


N, Q = map(int, input().split())
relations = [None] + [set() for _ in range(N)]
for _ in range(N - 1):
    ai, bi = map(int, input().split())
    relations[ai].add(bi)
    relations[bi].add(ai)
ct = CountTree(relations)
for _ in range(Q):
    pi, xi = map(int, input().split())
    ct.inc(pi, xi)
ct.p_cnt()

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

jun = []
# O(2n)
def chil_pop(l,p):
    jun.append(l)
    for i in b[l]:
        if i == p:
            continue
        chil_pop(i,l)
    b[l] = p

chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x

for i in jun[1:]:
    ans[i] += ans[b[i]]

ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

jun = []
# O(2n)
def chil_pop(l,p):
    jun.append(l)
    for i in b[l]:
        if i == p:
            continue
        chil_pop(i,l)
    b[l] = p

chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x

for i in jun[1:]:
    ans[i] += ans[b[i]]

ans_str = ''
for i in range(n):
    print(ans[i],end=' ')
    # ans_str = ans_str + str(ans[i]) + ' '
# print(ans_str)

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n
# O(n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

jun = []

def chil_pop(l,p):
    jun.append(l)
    for i in b[l]:
        if i == p:
            continue
        chil_pop(i,l)
    b[l] = p

chil_pop(0,-1)

for i in range(q):
    p,x = mi()
    ans[p-1] += x

for i in jun[1:]:
    ans[i] += ans[b[i]]

ans_str = ''
for i in range(n):
    # print(ans[i],end=' ')
    ans_str = ans_str + str(ans[i]) + ' '
print(ans_str)

Submission status: Time Limit Exceeded

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

import sys
from collections import defaultdict

input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 6)


class Graph(object):
    """ Graph data structure, undirected by default. """

    def __init__(self, connections, directed=False):
        self._graph = defaultdict(set)
        self._directed = directed
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections (list of tuple pairs) to graph """

        for u, v in connections:
            self.add(u, v)

    def add(self, u, v):
        """ Add connection between node u and node v """

        self._graph[u].add(v)
        if not self._directed:
            self._graph[v].add(u)

    def get_adj(self, v):
        """ Get adjacency list of node v """
        return self._graph[v]

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._graph))


# -----
N, Q = map(int, input().split())
connections = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    connections.append((a, b))
query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])
# print(N, Q)
# print(connections, query)

keys = [v for v in range(1, N + 1)]
values = [0 for _ in range(N)]
counter = dict(zip(keys, values))
# print(counter)
for p, x in query:
    counter[p] += x


def dfs(v, parent):
    for v_next in g.get_adj(v):
        if v_next != parent:
            counter[v_next] += counter.get(v)
            dfs(v_next, v)


g = Graph(connections)
# print(g)

root = 1
dfs(root, None)

for c in counter.values():
    print(c, end=" ")

Submission status: Time Limit Exceeded

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

import sys

sys.setrecursionlimit(10 ** 6)

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

edges = [[] 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)

query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])

counter = [0 for _ in range(N)]
for p, x in query:
    counter[p - 1] += x


def dfs(v, parent):
    for v_next in edges[v]:
        if v_next != parent:
            counter[v_next] += counter[v]
            dfs(v_next, v)


root = 0
dfs(root, None)

print(*counter)

Submission status: Time Limit Exceeded

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

from collections import defaultdict


class Graph(object):
    """ Graph data structure, undirected by default. """

    def __init__(self, connections, directed=False):
        self._graph = defaultdict(set)
        self._directed = directed
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections (list of tuple pairs) to graph """

        for u, v in connections:
            self.add(u, v)

    def add(self, u, v):
        """ Add connection between node u and node v """

        self._graph[u].add(v)
        if not self._directed:
            self._graph[v].add(u)

    def get_adj(self, v):
        """ Get adjacency list of node v """
        return self._graph[v]

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._graph))


# -----
N, Q = map(int, input().split())
connections = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    connections.append((a, b))
query = []
for _ in range(Q):
    p, x = map(int, input().split())
    query.append([p, x])
# print(N, Q)
# print(connections, query)

keys = [v for v in range(1, N + 1)]
values = [0 for _ in range(N)]
counter = dict(zip(keys, values))
# print(counter)
for p, x in query:
    counter[p] += x


def dfs(v, parent):
    for v_next in g.get_adj(v):
        if v_next != parent:
            counter[v_next] += counter.get(v)
            dfs(v_next, v)


g = Graph(connections)
# print(g)

root = 1
dfs(root, None)

for c in counter.values():
    print(c, end=" ")

Submission status: Time Limit Exceeded

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

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

def dfs(parents,checked_par):
	for children in net[parents]:
		if children == checked_par:
			continue
		costs[children] += costs[parents]
		dfs(children,parents)
dfs(0,-1)

print(*costs)

Submission status: Time Limit Exceeded

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

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

def dfs(parents,checked_par):
	for children in net[parents]:
		if children == checked_par:
			continue
		costs[children] += costs[parents]
		dfs(children,parents)
dfs(0,-1)

print(*costs)

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n
# O(n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)


def chil_pop(l):
    for i in b[l]:
        b[i].pop(b[i].index(l))
        chil_pop(i)

chil_pop(0)

def chil_add(z,x):
    ans[z] += x
    for i in b[z]:
        chil_add(i,x)

for i in range(q):
    p,x = mi()
    chil_add(p-1,x)

ans_str = ''
for i in range(n):
    # print(ans[i],end=' ')
    ans_str = ans_str + str(ans[i]) + ' '
print(ans_str)

Submission status: Time Limit Exceeded

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

tree = {}
for _ in range(n-1):
  a , b = map(lambda x:int(x)-1, input().split())
  if a not in tree:
    tree[a] = [b]
  else:
    tree[a].append(b)
  if b not in tree:
    tree[b] = [a]
  else:
    tree[b].append(a)

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
already = []
for i in range(n):
  while will_go:
    now = will_go.pop()
    already.append(now)
    tmp = ans[now]
    for root in tree[now]:
      if root not in already:
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)

Submission status: Time Limit Exceeded

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

tree = {}
for _ in range(n-1):
  a , b = map(lambda x:int(x)-1, input().split())
  if a not in tree:
    tree[a] = [b]
  else:
    tree[a].append(b)
  if b not in tree:
    tree[b] = [a]
  else:
    tree[b].append(a)

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
already = []
for i in range(n):
  while will_go:
    now = will_go.pop()
    already.append(now)
    tmp = ans[now]
    if now in tree:
      for root in tree[now]:
        if root not in already:
          ans[root] += tmp
          will_go.append(root)
        
print(*ans)

Submission status: Time Limit Exceeded

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

tree = {}

tmp = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
will_go = [0]
already = []

while will_go:
  tmp2 = []
  now = will_go.pop()
  already.append(now)
  for node in tmp:
    if (now == node[0]) & (node[1] not in already):
      will_go.append(node[1])
      if now not in tree:
        tree[now] = [node[1]]
      else:
        tree[now].append(node[1])
    if (now == node[1]) & (node[0] not in already):
      will_go.append(node[0])
      if now not in tree:
        tree[now] = [node[0]]
      else:
        tree[now].append(node[0])
    else:
      tmp2.append(node)
  tmp = [i for i in tmp2]

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    if now in tree:
      for root in tree[now]:
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)


def chil_pop(l):
    for i in b[l]:
        b[i].pop(b[i].index(l))
        chil_pop(i)

chil_pop(0)

def chil_add(z,x):
    ans[z] += x
    for i in b[z]:
        chil_add(i,x)

for i in range(q):
    p,x = mi()
    chil_add(p-1,x)

for i in range(n):
    print(ans[i],end=' ')

Submission status: Time Limit Exceeded

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

tree = {}
tmp = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
will_go = [0]
already = []
while will_go:
  now = will_go.pop()
  already.append(now)
  for node in tmp:
    if (now == node[0]) & (node[1] not in already):
      will_go.append(node[1])
      if now not in tree:
        tree[now] = [node[1]]
      else:
        tree[now].append(node[1])
    if (now == node[1]) & (node[0] not in already):
      will_go.append(node[0])
      if now not in tree:
        tree[now] = [node[0]]
      else:
        tree[now].append(node[0])

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    if now in tree:
      for root in tree[now]:
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)

Submission status: Time Limit Exceeded

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

tree = {}

tmp = [list(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
will_go = [0]
already = []
while will_go:
  now = will_go.pop()
  already.append(now)
  for node in tmp:
    if (now == node[0]) & (node[1] not in already):
      will_go.append(node[1])
      if now not in tree:
        tree[now] = [node[1]]
      else:
        tree[now].append(node[1])
    if (now == node[1]) & (node[0] not in already):
      will_go.append(node[0])
      if now not in tree:
        tree[now] = [node[0]]
      else:
        tree[now].append(node[0])

ans = [0]*n
for _ in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
will_go = [0]
for i in range(n):
  while will_go:
    now = will_go.pop()
    tmp = ans[now]
    if now in tree:
      for root in tree[now]:
        ans[root] += tmp
        will_go.append(root)
        
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
#全体に同じものを足すときは累積和を考えたい

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

children = [set([]) for _ in range(N)]
#children[i]:i+1番目の頂点の子
counter = [0 for _ in range(N)]
#counter[i]:i+1番目の頂点のカウンター
check = [False for _ in range(N)]
check[0] = True
#check[i]:i+1番目の頂点を木に入れた
cnt = 1
while cnt < N:
    i = 0
    for i in range(N-1):
        if (not check[AB[i][0]-1]) and check[AB[i][1]-1]:
            children[AB[i][1]-1].add(AB[i][0])
            check[AB[i][0]-1] = True
            cnt += 1
        elif (not check[AB[i][1]-1]) and check[AB[i][0]-1]:
            children[AB[i][0]-1].add(AB[i][1])
            check[AB[i][1]-1] = True
            cnt += 1

for i in range(Q):
    counter[PX[i][0]-1] += PX[i][1]

def cal(children,counter,node):
    if len(children[node-1]) > 0:
        for child in children[node-1]:
            counter[child-1] += counter[node-1]
            cal(children,counter,child)

cal(children,counter,1)

print(str(counter[0]),end="")
for i in range(1,N):
    print(" "+str(counter[i]),end="")
print()