Problem:


Score : 400 points

Problem Statement

Given is a rooted tree with N vertices numbered 1 to N.
The root is Vertex 1, and the i-th edge (1 \leq i \leq N - 1) connects Vertex a_i and b_i.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value 0.

Now, the following Q operations will be performed:

Operation j (1 \leq j \leq Q): Increment by x_j the counter on every vertex contained in the subtree rooted at Vertex p_j.

Find the value of the counter on each vertex after all operations.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq Q \leq 2 \times 10^5

1 \leq a_i < b_i \leq N

1 \leq p_j \leq N

1 \leq x_j \leq 10^4

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

4 3
1 2
2 3
2 4
2 10
1 100
3 1

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Each operation changes the values of the counters on the vertices as follows:

Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.

Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.

Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

Sample Output 2

20 20 20 20 20 20



Sample input:
4 3
1 2
2 3
2 4
2 10
1 100
3 1


Sample output:
100 110 111 110

Submission status: Time Limit Exceeded

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

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

# AB = [[int(x) for x in input().split()] for _ in range(N-1)]

# print(AB)

# 添字を1からにしたいのでN+1
graph = [[] for _ in range(N+1)]

# 各頂点に隣接する頂点
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

# print(graph)
counter = [0] * (N+1)

# print(counter)

# PX = [[int(x) for x in input().split()] for _ in range(Q)]

# 各頂点に点数を足す
for _ in range(Q):
  p, x = map(int, input().split())
  counter[p] += x


def shori(pa,c,val):
  val += counter[c]
  counter[c] = val
  for i in graph[c]:
    if i == pa:
      continue
    shori(c,i,val)
  
shori(0,1,0)
  

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

Submission status: Time Limit Exceeded

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

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

AB = [[int(x) for x in input().split()] for _ in range(N-1)]

# print(AB)

# 添字を1からにしたいのでN+1
graph = [[] for _ in range(N+1)]

# 各頂点に隣接する頂点
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

# print(graph)
counter = [0] * (N+1)

# print(counter)

PX = [[int(x) for x in input().split()] for _ in range(Q)]

# 各頂点に点数を足す
for p,x in PX:
  counter[p] += x


def shori(pa,c,val):
  val += counter[c]
  counter[c] = val
  for i in graph[c]:
    if i == pa:
      continue
    shori(c,i,val)
  
shori(0,1,0)
  

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,Q =map(int,input().split())
bond = [[]for _ in range(N)]
for i in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    bond[a].append(b)
    bond[b].append(a)

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

que =[]
for i in bond[0]:
    que.append([0,i])
    bond[i].remove(0)

for _ in range(N-1):
    ue,sita = que.pop(0)
    for i in bond[sita]:
        que.append([sita,i])
        bond[i].remove(sita)
    qlis[sita] += qlis[ue]
anstr = " ".join([str(i)for i in qlis])
print(anstr)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,Q =map(int,input().split())
bond = [[]for _ in range(N)]
for i in range(N-1):
    a,b = [int(i)-1 for i in input().split()]
    bond[a].append(b)
    bond[b].append(a)

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

ans = [0]*N
ans[0] += qlis[0]
que =[]
for i in bond[0]:
    que.append([0,i])
    bond[i].remove(0)

for _ in range(N-1):
    ue,sita = que.pop(0)
    for i in bond[sita]:
        que.append([sita,i])
        bond[i].remove(sita)
    ans[sita] = ans[ue]+qlis[sita]
anstr = " ".join([str(i)for i in ans])
print(anstr)

Submission status: Time Limit Exceeded

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

child = [[] for _ in range(n)]
for a,b in ab:
    a -= 1
    b -= 1
    child[a].append(b)
    child[b].append(a)
# print(child)

p_val = [0] * n
for p,x in px:
    p_val[p-1] += x

ans = [p_val[0]]+[0]*(n-1)
stack = [0]
visited = [0] * n
while stack:
    s = stack.pop()
    visited[s] = 1
    for c in child[s]:
        if visited[c]:
            continue
        stack+=[c]
        ans[c] = ans[s]+p_val[c]
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

def dfs(child, parent):
    X[child] += X[parent]
    for e in E[child]:
        if e==parent: continue
        dfs(e, child)

dfs(1,0)
print(*X[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

links = [deque() for x in range(n + 1)]
sums = [0 for x in range(n + 1)]
adds = [0 for x in range(n + 1)]

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

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

que = [0,[1]]
checked = [0 for x in range(n+1)]

que = [[-1, [0]]]

while que:
  link = que.pop()
  par = link[0]
  childs = link[1]

  for child in childs:
    if checked[child] != 1:
      sums[child] = sums[par] + adds[child]
      que.append([child, links[child]])
      checked[child] = 1

  
print(*sums[1:])

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N,Q = map(int,input().split())
d = defaultdict(list)

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

c = defaultdict(int)

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

ans = [0 for i in range(N)]
que = [(1,0,-1)]
while len(que)>0:
    tmp = []
    for v,x,par in que:
        x += c[v]
        ans[v-1] = str(x)
        for w in d[v]:
            if w != par:
                tmp.append((w,x,v))
    que = tmp

print(*ans)

Submission status: Time Limit Exceeded

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

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

value = [0]*(N+1)

for i in range(Q):
  p, x = map(int, input().split())
  value[p] += x
  
def dfs(v, parent):  
  for i in tree[v]:
    if i == parent:
      continue
    value[i] += value[v]
    dfs(i, v)
    
dfs(1, 0)  
print(*value[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
# from functools import reduce
import sys
from collections import defaultdict
 
sys.setrecursionlimit(1000000)
 
 
def main():
    # n, q
    n, q = map(int, input().split())
 
    trees = [[] for i in range(n+1)]
    # a, b
    for _ in range(0, n - 1):
        a, b = map(int, input().split())
        trees[a].append(b)
        trees[b].append(a)
 
    values = [0 for i in range(n+1)]
    # p, x
    for _ in range(0, q):
        p, x = map(int, input().split())
        values[p] += x
    process(1, -1, trees, values)
    print(*values[1:])
 
 
def process(i, parent, trees, values):
    for j in trees[i]:
        if j == parent:
            continue
        values[j] += values[i]
        process(j, i, trees, values)
 
 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

def dfs(v, parent):
    for i in graph[v]:
        if i==parent:
            continue
        counter[i] += counter[v]
        dfs(i, v)
        
dfs(0, -1)
print(*counter)

Submission status: Time Limit Exceeded

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

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

def dfs(v, prev):
    for i in to[v]:
        if prev == i:
            continue
        w[i] += w[v]
        dfs(i, v)

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

Submission status: Time Limit Exceeded

Solution code:
def bfs():
    p[1]=None
    frontier=[1]
    while frontier:
        next=[]
        for u in frontier:
            for v in adj[u]:
                if v not in p:
                    p[v]=u
                    next.append(v)
        frontier=next
        
def bfsc(s,co):
    frontier=[s]
    c[s]+=co
    while frontier:
        next=[]
        for u in frontier:
            for v in adj[u]:
                if v!=p[u]:
                    c[v]+=co
                    next.append(v)
        frontier=next
        
n,q=map(int,input().split())
adj={}
for i in range(n-1):
    a,b=map(int,input().split())
    if a not in adj:
        adj[a]=[b]
    else:
        adj[a].append(b)
    if b not in adj:
        adj[b]=[a]
    else:
        adj[b].append(a)
c={}
p={}
for i in range(1,1+n):
    c[i]=0
bfs()
for w in range(q):
    a,co=map(int,input().split())
    bfsc(a,co)
for i in range(1,1+n):
    print(c[i],end=" ")

Submission status: Time Limit Exceeded

Solution code:
#親ー子の順に書かれてるか否かめっちゃ重要なのになあ
n,q = map(int,input().split())
peer = [[] for _ in range(n)]
for i in range(n-1):
  a,b = (map(int,input().split()))
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
mom = [-1 for _ in range(n)]
mom[0] = 'luca'
child = [[] for _ in range(n)]
now = [0]
while now != []:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if mom[y] == -1:
        now.append(y)
        mom[y] = x
        child[x].append(y)
#print(peer)
#print(mom)
#print(child)
pq = [0 for _ in range(n)]
for i in range(q):
  p,x = map(int,input().split())
  p -= 1
  pq[p] += x
now = [0]
ans = pq
while now != []:
  last = now
  now = []
  for x in last:
    for y in child[x]:
      ans[y] += ans[x]
    now += child[x]
print(' '.join(list(map(str,ans))))

Submission status: Time Limit Exceeded

Solution code:
class Node:

    def __init__(self, name):
        self.name = name
        self.linked = []
        self.parent = None
        self.children = []
        self.progeny = []
        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())
            print("make 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)
    root_node.progeny.extend(root_node.children)
    for child in root_node.children:
        root_node.progeny.extend(child.children)

def make_counter(root_node):
    for child in root_node.children:
        child.add_count(root_node.count)
        make_counter(child)

if __name__ == "__main__":
    n, q = map(int, input().split())
    nodes = [0] + [Node(i) for i in range(1,n+1)]
    a = []
    b = []
    p = []
    x = []
    for i in range(1,n):
        _a, _b = map(int, input().split())
        a.append(_a)
        b.append(_b)
    
    for _ in range(q):
        _p, _x = map(int, input().split())
        p.append(_p)
        x.append(_x)

    for _a,_b in zip(a, b):
        nodes[_a].add_linked(nodes[_b])
        nodes[_b].add_linked(nodes[_a])

    make_tree(nodes[1])

    for _p,_x in zip(p, x):
        nodes[_p].add_count(_x)
    
    make_counter(nodes[1])
    
    print(" ".join([str(nodes[i].count) for i in range(1,n+1)]))

Submission status: Time Limit Exceeded

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())
            print("make 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)
    root_node.progeny = root_node.children
    for child in root_node.children:
        root_node.progeny.extend(child.children)

if __name__ == "__main__":
    n, q = map(int, input().split())
    nodes = [0] + [Node(i) for i in range(1,n+1)]
    a = []
    b = []
    p = []
    x = []
    for i in range(1,n):
        _a, _b = map(int, input().split())
        a.append(_a)
        b.append(_b)
    
    for _ in range(q):
        _p, _x = map(int, input().split())
        p.append(_p)
        x.append(_x)

    for _a,_b in zip(a, b):
        nodes[_a].add_linked(nodes[_b])
        nodes[_b].add_linked(nodes[_a])

    make_tree(nodes[1])

    for _p,_x in zip(p, x):
        nodes[_p].add_count(_x)
        for node in nodes[_p].get_progeny():
            node.add_count(_x)
    
    #print_tree(nodes[1], 0)
    print(" ".join([str(nodes[i].count) for i in range(1,n+1)]))

Submission status: Time Limit Exceeded

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)]
    a = []
    b = []
    p = []
    x = []
    for i in range(1,n):
        _a, _b = map(int, input().split())
        a.append(_a)
        b.append(_b)
    
    for _ in range(q):
        _p, _x = map(int, input().split())
        p.append(_p)
        x.append(_x)

    for _a,_b in zip(a, b):
        nodes[_a].add_linked(nodes[_b])
        nodes[_b].add_linked(nodes[_a])

    make_tree(nodes[1])

    for _p,_x in zip(p, x):
        nodes[_p].add_count(_x)
        for node in nodes[_p].get_progeny():
            node.add_count(_x)
    
    #print_tree(nodes[1], 0)
    print(" ".join([str(nodes[i].count) for i in range(1,n+1)]))

Submission status: Time Limit Exceeded

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 = []
    for oya in tmp2:
        tmp.extend(tree[oya])
        for ko in tree[oya]:
            tree[ko].remove(oya)


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 = []
        for aaa in tmp2:
            tmp.extend(tree[aaa])


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

Submission status: Time Limit Exceeded

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 = []
    for oya in tmp2:
        tmp.extend(tree[oya])
        for ko in tree[oya]:
            tree[ko].remove(oya)

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 = []
        for aaa in tmp2:
            tmp.extend(tree[aaa])

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

Submission status: Time Limit Exceeded

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

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

g = [[] for i in range(n+1)]

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

for i in range(q):
    p,x = map(int,input().split())
    count[p] += x
    
def dfs(x):
    check[x] = 1
    for u in g[x]:
        if check[u] == 1:
            continue
        count[u] += count[x]
        dfs(u)


dfs(1)

print(*count[1:])

Submission status: Time Limit Exceeded

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

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

g = [[] for i in range(n+1)]

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

for i in range(q):
    p,x = map(int,input().split())
    count[p] += x
    
def dfs(v):
  for u in g[v]:
    if check[u]==1:
      continue
    check[u]=1
    count[u]+=count[v]
    dfs(u)
 

check[1] = 1
dfs(1)

print(*count[1:])

Submission status: Time Limit Exceeded

Solution code:
class Queue:
    def __init__(self, data=[]):
        self.data = data

    def enqueue(self, x):
        self.data.append(x)  # 末尾に追加する

    def dequeue(self):
        return self.data.pop(0)  # 先頭を取り出す

    def is_Empty(self):  # 空であればTrueを返す
        if len(self.data) == 0:
            return True
        else:
            return False


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 = Queue()
q.enqueue(0)  # 開始のノード
flag = [False] * N

while not q.is_Empty():
    v = q.dequeue()
    flag[v] = True  # 部分木の根を到達済みにする

    for e in graph[v]:  # vを根にもつノード全てに操作をする
        # graphは子のみを格納するのではなく、そのノードから出ている辺を
        # 親とか子供とか関係なく全て格納してしまうため、親の方向に
        # 対して伝播をしないようにflagで管理する
        if flag[e]:  # 頂点eがvの親であればスルー
            continue
        # eはvの子供であることが確定する
        count[e] += count[v]  # 親の値を伝播させていく
        q.enqueue(e)

print(*count)

Submission status: Time Limit Exceeded

Solution code:
while True:
    try:
        N, Q = map(int, input().split())
        verts = [None] * N
        qs = [0] * N
        results = [0] * N
        for i in range(N - 1):
            a, b = map(int, input().split())
            a -= 1
            b -= 1
            if verts[a] is None:
                verts[a] = list()
            if verts[b] is None:
                verts[b] = list()
            verts[a].append(b)
            verts[b].append(a)
        for i in range(Q):
            q, x = map(int, input().split())
            q -= 1
            qs[q] += x
        rests = [(0, None)]
        while rests:
            x, parent = rests.pop()
            if parent is not None:
                results[x] += results[parent]
            results[x] += qs[x]
            if verts[x] is not None:
                rests.extend((i, x) for i in filter(lambda j: j != parent, verts[x]))
        print(" ".join(map(str, results)))
    except EOFError:
        break

Submission status: Time Limit Exceeded

Solution code:
# ki
from collections import deque

# input

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

edge = [[] for i in range(n+1)]

for next in ln:
    parent = next[0]
    child = next[1]
    edge[parent].append(child)
    edge[child].append(parent)


score = [0]*(n+1)
visited = [False]*(n+1)

for q in lq:
    score[q[0]] += q[1]

que = deque()
que.append(1)

while que:
    node = que.popleft()
    if not visited[node]:
        visited[node] = True
        for next in edge[node]:
            if not visited[next]:
                score[next] += score[node]
                que.append(next)

print(" ".join([str(n) for n in score][1:]))

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue
n, q = list(map(int, input().split()))
e = [[] for _ in range(n + 2)]
vis = [0 for _ in range(n + 2)]
d = [0 for _ in range(n + 2)]
for _ in range(n - 1):
    u, v = list(map(int, input().split()))
    e[u].append(v)
    e[v].append(u)
while q:
    q -= 1
    p, x = list(map(int, input().split()))
    d[p] += x
q = Queue()
q.put(1)
while not q.empty():
    x = q.get()
    vis[x] = 1
    for v in e[x]:
        if vis[v]: continue
        vis[v] = 1
        q.put(v)
        d[v] += d[x]
print(*(d[_] for _ in range(1, n + 1)))

Submission status: Time Limit Exceeded

Solution code:
n, q = tuple([int(i) for i in input().split(' ')])

g = [[] for _ in range(n + 1)]
c = [0 for _ in range(n + 1)]

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

def solve(i, p):
    c[i] += c[p]
    for e in g[i]:
        if e == p:
            continue
        else:
            solve(e, i)

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

import sys
sys.setrecursionlimit(200000)

solve(1, 0)

print(' '.join([str(i) for i in c[1:]]))

Submission status: Time Limit Exceeded

Solution code:

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

from collections import defaultdict

N, Q = map(int, input().split())
counts = [0] * N

# これだと N がでかすぎる時に TLE になるので、入ってきた値だけの配列を作る
#graph = [ [0 for _ in range(N)] for _ in range(N) ]
def get_graph(N):
    tmp = []
    graph = [ [] for _ in range(1) for _ in range(N)]
    for i in range(N-1):
        a, b = map(int, input().split())

        # 1 - 3 - 2 みたいなケース
        if (b-1) in tmp:
            graph[b-1].append(a-1)
        else:
            graph[a-1].append(b-1)
            tmp.append(b-1)

    return graph


graph = get_graph(N)
#print(graph)

# 指示はまとめる
dd = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    dd[p] += x


def inc(p, x, graph):
    # 0 index
    counts[p] += x

    for c in graph[p]:
        inc(c, x, graph)


for P, X in dd.items():
    P -= 1
    inc(P, X, graph)

print(*counts)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

# BFSで通す
N, Q = map(int, input().split())  # N頂点, Q個の命令

G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):  # 辺はN-1本
    a, b = map(lambda x: int(x)-1, input().split())
    G[a].append(b)
    G[b].append(a)

for i in range(Q):  # Q個の操作について
    p, x = map(int, input().split())
    count[p-1] += x

q = deque([0])  # 頂点のノードを入れる
flag = [False]*N

while len(q):
    v = q.pop()
    flag[v] = True  # 部分木の親を到達済みにする

    for e in G[v]:  # vを親にもつノードについてループを回す
        # if flag[e]:  # 頂点eに到達済みであれば
        #     continue
        count[e] += count[v]  # それぞれの子たちに親の値を伝播させる
        q.append(e)

print(*count)

Submission status: Time Limit Exceeded

Solution code:

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

from collections import defaultdict

N, Q = map(int, input().split())
graph = [ [0 for _ in range(N)] for _ in range(N) ]
counts = [0] * N

def get_graph(N):
    tmp = [False] * N
    for i in range(N-1):
        a, b = map(int, input().split())

        # 1 - 3 - 2 みたいなケース
        if tmp[b-1]:
            graph[b-1][a-1] = 1
        else:
            graph[a-1][b-1] = 1
            tmp[b-1] = True

    return graph

graph = get_graph(N)
#print(graph)

# 指示はまとめる
dd = defaultdict(int)
for i in range(Q):
    p, x = map(int, input().split())
    dd[p] += x


def inc(p, x):
    # 0 index
    counts[p] += x

    for i in range(N):
        if graph[p][i] == 0:
            continue
        inc(i, x)

for P, X in dd.items():
    P -= 1
    inc(P, X)

print(*counts)

Submission status: Time Limit Exceeded

Solution code:
from queue import Queue

N, Q = map(int, input().split())
G = [tuple(map(int, input().split())) for _ in range(N-1)]
W = [tuple(map(int, input().split())) for _ in range(Q)]


# 親に付いている重み
r = [0,] * (N+1)
for p, x in W:
    r[p] += x



# 木の隣接関係
M = [[] for _ in range(N+1)]
for g in G:
    M[g[0]].append(g[1])
    M[g[1]].append(g[0])

# print(M)

# 木の親子関係
P = [[] for _ in range(N+1)]
visited = [0,] * (N+1)

def bfs(start):
    q = Queue()
    q.put(start)
    while not q.empty():
        now = q.get()
        visited[now] = 1
        for child in M[now]:
            if not visited[child]:
                r[child] += r[now]
                q.put(child)


bfs(1)

print(*r[1:])

Submission status: Time Limit Exceeded

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


def dfs(tree, count, p):
    # print(p, tree[p])
    for i in tree[p]:
        count[i] += count[p]
        dfs(tree, count, i)


def solve(tree, count):
    from collections import deque
    stk = deque([1])

    while stk:
        p = stk.pop()
        for i in tree[p]:
            count[i] += count[p]
            stk.append(i)


def remove_parents(tree, p):
    for i in tree[p]:
        tree[i].remove(p)
        remove_parents(tree, i)


def main():
    N, Q = map(int, input().split())
    tree = {i+1: set() for i in range(N)}
    count = {i+1: 0 for i in range(N)}

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

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

    # print(count)

    # visited = {k+1: False for k in range(N)}
    # visited[1] = True

    remove_parents(tree, 1)
    # print(tree)
    # dfs(tree, count, 1)
    solve(tree, count)

    ans = [str(count[k]) for k in sorted(count.keys())]
    print(" ".join(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def dfs(tree, count, p):
    # print(p, tree[p])
    for i in tree[p]:
        # if i == p:
        #     continue
        count[i] += count[p]
        dfs(tree, count, i)


# def solve(tree, count):

def remove_parents(tree, p):
    for i in tree[p]:
        tree[i].remove(p)
        remove_parents(tree, i)


def main():
    N, Q = map(int, input().split())
    tree = {i+1: set() for i in range(N)}
    count = {i+1: 0 for i in range(N)}

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

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

    # print(count)

    # visited = {k+1: False for k in range(N)}
    # visited[1] = True

    remove_parents(tree, 1)
    # print(tree)
    dfs(tree, count, 1)

    ans = [str(count[k]) for k in sorted(count.keys())]
    print(" ".join(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def dfs(tree, count, p):
    # print(p, tree[p])
    for i in tree[p]:
        # if i == p:
        #     continue
        count[i] += count[p]
        dfs(tree, count, i)


def remove_parents(tree, p):
    for i in tree[p]:
        tree[i].remove(p)
        remove_parents(tree, i)


def main():
    N, Q = map(int, input().split())
    tree = {i+1: [] for i in range(N)}
    count = {i+1: 0 for i in range(N)}

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

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

    # print(count)

    # visited = {k+1: False for k in range(N)}
    # visited[1] = True

    remove_parents(tree, 1)
    # print(tree)
    dfs(tree, count, 1)

    ans = [str(count[k]) for k in sorted(count.keys())]
    print(" ".join(ans))


if __name__ == '__main__':
    main()