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:
def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    tree = make_tree(n, n_data)
    t_index = make_index(n, tree)

    score = [0] * n

    for qq in q_data:
        index = qq[0]
        #add_score(tree, score, qq, n_data, index)
        s_index = t_index[index - 1]
        for i in s_index:
            score[i] += qq[1]

    score = [str(s) for s in score]
    s = " ".join(score)

    return s


def add_score(tree, score, qq, n_data, index):
    score[index - 1] += qq[1]
    next_index = tree[index -1]
    for n_i in next_index:
        add_score(tree, score, qq, n_data, n_i)


def make_tree(n, n_data):
    r = {}
    for i in range(n):
        r[i] = []
    for n in n_data:
        k = n[0] - 1
        if k in r.keys():
            r[k].append(n[1])
        else:
            r[k] = [n[1]]
    return r


def make_index(n, tree):
    index = {}
    r0 = [0] * n
    for i in range(n):
        r0[i] = i
    index[0] = r0

    for i in range(1, n):
        r = []
        add_index(tree, i, r)
        index[i] = r

    return index


def add_index(tree, index, r):
    r.append(index)
    next_index = tree[index]
    for n_i in next_index:
        add_index(tree, n_i - 1, r)


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Runtime Error

Solution code:
def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    tree = make_tree(n, n_data)
    t_index = make_index(n, tree)

    score = [0] * n

    for qq in q_data:
        index = qq[0]
        #add_score(tree, score, qq, n_data, index)
        s_index = t_index[index - 1]
        for i in s_index:
            score[i] += qq[1]

    score = [str(s) for s in score]
    s = " ".join(score)

    return s


def add_score(tree, score, qq, n_data, index):
    score[index - 1] += qq[1]
    next_index = tree[index -1]
    for n_i in next_index:
        add_score(tree, score, qq, n_data, n_i)


def make_tree(n, n_data):
    r = {}
    for i in range(n):
        r[i] = []
    for n in n_data:
        k = n[0] - 1
        if k in r.keys():
            r[k].append(n[1])
        else:
            r[k] = [n[1]]
    return r


def make_index(n, tree):
    index = {}
    r0 = [0] * n
    for i in range(n):
        r0[i] = i
    index[0] = r0

    for i in range(1, n):
        r = []
        add_index(tree, i, r)
        index[i] = r

    return index


def add_index(tree, index, r):
    r.append(index)
    next_index = tree[index]
    for n_i in next_index:
        add_index(tree, n_i - 1, r)


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            input_ki.append(input1)
        except EOFError:
            break
    get_answer(input_ki)

Submission status: Runtime Error

Solution code:
def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    tree = make_tree(n, n_data)

    score = [0] * n

    for qq in q_data:
        index = qq[0]
        add_score(tree, score, qq, n_data, index)

    #score = [str(s) for s in score]
    #s = " ".join(score)
    for s in score:
        print(s, end="")
        print(" ", end="")

    return None


def add_score(tree, score, qq, n_data, index):
    score[index - 1] += qq[1]
    next_index = tree[index -1]
    for n_i in next_index:
        add_score(tree, score, qq, n_data, n_i)


def make_tree(n, n_data):
    r = {}
    for i in range(n):
        r[i] = []
    for n in n_data:
        k = n[0] - 1
        if k in r.keys():
            r[k].append(n[1])
        else:
            r[k] = [n[1]]
    return r


def make_index(n, tree):
    index = {}
    r0 = [0] * n
    for i in range(n):
        r0[i] = i
    index[0] = r0

    for i in range(1, n):
        r = []
        add_index(tree, i, r)
        index[i] = r

    return index


def add_index(tree, index, r):
    r.append(index)
    next_index = tree[index]
    for n_i in next_index:
        add_index(tree, n_i - 1, r)


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            input_ki.append(input1)
        except EOFError:
            break
    get_answer(input_ki)

Submission status: Runtime Error

Solution code:
def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    tree = make_tree(n, n_data)

    score = [0] * n

    for qq in q_data:
        index = qq[0]
        add_score(tree, score, qq, n_data, index)

    score = [str(s) for s in score]
    s = " ".join(score)

    return s


def add_score(tree, score, qq, n_data, index):
    score[index - 1] += qq[1]
    next_index = tree[index -1]
    for n_i in next_index:
        add_score(tree, score, qq, n_data, n_i)


def make_tree(n, n_data):
    r = {}
    for i in range(n):
        r[i] = []
    for n in n_data:
        k = n[0] - 1
        if k in r.keys():
            r[k].append(n[1])
        else:
            r[k] = [n[1]]
    return r


def make_index(n, tree):
    index = {}
    r0 = [0] * n
    for i in range(n):
        r0[i] = i
    index[0] = r0

    for i in range(1, n):
        r = []
        add_index(tree, i, r)
        index[i] = r

    return index


def add_index(tree, index, r):
    r.append(index)
    next_index = tree[index]
    for n_i in next_index:
        add_index(tree, n_i - 1, r)


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            if len(input1) == 0:
                break;
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Runtime Error

Solution code:
def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    tree = make_tree(n, n_data)

    score = [0] * n

    for qq in q_data:
        index = qq[0]
        add_score(tree, score, qq, n_data, index)

    score = [str(s) for s in score]
    s = " ".join(score)

    return s


def add_score(tree, score, qq, n_data, index):
    score[index - 1] += qq[1]
    next_index = tree[index -1]
    for n_i in next_index:
        add_score(tree, score, qq, n_data, n_i)


def make_tree(n, n_data):
    r = {}
    for i in range(n):
        r[i] = []
    for n in n_data:
        k = n[0] - 1
        if k in r.keys():
            r[k].append(n[1])
        else:
            r[k] = [n[1]]
    return r


def make_index(n, tree):
    index = {}
    r0 = [0] * n
    for i in range(n):
        r0[i] = i
    index[0] = r0

    for i in range(1, n):
        r = []
        add_index(tree, i, r)
        index[i] = r

    return index


def add_index(tree, index, r):
    r.append(index)
    next_index = tree[index]
    for n_i in next_index:
        add_index(tree, n_i - 1, r)


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Runtime Error

Solution code:
def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    tree = make_tree(n, n_data)

    score = [0] * n

    for qq in q_data:
        index = qq[0]
        add_score(tree, score, qq, n_data, index)

    score = [str(s) for s in score]
    s = " ".join(score)

    return s


def add_score(tree, score, qq, n_data, index):
    score[index - 1] += qq[1]
    next_index = tree[index -1]
    for n_i in next_index:
        add_score(tree, score, qq, n_data, n_i)


def make_tree(n, n_data):
    r = {}
    for i in range(n):
        r[i] = []
    for n in n_data:
        k = n[0] - 1
        if k in r.keys():
            r[k].append(n[1])
        else:
            r[k] = [n[1]]
    return r


def make_index(n, tree):
    index = {}
    for i in range(n):
        r = []
        add_index(tree, i, r)
        index[i] = r

    return index


def add_index(tree, index, r):
    r.append(index)
    next_index = tree[index]
    for n_i in next_index:
        add_index(tree, n_i - 1, r)


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Runtime Error

Solution code:
def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]
    tree = make_tree(n, n_data)

    score = [0] * n

    for qq in q_data:
        index = qq[0]
        add_score(tree, score, qq, n_data, index)

    score = [str(s) for s in score]
    s = " ".join(score)

    return s


def add_score(tree, score, qq, n_data, index):
    score[index - 1] += qq[1]
    next_index = tree[index -1]
    for n_i in next_index:
        add_score(tree, score, qq, n_data, n_i)


def make_tree(n, n_data):
    r = {}
    for i in range(n):
        r[i] = []


    for n in n_data:
        k = n[0] - 1
        if k in r.keys():
            r[k].append(n[1])
        else:
            r[k] = [n[1]]
    return r


if __name__ == "__main__":
    input_ki = []
    while True:
        try:
            input1 = input()
            if not input1:
                break;
            input_ki.append(input1)
        except EOFError:
            break
    print(get_answer(input_ki))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)

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

class Node:
    def __init__(self):
        self.children = []
        self.point = 0
    
    def get_children(self):
        if not self.children:
            return [self]
        ret = [self]
        for child in self.children:
            c = child.get_children()
            ret.extend(c)
        return ret

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

queries = []
for i in range(q):
    p, x = map(int, input().split(' '))
    queries.append((p, x))

for query in queries:
    ps = nodes[query[0]-1].get_children()
    for p in ps:
        p.point += query[1]

print(*[str(n.point) for n in nodes])

Submission status: Runtime Error

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

class Node:
    def __init__(self):
        self.children = set()
        self.point = 0
    
    def get_children(self):
        if not self.children:
            return set([self])
        ret = set([self])
        for child in self.children:
            c = child.get_children()
            ret = ret.union(c)
        return ret

nodes = [Node() for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split(' '))
    nodes[a-1].children.add(nodes[b-1])

queries = []
for i in range(q):
    p, x = map(int, input().split(' '))
    queries.append((p, x))

for query in queries:
    ps = nodes[query[0]-1].get_children()
    for p in ps:
        p.point += query[1]

print(*[str(n.point) for n in nodes])

Submission status: Runtime Error

Solution code:
def get_answer(ki):
    n = int(ki[0].split(" ")[0])
    q = int(ki[0].split(" ")[1])
    n_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[1:-q]]]
    q_data = [[int(k[0]), int(k[1])] for k in [k.split(" ") for k in ki[-q:]]]

    score = [0] * n

    for qq in q_data:
        index = qq[0]
        score[index - 1] += qq[1]
        add_score(score, qq, n_data, index)

    score = [str(s) for s in score]
    s = " ".join(score)

    return s


def add_score(score, qq, n_data, index):
    for nn in n_data:
        if nn[0] == index:
            score[nn[1] - 1] += qq[1]
            add_score(score, qq, n_data, nn[1])


if __name__ == "__main__":
    input_ki = []
    while True:
        input1 = input()
        if not input1:
            break;
        input_ki.append(input1)
    print(get_answer(input_ki))

Submission status: Runtime Error

Solution code:
#D

def dig(n, scn, count):
    global sc
    #global checed

    if scn == -1:
        scn = 0
    else:
        return
    
    scn = count + c[n]
    sc[n] = scn
    #checked.append(n)
    
    for i in E[n]:
        #if not(i in checked):
        dig(i, sc[i], scn)

        


#XXX=[int(x) for x in Input.split()]

n,q = (int(x) for x in input().split())
#n,q = XXX[0:2]

E = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = (int(x) for x in input().split())
    #a,b = XXX[i*2+2:i*2+4]
    #A.append(a)
    #B.append(b)
    E[a].append(b)
    E[b].append(a)

P = []
X = []
for i in range(q):
    p,x = (int(x) for x in input().split())
    #p,x = XXX[i*2+n*2:i*2+n*2+2]
    P.append(p)
    X.append(x)

c = [0]*(n+1)
for i in range(len(P)):
    c[P[i]]+=X[i]

sc = [-1]*(n+1)
#sc = [0]*(n+1)
#checked = []

dig(1,-1,0)
result = map(str, sc[1:])
print(" ".join(result))

Submission status: Runtime Error

Solution code:
#D

def dig(n, count):
    global sc
    global checed

    #if sc[n] == -1:
    #    sc[n] = 0
    #else:
    #    return
    
    sc[n] = count + c[n]
    checked.append(n)
    
    for i in E[n]:
        if not(i in checked):
            dig(i, sc[n])

        


#XXX=[int(x) for x in Input.split()]

n,q = (int(x) for x in input().split())
#n,q = XXX[0:2]

E = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = (int(x) for x in input().split())
    #a,b = XXX[i*2+2:i*2+4]
    #A.append(a)
    #B.append(b)
    E[a].append(b)
    E[b].append(a)

P = []
X = []
for i in range(q):
    p,x = (int(x) for x in input().split())
    #p,x = XXX[i*2+n*2:i*2+n*2+2]
    P.append(p)
    X.append(x)

c = [0]*(n+1)
for i in range(len(P)):
    c[P[i]]+=X[i]

#sc = [-1]*(n+1)
sc = [0]*(n+1)
checked = []

dig(1,0)
result = map(str, sc[1:])
print(" ".join(result))

Submission status: Runtime Error

Solution code:
#D

def dig(n, count):
    global sc

    if sc[n] == -1:
        sc[n] = 0
    else:
        return
    
    sc[n] = count + c[n]
    
    for i in E[n]:
        dig(i, sc[n])

        


#XXX=[int(x) for x in Input.split()]

n,q = (int(x) for x in input().split())
#n,q = XXX[0:2]

#A = []
#B = []
E = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = (int(x) for x in input().split())
    #a,b = XXX[i*2+2:i*2+4]
    #A.append(a)
    #B.append(b)
    E[a].append(b)
    E[b].append(a)

P = []
X = []
for i in range(q):
    p,x = (int(x) for x in input().split())
    #p,x = XXX[i*2+n*2:i*2+n*2+2]
    P.append(p)
    X.append(x)

c = [0]*(n+1)
for i in range(len(P)):
    c[P[i]]+=X[i]

#print(c)

sc = [-1]*(n+1)

dig(1,0)
result = map(str, sc[1:])
print(" ".join(result))

Submission status: Runtime Error

Solution code:
def run_count(counter, edges, p, x):
    counter[p] += x
    p_list = edges[p]
    if p_list is None:
        return counter

    for _p in p_list:
        counter = run_count(counter, edges, _p, x)

    return counter


N, Q = [int(i) for i in input().rstrip().split()]

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

p = [0] * Q
x = [0] * Q
for i in range(Q):
    p[i], x[i] = [int(j) for j in input().rstrip().split()]

edges = {}
for i in range(N):
    edges[i + 1] = []

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

counter = {}
for i in range(N):
    counter[i + 1] = 0

for i in range(Q):
    counter = run_count(counter, edges, p[i], x[i])

res = ""
for i in range(N):
    res += str(counter[i + 1])
    res += " "
res.rstrip(" ")

print(res)

Submission status: Runtime Error

Solution code:
class Node:

    def __init__(self, name):
        self.name = name
        self.linked = []
        self.parent = None
        self.children = []
        self.progeny = None
        self.count = 0
    
    def __str__(self):
        return "{}({}):{}".format(self.name, self.count, len(self.children))
        
    def add_linked(self, node):
        self.linked.append(node)

    def set_parent(self, parent):
        self.parent = parent
        
    def add_child(self, child):
        self.children.append(child)
        child.set_parent(self)
        
    def num_child(self):
        return len(self.children)
    
    def add_count(self, count):
        self.count += count
    
    def get_progeny(self):
        if self.progeny==None:
            self.progeny = []
            self.progeny.extend(self.children)
            for child in self.children:
                self.progeny.extend(child.get_progeny())
        return self.progeny


def print_tree(node, tab):
    print("{}{}({})".format("\t"*tab, node.name, node.count))
    num = node.num_child()
    if num != 0:
        for i in range(num):
            print_tree(node.children[i], tab+1)

def make_tree(root_node):
    linked_nodes = root_node.linked
    try:
        linked_nodes.remove(root_node.parent)
    except ValueError:
        pass
    for node in linked_nodes:
        root_node.add_child(node)
        make_tree(node)

if __name__ == "__main__":
    n, q = map(int, input().split())
    nodes = [0] + [Node(i) for i in range(1,n+1)]
    for i in range(1,n):
        a, b = map(int, input().split())
        nodes[a].add_linked(nodes[b])
        nodes[b].add_linked(nodes[a])

    make_tree(nodes[1])

    for _ in range(q):
        p, x = map(int, input().split())
        nodes[p].add_count(x)
        for node in nodes[p].get_progeny():
            node.add_count(x)
    
    print(" ".join([str(nodes[i].count) for i in range(1,n+1)]))

Submission status: Runtime Error

Solution code:
import numpy as np

N, Q = list(map(int, input().split()))
tree = np.eye(N)

for i in range(N-1):
  a, b = list(map(int, input().split()))
  ids = tree[:, a-1] > 0
  tree[ids, b-1] = 1
  
r = np.zeros(N)
for i in range(Q):
  p, x = list(map(int, input().split()))
  r += (tree[p-1] > 0)*x
  
r = np.array(r, dtype=int)
print(' '.join(map(str, r)))

Submission status: Runtime Error

Solution code:
import numpy as np

N, Q = list(map(int, input().split()))
tree = np.eye(N)

for i in range(N-1):
  a, b = list(map(int, input().split()))
  ids = tree[:, a-1] > 0
  tree[ids, b-1] = 1
  
r = np.zeros(N)
for i in range(Q):
  p, x = list(map(int, input().split()))
  r += (tree[p-1] > 0)*x
  
out = str(int(r[0]))
for i in range(1, N):
  out += ' {0}'.format(int(r[i]))

print(out)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
ab_array = [[int(x) for x in input().split()] for y in range(n - 1)]
px_array = {}
for i in range(q):
    p, x = map(int, input().split())
    px_array.setdefault(p, 0)
    px_array[p] += x

adjacency_list = [[] for x in range(n+1)]
for a, b in ab_array:
    if a < b:
        adjacency_list[a].append(b)
    else:
        adjacency_list[b].append(a)
cost = [0 for x in range(n)]
now_index = 1
now_cost = px_array[1]
nexts = [now_index]

while len(nexts) != 0:
    cost[now_index - 1] += now_cost
    for n in adjacency_list[now_index]:
        # cost[n - 1] += now_cost
        pass
    nexts.remove(now_index)
    nexts += adjacency_list[now_index]
    if len(nexts) == 0:
        continue
    now_index = nexts[-1]
    now_cost += px_array.get(now_index, 0)

for i in cost:
    print(i, end=" ")
print()

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
ab_array = [[int(x) for x in input().split()] for y in range(n - 1)]
px_array = {}
for i in range(q):
    p, x = map(int, input().split())
    px_array.setdefault(p, 0)
    px_array[p] += x

adjacency_list = [[] for x in range(n+1)]
for a, b in ab_array:
    if a < b:
        adjacency_list[a].append(b)
    else:
        adjacency_list[b].append(a)
cost = [0 for x in range(n)]
now_index = 1
now_cost = px_array[1]
nexts = [now_index]

while len(nexts) != 0:
    cost[now_index - 1] += now_cost
    for n in adjacency_list[now_index]:
        # cost[n - 1] += now_cost
        pass
    nexts.remove(now_index)
    nexts += adjacency_list[now_index]
    if len(nexts) == 0:
        continue
    now_index = nexts[-1]
    now_cost += px_array.get(now_index, 0)

for i in cost:
    print(i, end=" ")
print()

Submission status: Runtime Error

Solution code:
#D問題

def add_val(ans, point, value, query, route):
    if point in query.keys():
        value += query[point]
    
    ans[point] += value
    
    if point in route.keys():
        for next_point in route[point]:
            add_val(ans, next_point, value, query, route)

n, q = list(map(lambda x: int(x), input().split()))

r = {}

for i in range(n-1):
    s, e = list(map(lambda x: int(x), input().split()))
    if s-1 in r.keys():
        r[s-1].append(e-1)
    else:
        r[s-1] = [e-1]
        
queries = {}

for i in range(q):
    p, val = list(map(lambda x: int(x), input().split()))
    if p-1 in queries.keys():
        queries[p-1] += val
    else:
        queries[p-1] = val

ans = [0] * n    

add_val(ans, 0, 0, queries, r)
    


ans_str = ''

for i in range(n):
    ans_str += str(ans[i])
    if i < n-1:
        ans_str += ' '

print(ans_str)

Submission status: Runtime Error

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

tree = {i:[] for i in range(1, n + 1)}
for _ in range(1, n):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

tmp = [1]
while len(tmp) != 0:
    tmp2 = tmp
    tmp.clear()
    for bbb in tmp2:
        tree[bbb].remove(bbb)
        tmp.extend(tree[bbb])


cnt = [list(map(int, input().split())) for _ in range(q)]

ans = [0]*n
for p, x in cnt:
    tmp = [p]
    while len(tmp) != 0:
        for i in tmp:
            ans[i-1] += x
        tmp2 = tmp
        tmp.clear()
        for aaa in tmp2:
            tmp.extend(tree[aaa])
    print(ans)

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

Submission status: Runtime Error

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

dic = dict()
counter = [0]*(N+1)
for i in range(N-1):
    a,b = map(int,input().split())

    if not a in dic:
        dic[a] = [b]
    else:
        dic[a].append(b)
        
    if not b in dic:
        dic[b] = [a]
    else:
        dic[b].append(a)

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

def dfs(parent, current):
    counter[current] += counter[parent]
    
    for nex in dic[current]:
        if nex == parent:
            continue
        dfs(current, nex)

dfs(0, 1)

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

Submission status: Runtime Error

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

trees = [[] for i in range(n)]

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

#print("trees: ", trees)    
    
values = [0 for i in range(n)]
for i in range(q):
    p, x = map(int, input().split())
    values[p-1] += x

#print("values: ", values)

def dfs(i):
    for j in trees[i]:
        values[j] += values[i]
        #print("values",i , j, values)
        dfs(j)

dfs(0)
print(*values)

Submission status: Runtime Error

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

class tree:

    def __init__(self, n):
        self.nodes = {i+1:{"parent":None, "childlen":[], "counter":0} for i in range(n)}
    
    def add_relation(self, parent, child):
        self.nodes[parent]["childlen"].append(child)
        self.nodes[child]["parent"] = parent
            
    def get_all_childlen(self, parent):
        return get_childlen(parent)
        
    def get_childlen(self, parent, childlen):
        temp_childlen = self.nodes[parent]["childlen"]
        
        if temp_childlen == []:
            return []
        
        childlen = []
        for temp_c in temp_childlen:
            childlen.extend(get_childlen(temp_c))
            
        childlen.extend(temp_childlen)
        return childlen
        
    def add_counter(self, node, score):
        self.nodes[node]["counter"] += score
        
    #def update_all_counter(self):
    #    root = 0
    #    parent_cnt = self.nodes[root]["counter"]
    #    root_childlen = self.nodes[root]["childlen"]
    #    update(childlen=root_childlen, counter=parent_cnt)
    #    
    #def update(self, childlen, counter):
    #    if childlen == []:
    #        return
    #    
    #    for child in childlen:
    #        self.nodes[child]["counter"] += counter
    #        child_childlen = self.nodes[child]["childlen"]
    #        update(childlen=child_childlen)
    
    def update_all_counter(self):
        root = self.nodes[1]
        self.update(parent=root)
        
    def update(self, parent):
        for child_id in parent["childlen"]:
            child = self.nodes[child_id]
            child["counter"] += parent["counter"]
            self.update(parent=child)
    

T = tree(n)    
    
for i in range(n-1):
    a, b = map(int, input().split())
    T.add_relation(a,b)
    
for i in range(q):
    p, x = map(int, input().split())
    T.add_counter(p, x)
    
T.update_all_counter()
counters = [node["counter"] for node in T.nodes.values()]
print(" ".join([str(c) for c in counters]))

Submission status: Runtime Error

Solution code:
def dfs(tree, val, root, add_val):
  for node in tree[root]:
   	val[node - 1] += add_val
	if node in tree:
		dfs(tree, val, node, add_val)

n, q = raw_input().split()
n = int(n)
q = int(q)

a = []
for i in range(n - 1):
  a.append(map(int, raw_input().split()))
  
b = []
for i in range(q):
  b.append(map(int, raw_input().split()))
  
tree = {}
val = [0] * n

for i in range(n - 1):
  if a[i][0] not in tree:
  	tree[a[i][0]] = []
  
  tree[a[i][0]].append(a[i][1])
  
for i in range(q):
  root = b[i][0]
  add_val = b[i][1]
  val[root - 1] += add_val
  if root in tree:
  	dfs(tree, val, root, add_val)

for i in val:
  print i,

Submission status: Runtime Error

Solution code:
# from collections import deque
#
# N, Q = map(int, input().split())  # N個の頂点, Q回の操作
#
# # 辺を受け取る
# graph = [[] for _ in range(N)]
#
# for _ in range(N-1):
#     a, b = map(lambda x: int(x)-1, input().split())
#     graph[a].append(b)
#     graph[b].append(a)
#
# count = [0] * N
# # その頂点に対して与えられるカウントは伝播する
# for i in range(Q):  # Q個の操作について
#     p, x = map(int, input().split())
#     # ある頂点を根とする部分木には、今現在のcountが全て伝播していく
#     count[p-1] += x
#
# q = deque([0])  # 開始のノード
# flag = [False] * N
#
# while len(q):
#     v = q.pop()
#     flag[v] = True  # 部分木の根を到達済みにする
#
#     for e in graph[v]:  # vを根にもつノード全てに操作をする
#         # graphは子のみを格納するのではなく、そのノードから出ている辺を
#         # 親とか子供とか関係なく全て格納してしまうため、親の方向に
#         # 対して伝播をしないようにflagで管理する
#         if flag[e]:  # 頂点eがvの親であればスルー
#             continue
#         # eはvの子供であることが確定する
#         count[e] += count[v]  # 親の値を伝播させていく
#         q.append(e)
#
# print(*count)


#りゅうせいの解答（実行時エラー）
import numpy as np

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

ans = []
for k in range(N):
    ans.append(0)

#カウント用関数
def counting(ans,binary_tree,count_list, y, idy):
    ans[int(binary_tree[idy]) - 1] += y[1]
    if (binary_tree[idy*2 + 1] != 0):
        counting(ans, binary_tree, count_list, y, idy*2 + 1)

    if (binary_tree[idy*2 + 2] != 0):
        counting(ans, binary_tree, count_list, y, idy*2 + 2)


#treeの作成
binary_tree = np.zeros(2**(4*N))
binary_tree[0] = 1

tuple_list = [list(map(int,input().split())) for i in range(N-1)]

while (len(tuple_list)):
    x = tuple_list.pop(0)
    idx = np.where(binary_tree == x[0])[0]

    if (binary_tree[idx*2 + 1] == 0):
        binary_tree[idx * 2 + 1] = x[1]

    else:
        binary_tree[idx * 2 + 2] = x[1]

#木の表示
#print(binary_tree)

count_list = [list(map(int,input().split())) for j in range(Q)]
while (len(count_list)):
    y = count_list.pop(0)
    idy = np.where(binary_tree == y[0])[0]
    counting(ans, binary_tree, count_list, y, idy)

strs = [str(num) for num in ans]
print(" ".join(strs))