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: Runtime Error

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):
    if v != 1:
        counter[v] += counter.get(parent)
    for v_next in g.get_adj(v):
        dfs(v_next, v)


g = Graph(connections, directed=True)
# print(g)

keys = [v for v in range(1, N + 1)]
values = [False for _ in range(N)]
seen = dict(zip(keys, values))
root = 1
dfs(root, None)

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

Submission status: Runtime Error

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)

g = Graph(connections, directed=True)
# print(g)

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(g, v, parent):
    if v != 1:
        counter[v] += counter.get(parent)
    for v_next in g.get_adj(v):
        dfs(g, v_next, v)


keys = [v for v in range(1, N + 1)]
values = [False for _ in range(N)]
seen = dict(zip(keys, values))
root = 1
dfs(g, root, None)

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

Submission status: Runtime Error

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

import sys
from collections import defaultdict
sys.setrecursionlimit(20000)


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)

g = Graph(connections, directed=True)
# print(g)

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


def dfs(g, p, x):
    counter[p] += x
    for p_next in g.get_adj(p):
        dfs(g, p_next, x)


for p, x in query:
    dfs(g, p, x)

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

Submission status: Runtime Error

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)

g = Graph(connections, directed=True)
# print(g)

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


def dfs(g, p, x):
    counter[p] += x
    for p_next in g.get_adj(p):
        dfs(g, p_next, x)


for p, x in query:
    dfs(g, p, x)

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

Submission status: Runtime Error

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 remove(self, v):
        """ Remove all references to node v """

        for _, cxns in self._graph.items():
            try:
                cxns.remove(v)
            except KeyError:
                pass
        try:
            del self._graph[v]
        except KeyError:
            pass

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

    def is_connected(self, u, v):
        """ Is node u directly connected to node v """

        return u in self._graph and v in self._graph[u]

    def find_path(self, src, dst, path=[]):
        """ Find any path from src node to dst node (may not be shortest) """

        path = path + [src]
        if src == dst:
            return path
        if src not in self._graph:
            return None
        for src_next in self._graph[src]:
            if src_next not in path:
                new_path = self.find_path(src_next, dst, path)
                if new_path:
                    return new_path
        return None

    def find_all_paths(self, src, dst, path=[]):
        """ Find all paths from src node to dst node """
        path = path + [src]
        if src == dst:
            return path
        if src not in self._graph:
            return None
        paths = []
        for src_next in self._graph[src]:
            if src_next not in path:
                new_path = self.find_all_paths(src_next, dst, path)
                if new_path:
                    paths.append(new_path)
        if len(paths) > 0:
            return paths
        return None

    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)

g = Graph(connections, directed=True)
# print(g)

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

def dfs(g, p, x):
    counter[p] += x
    for p_next in g.get_adj(p):
        dfs(g, p_next, x)


for p, x in query:
    dfs(g, p, x)

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

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
G = dict([[i, []] for i in range(N)])
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
C = [0] * N
visited = [False] * N
# print(G)


def dfs(p, x):
    if visited[p]:
        return

    C[p] += x

    for v in G[p]:
        dfs(v, x)


for _ in range(Q):
    p, x = map(int, input().split())
    visited = [False] * N
    dfs(p-1, x)

print(*C)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

class Ki(object):
    def __init__(self, N):
        self.node = [-1] * N
        self.score = [0] * N
        self.child = [[] for _ in range(N)]

    def root(self, x):
        if self.node[x] < 0:
            return x
        else:
            return self.root(self.node[x])

    def connect(self, x, y):
        a = self.root(x)
        b = self.root(y)

        # 問題文から、a・bのいずれかは0になる
        # xを根に近い方として扱う
        if a > b:
            x, y = y, x

        self.node[y] = x
        self.child[x].append(y)

        return

    def add_score(self, x, point):
        self.score[x] += point

        for c in self.child[x]:
            self.add_score(c, point)

        return


def main():
    N, Q = map(int, input().split())
    tree = Ki(N)
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1,input().split())
        tree.connect(a, b)

    for _ in range(Q):
        p, x = map(int, input().split())
        p -= 1
        tree.add_score(p, x)


    print(*tree.score)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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 + ans[i] + ' '
print(ans_str)

Submission status: Runtime Error

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

import sys
sys.setrecursionlimit(4000)

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: Runtime Error

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

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: Runtime Error

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

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)

print(b)

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: Runtime Error

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

graph = [set([]) for _ in range(N+1)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]
check[1] = True
#check[i]:i番目の頂点を発見した
#check[i] == True and i in graph[j]ならiはjの親

for p,x in PX:
    counter[p] += x

def cal(graph,counter,edge,parent):
    for e in (graph[edge]-parent):
        counter[e] += counter[edge]
        cal(graph,counter,e,set([edge]))
    check[edge] = True

cal(graph,counter,1,set())

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

Submission status: Runtime Error

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

graph = [set([]) for _ in range(N+1)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]
check[1] = True
#check[i]:i番目の頂点を発見した
#check[i] == True and i in graph[j]ならiはjの親

for p,x in PX:
    counter[p] += x

def cal(graph,counter,edge,parent):
    for e in (graph[edge]-parent):
        counter[e] += counter[edge]
    check[edge] = True
    for e in (graph[edge]-parent):
        cal(graph,counter,e,set([edge]))

cal(graph,counter,1,set())

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

Submission status: Runtime Error

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

graph = [set([]) for _ in range(N+1)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]
check[1] = True
#check[i]:i番目の頂点を発見した
#check[i] == True and i in graph[j]ならiはjの親

for p,x in PX:
    counter[p] += x

def cal(graph,counter,edge):
    for e in graph[edge]:
        if not check[e]:
            counter[e] += counter[edge]
            check[edge] = True
            cal(graph,counter,e)

cal(graph,counter,1)

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

Submission status: Runtime Error

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

graph = [set([]) for _ in range(N+1)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]
check[1] = True
#check[i]:i番目の頂点を発見した
#check[i] == True and i in graph[j]ならiはjの親

for p,x in PX:
    counter[p] += x

def cal(graph,counter,edge):
    for e in graph[edge]:
        if not check[e]:
            counter[e] += counter[edge]
            check[e] = True
            cal(graph,counter,e)

cal(graph,counter,1)

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

Submission status: Runtime Error

Solution code:

N, Q=map(int, input().split())
value=np.array([0]*N)
#各ノードの下につくノード

oya=[-1]*N
for i in range(N-1):
  a,b=map(int, input().split())
  
  oya[b-1]=a-1
  
#adds=[0]*N



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

for i in range(N):
  if i >0:
    value[i]+=value[oya[i]]
    ans=value[i]
  else:
    ans=value[i]
  print(ans, end=" ")

Submission status: Runtime Error

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: Runtime Error

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番目の頂点のカウンター

for i in range(N-1):
    children[AB[i][0]-1].add(AB[i][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()

Submission status: Runtime Error

Solution code:
N, Q=map(int, input().split())
value=[0]*N
#各ノードの下につくノード
road=[[] for _ in range(N)]
for i in range(N-1):
  a,b=map(int, input().split())
  road[a-1].append(b-1)
  
adds=[0]*N
for i in range(Q):
  p,x=map(int, input().split())
  adds[p-1]+=x
  
#自身のノード番号 足していく
#a: add[なんとか]
def dfs(a,  i):
  value[i]+=a
  L=road[i]
  for l in L:
    dfs(a,l)
for i in range(N):
  dfs(adds[i], i)


for v in value:
  print(v, end=" ")

Submission status: Runtime Error

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 = {}
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: Runtime Error

Solution code:
_f = lambda x: int(x) - 1
N, Q = map(int, input().split())
T = [[] for i in range(N)]
for i in range(N-1):
  a, b = map(_f, input().split())
  T[a].append(b)
  T[b].append(a)

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

def dfs(v, p):
  for u in T[v]:
    if u == p: continue
    C[u] = C[v]
    dfs(u, v)
dfs(0, -1)
print(' '.join(map(str, C)))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
C = [0 for i in range(N)]
T = [[] for i in range(N)]
_f = lambda x: int(x) - 1
def add_value(i, f):
  for j in T[i]:
    if j == f: continue
    C[j] += C[i]
    add_value(j, i)
for i in range(N-1):
  a, b = map(_f, input().split())
  T[a].append(b)
  T[b].append(a)
for j in range(Q):
  p, x = map(int, input().split())
  C[p-1] += x
add_value(0, -1)
print(' '.join(map(str, C)))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
counters = [0 for i in range(N)]
tree = [[] for i in range(N)]
_f = lambda x: int(x) - 1
def add_value(i, v):
  for j in tree[i]:
    counters[j] += v
    add_value(j, counters[j])
for i in range(N-1):
  a, b = map(_f, input().split())
  tree[a].append(b)
for i in range(Q):
  p, x = map(int, input().split())
  counters[p-1] += x
add_value(0, counters[0])
print(' '.join(map(str, counters)))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
counters = [0 for i in range(N)]
tree = [[] for i in range(N)]
_f = lambda x: int(x) - 1
def add_value(i, v):
  counters[i] += v
  for j in tree[i]:
    add_value(j, v)
for i in range(N-1):
  a, b = map(_f, input().split())
  tree[a].append(b)
for i in range(Q):
  p, x = map(int, input().split())
  add_value(p-1, x)
print(' '.join(map(str, counters)))

Submission status: Runtime Error

Solution code:
class Node():
  def __init__(self, n):
    self.n = n
    self.counter = 0
    self.to = []
  def add_values(self, v):
    self.counter += v
    for c in self.to:
      c.add_values(v)
N, Q = map(int, input().split())
tree = [None for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if tree[a] is None:
    tree[a] = Node(a)
  if tree[b] is None:
    tree[b] = Node(b)
  tree[a].to.append(tree[b])
for i in range(Q):
  p, x = map(int, input().split())
  p -= 1
  tree[p].add_values(x)
print(' '.join(map(lambda x: str(x.counter), tree)))

Submission status: Runtime Error

Solution code:
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: Runtime Error

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

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: Runtime Error

Solution code:
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:
  if parent[a-1]<0:
    parent[a-1] = b-1
    child[b-1] = child[b-1] + [a-1]
  else:
    parent[b-1] = a-1
    child[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: Runtime Error

Solution code:
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

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

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: Runtime Error

Solution code:
#138_D
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: Runtime Error

Solution code:
#138_D
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
    
used = [True for _ in range(n)]
def dfs(s):
    used[s] = False
    for idx in edges[s]:
        if used[idx]:
            cnt[idx] += cnt[s]
            dfs(idx)
dfs(0)          
print(*cnt)

Submission status: Runtime Error

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

#mat = [[0]*N for j in range(N)]
mat = [0]*(N**2)
cnt = [0]*N
for i in range(N-1):
  a,b = map(int, input().split())
  #mat[a-1][b-1] = 1
  mat[(a-1)*N + b - 1 ] = 1
for i in range(Q):
  p,x = map(int, input().split())
  cnt[p-1] += x
      
for i in range(N):
    #for j, v in enumerate(mat[i]):
    #if v == 1:
  for j in range(N):
    if mat[i*N+j] == 1:
      cnt[j] += cnt[i]

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

Submission status: Runtime Error

Solution code:
N,Q = (int(x) for x in input().split())

mat = [[0]＊N for j in range(N)]

cnt = [0]*N
for i in range(N-1):
  a,b = (int(x) for x in input().split())
  mat[a-1][b-1] = 1

for i in range(Q):
  p,x = (int(x) for x in input().split())
  cnt[p-1] += x
      
for i in range(N):
  for j, v in enumerate(mat[i]):
    if v == 1:
      cnt[j] += cnt[i]

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
D - Ki
https://atcoder.jp/contests/abc138/tasks/abc138_d

"""
import sys


from functools import lru_cache
from collections import deque

def solve(N, Q):
    @lru_cache(maxsize=None)
    def calc_score(n):
        if n == 1 or nodes[n][3]:
            return nodes[n][0]
        res = calc_score(nodes[n][2]) + nodes[n][0]
        nodes[n][3] = True
        return res

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

    visited = set()
    q = deque([1])
    while q:
        n = q.popleft()
        if n not in visited:
            visited.add(n)
            for m in (e for e in edges[n] if e not in visited):
                q.appendleft(m)
                nodes[m][2] = n
    ans = [calc_score(i) for i in range(1, N+1)]
    return ans


def main(args):
    N, Q = map(int, input().split())
    ans = solve(N, Q)
    print(*ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(20000)N, Q = list(map(int, input().split()))

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

operations = []
for _ in range(Q):
    operations.append(list(map(int, input().split())))

# print(points)
# print(operations)


def dfs(points, counters, i, count):
    counters[i - 1] += count
    for next_point in points[i - 1]:
        dfs(points, counters, next_point, count)


for operation in operations:
    dfs(points, counters, operation[0], operation[1])
# print(counters)

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