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

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

tree = [[] for _ in range(n)]
ope = [0]*n
opef=[False]*n
ret=[0]*n

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

def counter(target,num):
    global ret
    global ope
    global opef
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        tmp=0
        if opef[i]==False:
            tmp=ope[i]
            opef[i]=True
        counter(i,num+tmp)

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

for i in range(n):
    if opef[i]==False:
        opef[i]=True
        counter(i,ope[i])

print(*ret)

Submission status: Time Limit Exceeded

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

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

result = [0]*N

def konitas(i, j):
    result[i-1] += j
    for ii, mi in enumerate(matrix[i-1]):
        if mi==1:
            konitas(ii+1, j)

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

print(*result)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
# [[parents]]
tree = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  if a == 1:
    tree[b-1] = [1]
  elif b == 1:
    tree[a-1] = [1]
  
  elif len(tree[a-1]) == 0:
    tree[a-1] = tree[b-1].copy()
    tree[a-1].append(b)
  elif len(tree[b-1]) == 0:
    tree[b-1] = tree[a-1].copy()
    tree[b-1].append(a)

# tr[parent] = [childern]
tr = [[] for _ in range(n)]
for i, row in enumerate(tree):
  for x in row:
    tr[x-1].append(i+1)

cnt = [0 for _ in range(n)]
for _ in range(q):
  p, x = map(int, input().split())
  cnt[p-1] += x
  for child in tr[p-1]:
    cnt[child-1] += x
print(' '.join(map(str, cnt)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
l=[None]*N
l[0]=[1,1,0]
for i in range(1,N):
    a,b=map(int,input().split())
    l[i]=[b,a,0]
l.sort()
for i in range(Q):
    p,x=map(int,input().split())
    l[p-1][2]+=x
t=[l[0][2]]+[None]*(N-1)
for i in range(1,N):
    t[i]=t[l[i][1]-1]+l[i][2]
print(*t)

Submission status: Time Limit Exceeded

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

N, Q = map(int,input().split())
Node = [-1] * N
Counter = [0] * N
Result = [0] * N

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

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

for i in range(N):
    p = i
    ans = 0
    while p >= 0:
        ans = ans + Counter[p]
        p = Node[p]
        
    Result[i] = ans

print(" ".join(list(map(str,Result))))

Submission status: Time Limit Exceeded

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

graph = [[] for i in range(n)]
for i in range(n-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
cost_ls = [0 for i in range(n)]
for i in range(q):
    a,b = list(map(int,input().split()))
    cost_ls[a-1] += b

#深さ優先探索
checkls = [True for i in range(n)]
returnCheck = [True for i in range(n)]
kesita = [True for i in range(n)]
v = 0
cost = 0
stack = [0]
checkls[0] = False
hikuV = []
ansls = [0 for i in range(n)]
while stack:
    v = stack.pop()
    cost += cost_ls[v]
    hikuV.append(v)
    returnCheck[v] = False
    ansls[v] = cost
    finish_check = True
    for i in graph[v]:
        if checkls[i]:
            stack.append(i)
            checkls[i] = False
            finish_check = False
    if not stack:
        break
    if finish_check:
        cost -= cost_ls[v]
        while True:
            breakcheck = False
            kari = 0
            for i in graph[v]:
                if v != i and kesita[i]:
                    kari = i
                if returnCheck[i]:
                    breakcheck = True
            if breakcheck:
                break
            cost -= cost_ls[v]
            kesita[v] = False
            v = kari

for i in range(len(ansls)):
    print(ansls[i],end = ' ')
print()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
n,q= map(int,input().split())
nodes = [[]for _ in range(n+1)]
subnode = [[]for _ in range(n+1)]
value = [0 for _ in range(n+1)]
for i in range(n-1):
    a,b = map(int,sys.stdin.readline().split())
    nodes[a].append(b)
    nodes[b].append(a)
query = []
for i in range(q):
    a, b = map(int, sys.stdin.readline().split())
    query.append([a,b])
def dfs(node,p):
    temp = []
    for v in nodes[node]:
        if v !=p:
            temp= temp+ dfs(v,node)
    my = temp+[node]
    # print(node,my)
    subnode[node]=my
    return my
dfs(1,-1)
for a,b in query:
    for v in subnode[a]:
        value[v]+=b
print(*value[1:])

Submission status: Time Limit Exceeded

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

x_sorted = [0 for _ in range(n)]
for i in range(q):
    p = px[i][0]
    x = px[i][1]
    x_sorted[p - 1] += x

start = 0
inf = float('inf')
cost = dict() # コストテーブル
for i, j in ab:
    c = x_sorted[i - 1]
    cost[i - 1] = cost.get(i - 1, []) + [(j - 1, c)]

d = [inf for i in range(n)] # 最短距離
d[start] = 0

qq = [[d[0], 0]]
while qq:
    [du, u] = qq.pop(0) # 最短距離とその頂点
    for v, weight in cost.get(u, []):
        alt = du + weight
        d[v] = alt
        qq.append([alt, v])

ans = ''
for i in range(n):
    ans += str(d[i] + x_sorted[i]) + ' '

print(ans[:-1])

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
memo = [[i] for i in range(N)]
flg = [False]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)

ans = [0]*N

for i in range(Q):
    p, x = map(int, input().split())
    if not flg[p-1]:
        flg[p-1] = True
        ans[p-1] += x
        queue = [p-1]
        while queue:
            par = queue.pop(0)
            if G[par]:
                for i in G[par]:
                    ans[i] += x
                    queue.append(i)
                    memo[p-1].append(i)
    else:
        for i in memo[p-1]:
            ans[i] += x

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy


class Node:
    def __str__(self):
        return 'ノード {}'.format(self.num)

    def __init__(self, num):
        self.num = num
        self.children = []
        self.all_children = []
        self.count = 0

    def add_child(self, child):
        self.children.append(child)

    def print_child(self, _all=False):
        if _all:
            for child in self.all_children:
                print(child)
        else:
            for child in self.children:
                print(child)

    def search_all_children(self):
        self.all_children = self.children
        for child in self.children:
            self.all_children += child.search_all_children()
        return self.all_children

    def count_all(self, amount):
        self.count += amount
        for child in self.all_children:
            child.count += amount


n, q = map(int, input().split())
ab = sorted([sorted(list(map(int, input().split()))) for _ in range(n-1)], key=lambda x: x[0])
# add x to nodes[p-1]
px = [list(map(int, input().split())) for _ in range(q)]

nodes = [Node(i+1) for i in range(n)]
heads = {1}
while ab:
    c = ab.pop(0)
    if c[0] in heads:
        nodes[c[0]-1].add_child(nodes[c[1]-1])
        heads.add(c[1])
    elif c[1] in heads:
        nodes[c[1]-1].add_child(nodes[c[0]-1])
        heads.add(c[0])
    else:
        ab.append(c)

nodes[0].search_all_children()

for q in px:
    nodes[q[0]-1].count_all(q[1])

for node in nodes:
    print(node.count, end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
# A, B = [int(i) for i in input().split(" ")]
# A = int(input())
# As = [int(i) for i in input().split(" ")]
# Ss = ["".join(sorted(input())) for _ in range(N)]
# from math import factorial
# def nCr(n, r): return factorial(n) // factorial(r) // factorial(n - r)
from collections import defaultdict 
import sys
sys.setrecursionlimit(2**20) 

N, Q = [int(i) for i in input().split(" ")]
edges = defaultdict(list)
for _ in range(N - 1):
    a, b = [int(i) for i in input().split(" ")]
    edges[a-1].append(b-1)
PX = defaultdict(int)
for _ in range(Q):
    p, x = [int(i) for i in input().split(" ")]
    PX[p-1] += x

ans = [0 for _ in range(N)]
visited = [False for _ in range(N)]
def dfs(i, v):
    if visited[i]:
        return
    visited[i] = True
    ans[i] += v
    for j in edges[i]:
        dfs(j, v + PX[j])
dfs(0, PX[0])
for a in ans:
    print(a, end=" ")

Submission status: Time Limit Exceeded

Solution code:
#0818_D
N, Q = list(map(int,input().split()))
ki = {}
# 木構築
for i in range(N-1):
    a,b = list(map(int,input().split()))
    try:
        if len(ki[a]) == 0:
            ki[a] = [b]
        else:
            ki[a].append(b)
    except:# ディクショナリ登録がなかった場合の例外処理
        ki[a] = [b]

counter = [0] * N
searchlist = []
# 操作
for i in range(Q):
    p,x = list(map(int,input().split()))
    counter[p-1] += x
    searchlist.append(p)
    while len(searchlist) > 0:
        for j in searchlist:
            searchlist.remove(j)
            try:
                for k in ki[j]:
                    counter[k-1] += x
                    searchlist.append(k)
            except:# 要素がなかった場合の例外処理
                continue
for i in range(N):
    print(counter[i], end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from collections import deque

def main():
    N,Q=map(int, input().split())
    T = defaultdict(list)
    C = defaultdict(int)
    PX = deque()
    for i in range(N-1):
        a,b=map(int, input().split())
        T[a].append(b)
    for i in range(Q):
        p,x=map(int, input().split())
        PX.append((p,x))
    
    while len(PX) > 0:
        px = PX.pop()
        C[px[0]] += px[1]
        for i in T[px[0]]:
            PX.appendleft((i, px[1]))

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def down(p, x, N, Point, part_tree):
    #print(Point)
    Point[p] += x
    for i in range(1, N + 1):
        if part_tree[p][i] == 1:
            down(i, x, N, Point, part_tree)

def main():
    N, Q = list(map(int, input().split(' ')))

    Point = [0 for i in range(N + 1)]
    part_tree = [[0 for i in range(N + 1)] for j in range(N + 1)]
    for i in range(N - 1):
        a, b = list(map(int, input().split(' ')))
        part_tree[a][b] = 1
    #print(part_tree)
    #print(Point)

    PX = [list(map(int, input().split(' '))) for i in range(Q)]
    PX.sort()
    i = 1
    while i < len(PX):
        if PX[i - 1][0] == PX[i][0]:
            PX[i - 1][1] += PX[i][1]
            PX.pop(i)
        else:
            i += 1
    #print(PX)
    for px in PX:
        down(px[0], px[1], N, Point, part_tree)
    Point.pop(0)
    print(*Point)

if __name__ != 'main':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)

class Node(object):
    def __init__(self, id):
        self.id = id
        self.value = 0
        self.parent_id = []
        self.children_id = []

    def set_parent(self, parent_id):
        self.parent_id.append(parent_id)

    def set_child(self, child_id):
        self.children_id.append(child_id)

    def add_number(self, n):
        self.value += n
        for child_id in self.children_id:
            nodes[child_id].add_number(n)

    def get_value(self):
        return self.value


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

nodes = []
for i in range(N + 1):
    nodes.append(Node(i))

for j in range(N - 1):
    parent, child = map(int, input().split())
    nodes[parent].set_child(child)
    nodes[child].set_parent(parent)

for _ in range(Q):
    parent, number = map(int, input().split())
    nodes[parent].add_number(number)

res = []
for k in range(1, N + 1):
    res.append(nodes[k].get_value())

print(*res, sep=' ')

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

temp=[[i+1] for i in range(n)]
tempr=[]
check=[]
for i in range(n-1):
    temp[ab[i][0]-1].append(ab[i][1])
    tempr.append([ab[i][1],ab[i][0]])
    if i >= 1:
        for j in range(i):
            if ab[i][0] == tempr[j][0]:
                temp[tempr[j][1]-1].append(ab[i][1])

ans=[0 for i in range(n)]
for j in range(q):
    for _ in temp[px[j][0]-1]:
        ans[_-1]+=px[j][1]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**6)

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

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

# global counter
tree = [[] for _ in range(n+1)]

def make_tree(num, tree, path, parent):
  for i in path[num]:
    if i == parent:
      continue

    tree[num].append(i)
    make_tree(i, tree, path, num)

make_tree(1, tree, path, 0)

plus = [0] * (n + 1)

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

def calc(num, tree, plus, parent):
  for i in tree[num]:
    if i == parent:
      continue

    plus[i] += plus[num]
    calc(i, tree, plus, num)

calc(1, tree, plus, 0)

print(" ".join([str(i) for i in plus[1:]]))

Submission status: Time Limit Exceeded

Solution code:
# Setup
import sys
import collections
sys.setrecursionlimit(4100000)

n,q = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(n-1)]
p = [[int(i) for i in input().split()] for _ in range(q)]

childs = collections.defaultdict(list)

for A,B in a:
    childs[A].append(B)

counter = collections.defaultdict(int)
affections = collections.defaultdict(list)

for A,B in p:
    counter[A] += B
    if affections.get(A):
        continue
    current = A
    aff = []
    tosee = [current]
    while len(tosee) != 0:
        temp = tosee.pop()
        aff.append(temp)
        for z in childs[temp]:
            if affections.get(z):
                aff += affections[z]
            else:
                tosee.append(z)
    affections[A] = aff
counts = collections.defaultdict(int)
for i in range(1,n+1):
    for z in affections[i]:
        counts[z] += counter[i]

ans = ""
for i in range(1,n+1):
    ans += str(counts[i]) + " "
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

px_dict = {}
for p, x in px_list:
    if p in px_dict:
        px_dict[p] += x
    else:
        px_dict[p] = x

ab_dict = {}
for a,b in ab_list:
    if a in ab_dict:
        ab_dict[a].append(b)
    else:
        ab_dict[a] = [b]

scores = [0 for _ in range(N+1)] # 1子おおい

def add_cnt(v, score):
    # pxdictから持ってきてスコアを足す
    if v in px_dict:
        score += px_dict[v]
    # スコアを足さないこともある
    
    #今いる頂点に現在のスコアをめも
    scores[v] = score
    
    # 繋がっている頂点に今のスコアを投げる
    if v in ab_dict:
        for b in ab_dict[v]:
            add_cnt(b,score)

add_cnt(1,0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
tree = [[0] * n for _ in range(n)]
counter = [0] * n
for i in range(n - 1):
    a, b = map(int, input().split())
    tree[a - 1][b - 1] = 1
for i in range(n - 1, 0, -1):
    for j in range(n):
        if tree[i - 1][j] == 1:
            tree[i - 1] = [x + y for x, y in zip(tree[i - 1], tree[j])]
for i in range(q):
    p, x = map(int, input().split())
    counter[p - 1] += x
    for j in range(n):
        counter[j] += x * tree[p - 1][j]
print(*counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
n, q = map(int,input().split())
d = {}
for i in range(n-1):
    ai, bi = map(int,input().split())
    if ai-1 in d:
        d[ai-1] += [bi-1]
    else:
        d[ai-1] = [bi-1]
    if bi-1 in d:
        d[bi-1] += [ai-1]
    else:
        d[bi-1] = [ai-1]
#point
px = {}
for i in range(q):
    pi,xi = map(int,input().split())
    if pi- 1 in px:
        px[pi-1] += xi
    else:
        px[pi-1] = xi
sp = [0 for i in range(n)]

def f(v,vp,p):
    if v in px:
        su = p + px[v]
    else:
        su = p
    sp[v] = su
    if v in d:
        for di in d[v]:
            if not di == vp:
                f(di,v,su)
f(0,0,0)
for i in range(n):
    print(sp[i])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
a=[0]*(n-1)
b=[0]*(n-1)
for i in range(n-1):
    a[i],b[i]=map(int,input().split())
p=[0]*q
x=[0]*q
for k in range(q):
    p[k],x[k]=map(int,input().split())
t=[[i] for i in range(1,n+1)]
for i in range(n-1):
    if a[i] not in t[a[i]-1]:
        t[a[i]-1].append(a[i])
    if b[i] not in t[a[i]-1]:
        t[a[i]-1].append(b[i])
for i in range(n):
    for j in t[i]:
        for y in t[j-1]:
            if y not in t[i]:        
                t[i].append(y)
ans=[0 for _ in range(n)]
g=0
for k in p:
    for j in t[k-1]:
        ans[j-1]+=x[g]
    g+=1  
print(' '.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = (int(v) for v in input().split())
edge_dict = {}
for i in range(1, N):
    a, b = (int(v) for v in input().split())
    edge_dict.setdefault(a, []).append(b)
cnt_dict = {}
for i in range(1, Q + 1):
    p, x = (int(v) for v in input().split())
    cnt_dict[p] = cnt_dict.get(p, 0) + x

for p in range(1, N + 1):
    if cnt_dict.get(p, 0) == 0:
        continue
    for q in edge_dict.get(p, []):
        cnt_dict[q] = cnt_dict.get(q, 0) + cnt_dict.get(p, 0)

for p in range(1, N):
    print(cnt_dict.get(p, 0), end=' ')
print(cnt_dict.get(N, 0))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]
ab.sort(key=lambda x: (x[0], x[1]))
px.sort(key=lambda x: (x[0], x[1]))
ans = [0] * n

for i in px:
  ans[i[0] - 1] += i[1]

for i in ab:
  ans[i[1] - 1] += ans[i[0] - 1]
  
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10000000)

class tree:
    def __init__(self):
        self.baby_list=[]
        self.counter=0
    
    def add_value(self):
        for i in self.baby_list:
            hoge[i].counter += self.counter
            hoge[i].add_value()

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


hoge={}

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

for i in range(Q):
    root, value = list(map(int, input().split() ))
    hoge[root].counter+=value

hoge[1].add_value()
output = []
for t in hoge:
    output.append(hoge[t].counter)

output = list(map(str, output))
print(" ".join(output))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
class AdjacencyList(object):
    def __init__(self):
        self.List = {}

    def addEdge(self, fromVertex, toVertex):
        # check if vertex is already present
        if fromVertex in self.List.keys():
            self.List[fromVertex].append(toVertex)
        else:
            self.List[fromVertex] = [toVertex]


if __name__ == '__main__':
    al = AdjacencyList()
    n,q = (int(i) for i in input().split())
    for i in range(n-1):
        num1,num2 = (int(i) for i in input().split())
        al.addEdge(num1,num2)

    counter = defaultdict(list)
    for i in range(q):
        num1,num2 = (int(i) for i in input().split())
        counter[num1].append(num2)

    dp = [0,sum(counter[1])]
    for i in range(1,n+1):
        ans=0
        if(i==1):
            print(sum(counter[i]),end=" ")
        else:
            for j in al.List.keys():
                if(i in al.List[j]):
                    break
            ans = dp[j]+sum(counter[i])
            print(ans,end=" ")
            dp.append(ans)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
chi = [set([i]) for i in range(N)]
par = [set([i]) for i in range(N)]


for n in range(N-1):
    a,b = map(int, input().split())
    chi[a-1].add(b-1)
    par[b-1].add(a-1)
    f = par[a-1]
    for i in f:
        chi[i] = chi[i] | chi[a-1]
        par[a-1] = par[a-1] | par[i]
            
cnt = [0]*N   
for q in range(Q):
   p,x = map(int, input().split())
   for i in chi[p-1]:
       cnt[i] += x

for n in range(N):
    print(cnt[n], end=" ")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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


class Node:
    def __init__(self, index):
        self.index = index
        self.point = 0

    def updatePoints(self, point):
        self.point += point


nodes = [Node(i) for i in range(1, n + 1)]


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


def selectNode(p):
    selected = [p]
    ls = edges[p]
    selected += ls

    while True:
        if ls == []:
            break
        for x in ls:
            ls = edges[x]
            selected += ls
    return selected

for _ in range(q):
    p, x = map(int, input().split())
    node_index_list = selectNode(p)
    for idx, node in enumerate(nodes):
        if idx + 1 in node_index_list:
            node.updatePoints(x)

print(*(node.point for node in nodes))

Submission status: Time Limit Exceeded

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

    # tree = [[] for _ in range(N)]
    tree = defaultdict(list)

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

    for i in range(N-1,-1,-1):
        if tree[i]:
            for j in tree[i]:
                if tree[j]:
                    for k in tree[j]:
                        tree[i].append(k)
    
    ans = [0] * N

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

    print(*ans)


main()

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
Ki_p = [0 for i in range(N+1)]
Ki_c = [[] for i in range(N+1)]
Ki_co = [0 for i in range(N+1)]
v = set([1])
re = []

for i in range(N-1):
    a,b = map(int,input().split())
    if a in v:
        Ki_p[b] = a
        Ki_c[a] += [b]
        v.add(b)
    elif b in v:
        Ki_p[a] = b
        Ki_c[b] += [a]
        v.add(a)
    else:  re.append([a,b])

while len(re) > 0:
    for i in range(len(re)):
        a,b = (x for x in re.pop(0))
        if a in v:
            Ki_p[b] = a
            Ki_c[a] += [b]
            v.add(b)
        elif b in v:
            Ki_p[a] = b
            Ki_c[b] += [a]
            v.add(a)
        else:  re.append([a,b])

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

ans = [0 for i in range(N+1)]
vc = [1]
for i in range(N):
    vi = vc.pop(0)
    ans[vi] = Ki_co[vi] + ans[Ki_p[vi]]
    vc += Ki_c[vi]

print(' '.join(map(str,ans[1:N+1])))

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(1000000)

from collections import defaultdict

def inc(tree, point, p, x):
    # 自分
    point[p] += x
    if tree[p] == -1:
        return

    for child in tree[p]:
        inc(tree, point, child, x)


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

tree = [-1] * (N+1)
point = [0] * (N+1)

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

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

for p, x in dd.items():
    inc(tree, point, p, x)

point.pop(0)
print(*point)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(20000000)
n,q = map(int,input().split())
ab = [[int(v) for v in input().split()] for _ in range(n-1)]
px = [[int(v) for v in input().split()] for _ in range(q)]

adjacent_list = [[] for _ in range(n+1)]

n_num = [0 for _ in range(n+1)]
q_num = [0 for _ in range(n+1)]

for query in px:
    p,x = query
    q_num[p] += x

for edge in ab:
    a,b = edge
    adjacent_list[a].append(b)

def dfs(cur,prev_state):
    now_state = q_num[cur] + prev_state
    n_num[cur] = now_state

    for next_node in adjacent_list[cur]:
        dfs(next_node,now_state)

dfs(1,0)

for ans in n_num[1:]:
    print(ans,end=' ')
print()

Submission status: Time Limit Exceeded

Solution code:
np = input().split()
N = int(np[0])
Q = int(np[1])


class Node:

    def __init__(self, number_id):
        self.number_id = number_id  # int
        self.connection_list = []  # つながりのあるidのリスト
        self.parent_id = None
        self.children_list = []
        self.add_number = 0

    def add_add_number(self, add_n):
        self.add_number += add_n

    def add_connection(self, connect_id):
        self.connection_list.append(connect_id)

    def set_tree(self, parent_id, add_n):
        self.parent_id = parent_id
        self.add_number += add_n
        for child_d in self.connection_list:
            if child_d != parent_id:
                self.children_list.append(child_d)
        self.connection_list = []
        return self.children_list


# 読み込んでグラフを作成
# ノード間のつながりができてから，親と子を決定する
node_list = [Node(i+1) for i in range(N)]
for _ in range(N-1):
    ab = input().split()
    a = int(ab[0])
    b = int(ab[1])
    a_node = node_list[a-1]
    b_node = node_list[b-1]
    a_node.add_connection(b)
    b_node.add_connection(a)

# ノードごとに足される数を保存する
for _ in range(Q):
    px = input().split()
    p = int(px[0])
    x = int(px[1])
    p_node = node_list[p-1]
    p_node.add_add_number(x)
# のーど1からノードにあるadd numberを足していく
# node 1 から親子関係を決定する
node_one = node_list[0]
children_dictionary = {}  # key:parent id, value: children list
key_list = [1]
child_l = node_one.set_tree(0, 0)
children_dictionary[1] = child_l
while len(children_dictionary) != 0:
    # key = sorted(children_dictionary.keys())[0]
    key = key_list.pop(0)
    parent_add_n = node_list[key-1].add_number
    children_l = children_dictionary.pop(key)
    for child in children_l:
        new_children = node_list[child-1].set_tree(key, parent_add_n)
        children_dictionary[child] = new_children
        key_list.append(child)

# 出力
for node in node_list:
    print(node.add_number, end=" ")
print("")

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def DFS(n):
	if n != 0 and ans[n] != -1:
		return 0
	if not n == 0:
		ans[n] = counter[n] + ans[par[n]]
	for child in tree[n]:
		DFS(child)

N, Q = MAP()
ab = [LIST() for _ in range(N-1)]
tree = defaultdict(list)
for a, b in ab:
	tree[a-1].append(b-1)
	tree[b-1].append(a-1)

par = [-1]*N
par[0] = 0
zyunban = []
for a, b in ab:
	if par[a-1] != -1:  # 親が存在
		par[b-1] = a-1
	elif par[b-1] != -1:
		par[a-1] = b-1
	else:
		par[a-1] = b-1
		par[b-1] = a-1

px = [LIST() for _ in range(Q)]

counter = defaultdict(int)  # まとめる
for p, x in px:
	counter[p-1] += x

ans = [-1] * N  # 答え入れる
ans[0] = counter[0]
DFS(0)
print(*ans, sep=" ")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, q = map(int, input().split())

counter = [0 for _ in range(n)]
children = [[] for _ in range(n)]

# read a_i b_i
for _ in range(n-1):
    a, b = map(int, input().split())
    children[a-1].append(b-1)

for srt in children[::-1]:
    if len(srt) == 0:
        continue

    st_nodes = []
    for child in srt:
        if len(children[child]) == 0:
            continue
        else:
            st_nodes.extend(children[child])

    srt.extend(st_nodes)

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

for i, xi in enumerate(x):
    counter[i] += xi
    for c in children[i]:
        counter[c] += xi

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