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 copy
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)

n ,m = ips()
tree = [[] for i in range(n+1)]
for i in range(n-1):
    x,y = ips()
    tree[x].append(y)
    tree[y].append(x)
total = [0 for i in range(n+1)]
for i in range(m):
    x,adder = ips()
    total[x]+=adder
base = copy.copy(total)
q = [1]
pos = 0
cs = set([1])
while len(q) > pos:
    #print("adding up",pos,q)
    i = q[pos]
    value = total[i]
    cs.add(i)
    if len(tree[i]):
        for k in tree[i]:
            if k not in cs:
                q.append(k)
                total[k]+=value
    pos+=1
for i in range(1,n):
    print(total[i],end=" ")
print(total[n])

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions
import copy
def j(q):
    if q==1: print("Yes")
    elif q == 0:print("No")
    exit(0)
rem = pow(10,9)+7
"""
def ct(x,y):
    if (x>y):print("+")
    elif (x<y): print("-")
    else: print("?")
"""

def ip():
    return int(input())
def iprow():
    return [int(i) for i in input().split()]
def ips():
    return (int(i) for i in input().split())
def printrow(a):
    for i in a:
        print(i)
"""
#decomment when needed
def combinations(n,r):
    if n<r:return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
def permutations(n,r):
    if n<r:return 0
    return math.factorial(n) // math.factorial(n - r)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
"""

def addbottom(total,tree,k,value,base):
    #print("current layer",k)
    #print(k,value)
    total[k]+=value
    #print(total)
    if len(tree[k]):
        for i in tree[k]:
            #print(k,i)
            total = addbottom(total, tree, i, value,base)
    return total


n ,m = ips()
tree = [[] for i in range(n+1)]
for i in range(n-1):
    x,y = ips()
    tree[x].append(y)
    tree[y].append(x)
total = [0 for i in range(n+1)]
for i in range(m):
    x,adder = ips()
    total[x]+=adder
base = copy.copy(total)
q = [1]
pos = 0
cs = set([1])
while len(q) > pos:
    #print("adding up",pos,q)
    i = q[pos]
    value = total[i]
    cs.add(i)
    if len(tree[i]):
        for k in tree[i]:
            if k not in cs:
                q.append(k)
                total[k]+=value
    pos+=1
for i in range(1,n):
    print(total[i],end=" ")
print(total[n])

Submission status: Time Limit Exceeded

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


def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N)]
    a = []
    b = []
    a_append = a.append
    b_append = b.append
    for i in range(N-1):
        x, y = map(int, input().split())
        a_append(x)
        b_append(y)
    cost = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cost[p-1] += x

    for i in range(N-1):
        ai = a[i]-1
        bi = b[i]-1
        ci = cost[i]
        link[ai].append((bi, ci))
        link[bi].append((ai, ci))

    def dfs(v, c, p):
        for nv in link[v]:
            nv0 = nv[0]
            if nv0 != p:
                cost[nv0] += c
                dfs(nv0, cost[nv0], v)

    dfs(0, cost[0], -1)

    print(*cost)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
 
def resolve():
    def dfs(num, p=-1):
        for i in to[num]:
            if p == i:
                continue
            ns[i] += ns[num]
            dfs(i, num)
 
    n, q = map(int, input().split())
 
    to = [[] for _ in range(n)]
 
    for _ in range(n-1):
        a,b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
 
    ns = [0 for _ in range(n)]
    for _ in range(q):
        p, x = map(int, input().split())
        p -= 1
        ns[p] += x
 
    dfs(0)
    print(*ns)
resolve()

Submission status: Time Limit Exceeded

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


def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N)]
    a = []
    b = []
    a_append = a.append
    b_append = b.append
    for i in range(N-1):
        x, y = map(int, input().split())
        a_append(x)
        b_append(y)
    cost = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cost[p-1] += x

    for i in range(N-1):
        link[a[i]-1].append([b[i]-1, cost[i]])
        link[b[i]-1].append([a[i]-1, cost[i]])

    def dfs(v, c, p):
        for nv in link[v]:
            nv0 = nv[0]
            if nv0 != p:
                cost[nv0] += c
                dfs(nv0, cost[nv0], v)

    dfs(0, cost[0], -1)

    print(*cost)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import defaultdict, Counter, deque
from operator import itemgetter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
def inpl(): return list(map(int, input().split()))

def eulartour(G):
    N = len(G)
    depth = [-1]*N
    depth[0] = 0
    eular = []
    L = [0]*N
    R = [0]*N
    i = 0
 
    def dfs(p):
        nonlocal depth, eular, i
        #eular.append(p)
        L[p] = i
        i += 1
        for q in G[p]:
            if depth[q] != -1:
                continue
            depth[q] = depth[p] + 1
            dfs(q)
        #eular.append(p)
        R[p] = i
        i += 1
    
    dfs(0)
    return L, R

class LazySegmentTree:
    
    def __init__(self, N, init_node=None, mode="max"):
        if mode == "sum":
            self.aggfunc = lambda x, y: x+y
            self.lazyaddfunc = lambda x, l, r: x*(r-l)
            self.lazyfunc = lambda x: x//2
        
        elif mode == "max":
            self.aggfunc = lambda x, y: x if x > y else y
            self.lazyaddfunc = lambda x, l, r: x
            self.lazyfunc = lambda x: x
        
        self.size = 2**int.bit_length(N)
        self.node = [0]*(2*self.size-1)
        if not init_node is None:
            for i in range(N):
                self.node[i+self.size-1] = init_node[i]
            for i in range(self.size-2, -1, -1):
                self.node[i] = self.aggfunc(self.node[2*i+1], self.node[2*i+2])
        self.lazy = [0]*(2*self.size-1)

    def eval(self, k, l, r):
        if self.lazy[k]:
            self.node[k] += self.lazy[k]
            if r-l-1:
                self.lazy[2*k+1] += self.lazyfunc(self.lazy[k])
                self.lazy[2*k+2] += self.lazyfunc(self.lazy[k])
            self.lazy[k] = 0

    def add(self, a, b, val):
        Q = [[0, 0, self.size]]
        Q2 = []

        def inner(k, l, r):
            nonlocal Q, Q2
            self.eval(k, l, r)
            if (b <= l) or (r <= a):
                return
            if (a<=l) and (r<=b):
                self.lazy[k] += self.lazyaddfunc(val, l, r)
                self.eval(k, l, r)
            else:
                Q.append([2*k+1, l, (l+r)//2])
                Q.append([2*k+2, (l+r)//2, r])
                Q2.append(k)

        while Q:
            inner(*Q.pop())
        
        while Q2:
            k = Q2.pop()
            self.node[k] = self.aggfunc(self.node[2*k+1], self.node[2*k+2])


    def getagg(self, a, b):
        ix = 0
        Q = [[0, 0, self.size, 0]]
        Q2 = []
        S = [0]

        def inner(k, l, r, i):
            nonlocal ix, Q, Q2, S
            if (b<=l) or (r <= a):
                return 0
            self.eval(k, l, r)
            if (a<=l) and (r<=b):
                S[i] = self.node[k]


            else:
                Q.append([2*k+1, l, (l+r)//2, ix+1])
                Q.append([2*k+2, (l+r)//2, r, ix+2])
                Q2.append([ix, ix+1, ix+2])
                S.extend([0, 0])
                ix += 2
        while Q:
            inner(*Q.pop())

        while Q2:
            x, y, z = Q2.pop()
            S[x] = self.aggfunc(S[y], S[z])
        return S[0]


N, Q = inpl()
G = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = inpl()
    G[a-1].append(b-1)
    G[b-1].append(a-1)

L, R = eulartour(G)

RSQ = LazySegmentTree(2*N)

for _ in range(Q):
    x, d = inpl()
    x -= 1
    RSQ.add(L[x], R[x]+1, d)

for i in range(RSQ.size-1):
    RSQ.eval(i, 0, 2)

for i in range(RSQ.size-1, RSQ.size*2-1):
    RSQ.eval(i, 1, 2)


print(*[RSQ.node[L[i]-1+RSQ.size] for i in range(N)])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import defaultdict, Counter, deque
from operator import itemgetter
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
def inpl(): return list(map(int, input().split()))

def eulartour(G):
    N = len(G)
    depth = [-1]*N
    depth[0] = 0
    eular = []
    L = [0]*N
    R = [0]*N
    i = 0
 
    def dfs(p):
        nonlocal depth, eular, i
        #eular.append(p)
        L[p] = i
        i += 1
        for q in G[p]:
            if depth[q] != -1:
                continue
            depth[q] = depth[p] + 1
            dfs(q)
        #eular.append(p)
        R[p] = i
        i += 1
    
    dfs(0)
    return L, R

def norecursive_eulartour(G):
    N = len(G)
    Q = [0]
    Q2 = []
    size = [0]*N
    size[0] = 1
    L = [0]*N
    R = [0]*N
    i = 0
 
    def inner(p):
        nonlocal Q, Q2, size
        for q in G[p]:
            if size[q]:
                continue
            size[q] = 1
            Q.append(q)
            Q2.append([p, q])

    def add(p, q):
        nonlocal size
        size[p] += size[q]

    while Q:
        inner(Q.pop())
    while Q2:
        add(*Q2.pop())

    searched = [0]*N
    searched[0] = 1
    Q = deque([[0, 0]])

    while Q:
        p, eix = Q.popleft()
        L[p] = eix
        R[p] = eix + 2*size[p] - 1
        for q in G[p]:
            if searched[q]:
                continue
            searched[q] = 1
            Q.append([q, eix+1])
            eix += 2*size[q]
    return L, R


class LazySegmentTree:
    
    def __init__(self, N, init_node=None, mode="max"):
        if mode == "sum":
            self.aggfunc = lambda x, y: x+y
            self.lazyaddfunc = lambda x, l, r: x*(r-l)
            self.lazyfunc = lambda x: x//2
        
        elif mode == "max":
            self.aggfunc = lambda x, y: x if x > y else y
            self.lazyaddfunc = lambda x, l, r: x
            self.lazyfunc = lambda x: x
        
        self.size = 2**int.bit_length(N)
        self.node = [0]*(2*self.size-1)
        if not init_node is None:
            for i in range(N):
                self.node[i+self.size-1] = init_node[i]
            for i in range(self.size-2, -1, -1):
                self.node[i] = self.aggfunc(self.node[2*i+1], self.node[2*i+2])
        self.lazy = [0]*(2*self.size-1)

    def eval(self, k, l, r):
        if self.lazy[k]:
            self.node[k] += self.lazy[k]
            if r-l-1:
                self.lazy[2*k+1] += self.lazyfunc(self.lazy[k])
                self.lazy[2*k+2] += self.lazyfunc(self.lazy[k])
            self.lazy[k] = 0

    def add(self, a, b, val):
        Q = [[0, 0, self.size]]
        Q2 = []

        def inner(k, l, r):
            nonlocal Q, Q2
            self.eval(k, l, r)
            if (b <= l) or (r <= a):
                return
            if (a<=l) and (r<=b):
                self.lazy[k] += self.lazyaddfunc(val, l, r)
                self.eval(k, l, r)
            else:
                Q.append([2*k+1, l, (l+r)//2])
                Q.append([2*k+2, (l+r)//2, r])
                Q2.append(k)

        while Q:
            inner(*Q.pop())
        
        while Q2:
            k = Q2.pop()
            self.node[k] = self.aggfunc(self.node[2*k+1], self.node[2*k+2])


    def getagg(self, a, b):
        ix = 0
        Q = [[0, 0, self.size, 0]]
        Q2 = []
        S = [0]

        def inner(k, l, r, i):
            nonlocal ix, Q, Q2, S
            if (b<=l) or (r <= a):
                return 0
            self.eval(k, l, r)
            if (a<=l) and (r<=b):
                S[i] = self.node[k]


            else:
                Q.append([2*k+1, l, (l+r)//2, ix+1])
                Q.append([2*k+2, (l+r)//2, r, ix+2])
                Q2.append([ix, ix+1, ix+2])
                S.extend([0, 0])
                ix += 2
        while Q:
            inner(*Q.pop())

        while Q2:
            x, y, z = Q2.pop()
            S[x] = self.aggfunc(S[y], S[z])
        return S[0]


N, Q = inpl()
G = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = inpl()
    G[a-1].append(b-1)
    G[b-1].append(a-1)

L, R = norecursive_eulartour(G)

RSQ = LazySegmentTree(2*N)

for _ in range(Q):
    x, d = inpl()
    x -= 1
    RSQ.add(L[x], R[x]+1, d)

for i in range(RSQ.size-1):
    RSQ.eval(i, 0, 2)

for i in range(RSQ.size-1, RSQ.size*2-1):
    RSQ.eval(i, 1, 2)


print(*[RSQ.node[L[i]-1+RSQ.size] for i in range(N)])

Submission status: Time Limit Exceeded

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

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

task = [[] for _ in range(N+1)]
for i in range(Q):
    p, x = map(int, input().split())
    task[p].append(x)

task_sum = [[] for _ in range(N+1)]
for i in range(N+1):
    task_sum[i].append(sum(task[i]))

#print('task_sum:', task_sum)

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

#最初はdfs(1, -1, task_sum[1])

def dfs(v, p, cost):
        
    for nv in edges[v]:
        if nv == p:
            continue
        
        dfs(nv, v, cost+task_sum[nv])

    cnt[v].append(cost)

dfs(1, -1, task_sum[1])


for i in range(1, N+1):
    print(int(sum(cnt[i][0])), end=' ')

Submission status: Time Limit Exceeded

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

def resolve():
    def dfs(num, p=-1):
        for i in to[num]:
            if p == i:
                continue
            ns[i] += ns[num]
            dfs(i, num)

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

    to = [[] for _ in range(n)]

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

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

    dfs(0)
    print(*ns)
resolve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from collections import defaultdict, Counter, deque
from operator import itemgetter
import sys
#input = sys.stdin.readline
sys.setrecursionlimit(10**9)
def inpl(): return list(map(int, input().split()))

def eulartour(G):
    N = len(G)
    depth = [-1]*N
    depth[0] = 0
    eular = []
    L = [0]*N
    R = [0]*N
    i = 0
 
    def dfs(p):
        nonlocal depth, eular, i
        #eular.append(p)
        L[p] = i
        i += 1
        for q in G[p]:
            if depth[q] != -1:
                continue
            depth[q] = depth[p] + 1
            dfs(q)
        #eular.append(p)
        R[p] = i
        i += 1
    
    dfs(0)
    return L, R

class LazySegmentTree:
    
    def __init__(self, N, init_node=None, mode="max"):
        if mode == "sum":
            self.aggfunc = lambda x, y: x+y
            self.lazyaddfunc = lambda x, l, r: x*(r-l)
            self.lazyfunc = lambda x: x//2
        
        elif mode == "max":
            self.aggfunc = lambda x, y: x if x > y else y
            self.lazyaddfunc = lambda x, l, r: x
            self.lazyfunc = lambda x: x
        
        self.size = 2**int.bit_length(N)
        self.node = [0]*(2*self.size-1)
        if not init_node is None:
            for i in range(N):
                self.node[i+self.size-1] = init_node[i]
            for i in range(self.size-2, -1, -1):
                self.node[i] = self.aggfunc(self.node[2*i+1], self.node[2*i+2])
        self.lazy = [0]*(2*self.size-1)

    def eval(self, k, l, r):
        if self.lazy[k]:
            self.node[k] += self.lazy[k]
            if r-l-1:
                self.lazy[2*k+1] += self.lazyfunc(self.lazy[k])
                self.lazy[2*k+2] += self.lazyfunc(self.lazy[k])
            self.lazy[k] = 0

    def add(self, a, b, val):
        Q = [[0, 0, self.size]]
        Q2 = []

        def inner(k, l, r):
            nonlocal Q, Q2
            self.eval(k, l, r)
            if (b <= l) or (r <= a):
                return
            if (a<=l) and (r<=b):
                self.lazy[k] += self.lazyaddfunc(val, l, r)
                self.eval(k, l, r)
            else:
                Q.append([2*k+1, l, (l+r)//2])
                Q.append([2*k+2, (l+r)//2, r])
                Q2.append(k)

        while Q:
            inner(*Q.pop())
        
        while Q2:
            k = Q2.pop()
            self.node[k] = self.aggfunc(self.node[2*k+1], self.node[2*k+2])


    def getagg(self, a, b):
        ix = 0
        Q = [[0, 0, self.size, 0]]
        Q2 = []
        S = [0]

        def inner(k, l, r, i):
            nonlocal ix, Q, Q2, S
            if (b<=l) or (r <= a):
                return 0
            self.eval(k, l, r)
            if (a<=l) and (r<=b):
                S[i] = self.node[k]


            else:
                Q.append([2*k+1, l, (l+r)//2, ix+1])
                Q.append([2*k+2, (l+r)//2, r, ix+2])
                Q2.append([ix, ix+1, ix+2])
                S.extend([0, 0])
                ix += 2
        while Q:
            inner(*Q.pop())

        while Q2:
            x, y, z = Q2.pop()
            S[x] = self.aggfunc(S[y], S[z])
        return S[0]


N, Q = inpl()
G = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = inpl()
    G[a-1].append(b-1)
    G[b-1].append(a-1)

L, R = eulartour(G)

RSQ = LazySegmentTree(2*N)

for _ in range(Q):
    x, d = inpl()
    x -= 1
    RSQ.add(L[x], R[x]+1, d)

for i in range(RSQ.size-1):
    RSQ.eval(i, 0, 2)

for i in range(RSQ.size-1, RSQ.size*2-1):
    RSQ.eval(i, 1, 2)


print(*[RSQ.node[L[i]-1+RSQ.size] for i in range(N)])

Submission status: Time Limit Exceeded

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

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)]
 
g = [[] for _ in range(N+1)]
for a,b in AB:
    g[a].append(b)
    g[b].append(a)
 
cnt = [0] * (N+1)
for p,x in PX:
    cnt[p] += x

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

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

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
ans = [0]*N
for _ in range(N-1):
    aa, bb = map(int, input().split())
    tree[aa-1].append(bb - 1)
    tree[bb-1].append(aa - 1)


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

def DFS(x, pre):
    global ans
    for i in tree[x]:
        if i==pre:
            continue

        ans[i] += ans[x]
        DFS(i, x)

    return

DFS(0, -1)
for x in ans:
    print(x)

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+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

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

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
def search(tree, p, callback):
    if tree[0] == p:
        callback(tree)
        return True         # 見つかったら加算に入って検索を停止
    else:
        for sub in tree[2]:
            if search(sub, p, callback):
                break

def add(tree, x):
    tree[1] += x
    for sub in tree[2]:
        add(sub, x)

def add_once(tree, x):
    tree[1] += x

def add_and_propagate(tree, x=0):
    tree[1] += x
    for sub in tree[2]:
        add_and_propagate(sub, tree[1])

    
def get_nodes(tree):
    yield tree[:2]
    for sub in tree[2]:
        yield from get_nodes(sub)

def add_children(tree, p, qs):
    def callback(tree):
        tree[2].extend([[q, 0, []] for q in qs])
    return search(tree, p, callback)

def find_next(p, edges):
    to_remove = set()
    for e in edges:
        if p in e:
            to_remove.add(e)
            yield e[0] if p == e[1] else e[1]
    edges.difference_update(to_remove)


def output(tree):
    print(*(c for n, c in sorted(get_nodes(tree))))

def readlines(N):
    for _ in range(N):
        yield tuple(map(int, input().split()))

N, Q = next(readlines(1))
edges = set(readlines(N-1))
tree = [1, 0, []]
frontier = [1]
for f in frontier:
    nexts = list(find_next(f, edges))
    frontier.extend(nexts)
    add_children(tree, f, nexts)

for p, x in readlines(Q):
    search(tree, p, lambda t: add_once(t, x))
add_and_propagate(tree)

output(tree)

Submission status: Time Limit Exceeded

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

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

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

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

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

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

Submission status: Time Limit Exceeded

Solution code:
def search(tree, p, callback):
    if tree[0] == p:
        callback(tree)
        return True         # 見つかったら加算に入って検索を停止
    else:
        for sub in tree[2]:
            if search(sub, p, callback):
                break

def add(tree, x):
    tree[1] += x
    for sub in tree[2]:
        add(sub, x)
    
def get_nodes(tree):
    yield tree[:2]
    for sub in tree[2]:
        yield from get_nodes(sub)

def add_children(tree, p, qs):
    def callback(tree):
        tree[2].extend([[q, 0, []] for q in qs])
    return search(tree, p, callback)

def find_next(p, edges):
    to_remove = set()
    for e in edges:
        if p in e:
            to_remove.add(e)
            yield e[0] if p == e[1] else e[1]
    edges.difference_update(to_remove)


def output(tree):
    print(*(c for n, c in sorted(get_nodes(tree))))

def readlines(N):
    for _ in range(N):
        yield tuple(map(int, input().split()))

N, Q = next(readlines(1))
edges = set(readlines(N-1))
tree = [1, 0, []]
frontier = [1]
for f in frontier:
    nexts = list(find_next(f, edges))
    frontier.extend(nexts)
    add_children(tree, f, nexts)

for p, x in readlines(Q):
    search(tree, p, lambda t: add(t, x))

output(tree)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10**6)
#es = [[] for i in range(N)]
es = {}
for i in range(N-1):
    a,b = map(int, input().split())
    a,b = a-1, b-1
    if a in es:
        es[a].append(b)
    else:
        es[a] = [b]
    if b in es:
        es[b].append(a)
    else:
        es[b] = [a]


point = [0] * N

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

ans = [0] * N
ans[0] = point[0] # 一番上の根なのでこれだけ
visited = [False] * N
visit_cnt = 1
from collections import deque
nexts = deque([0])
while len(nexts) >= 1:
    now = nexts.popleft()
    visited[now] = True
    if now in es:
        for next in es[now]:
            if visited[next] == True:
                continue
            nexts.append(next)
            ans[next] = ans[now] + point[next]


print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import queue

N, Q = map(int, input().split())
adjacent = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adjacent[a].append(b)
    adjacent[b].append(a)
ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x

q = queue.Queue()
q.put((0, -1))
while not q.empty():
    u, p = q.get()
    for v in adjacent[u]:
        if v == p:
            continue
        ans[v] += ans[u]
        q.put((v, u))
print(' '.join([str(ans[i]) for i in range(N)]))

Submission status: Time Limit Exceeded

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

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

def main():
    N, Q = map(int, input().split())
    tree = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)
    ans = [0] * N
    for i in range(Q):
        p, x = map(int, input().split())
        p -= 1
        ans[p] += x

    dfs(0, -1, tree, ans)

    print(*ans)

main()

Submission status: Time Limit Exceeded

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

def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N)]
    a = []
    b = []
    a_append = a.append
    b_append = b.append
    for i in range(N-1):
        x, y = map(int, input().split())
        a_append(x)
        b_append(y)
    cost = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cost[p-1] += x

    for i in range(N-1):
        link[a[i]-1].append([b[i]-1, cost[i]])
        link[b[i]-1].append([a[i]-1, cost[i]])

    def dfs(v, c, p):
        for nv in link[v]:
            if nv[0] == p:
                continue
            cost[nv[0]] = c + cost[nv[0]]
            dfs(nv[0], cost[nv[0]], v)
        return

    dfs(0, cost[0], -1)

    print(*cost)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
dfs(0, -1)
print(*ans)

Submission status: Time Limit Exceeded

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

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

N, Q = map(int, input().split())
tree = [[] for _ in range(N)]
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)
ans = [0] * N
for i in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
dfs(0, -1)
print(*ans)

Submission status: Time Limit Exceeded

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

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

def main():
    N, Q = map(int, input().split())
    tree = [[] for _ in range(N)]

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

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

    dfs(0, -1, tree, ans)

    print(*ans)

main()

Submission status: Time Limit Exceeded

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

def main():
    N, Q = map(int, input().split())
    link = [[] for _ in range(N)]
    a = [None] * (N-1)
    b = [None] * (N-1)
    for i in range(N-1):
        a[i], b[i] = map(int, input().split())

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

    for i in range(N-1):
        link[a[i]-1].append([b[i]-1, cost[i]])
        link[b[i]-1].append([a[i]-1, cost[i]])

    def dfs(v, c, p):
        for nv in link[v]:
            if nv[0] == p:
                continue
            cost[nv[0]] = c + cost[nv[0]]
            dfs(nv[0], cost[nv[0]], v)
        return

    dfs(0, cost[0], -1)

    print(*cost)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque


def main():
    N, Q = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    cnt = [0] * N
    for _ in range(Q):
        p, x = map(int, input().split())
        cnt[p-1] += x
    ans = [0] * N
    q = deque([(0, 0, -1)])
    while len(q):
        cur, total, prev = q.popleft()
        total += cnt[cur]
        ans[cur] = total
        for a in adj[cur]:
            if a == prev:
                continue
            q.append((a, total, cur))
    print(*ans)


if __name__ == "__main__":
    main()