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: Wrong Answer

Solution code:
import sys
from collections import defaultdict
inputs = sys.stdin.readlines()

class Tree():
    def __init__(self, edges=None):
        self.nodes = set()
        self.edges = dict()
        if edges is not None:
            for e in edges:
                self.add_edge(e)
        
    def __iter__(self):
        return self.edges.__iter__()
    
    def __str__(self):
        return self.edges.__str__()
    
    def __repr__(self):
        return self.edges.__repr__()
    
    def add_node(self, x):
        self.nodes.add(x)
    
    def add_edge(self, x, cost=0):
        assert len(x) == 2, '{} is not appropriate edge!'.format(x)
        a, b = (x[0], x[1]) if x[0] < x[1] else (x[1], x[0])
        if a not in self.nodes:
            self.nodes.add(a)
        if b not in self.nodes:
            self.nodes.add(b)
        self.edges[(a, b)] = cost
    
    def degree(self, n):
        assert n in self.nodes, '{} is not appropriate node!'.format(n)
        return sum([(n in edge) for edge in self.edges])
    
    def get_edges(self, n):
        return [edge for edge in self.edges if n in edge]
    
    def get_nearby_nodes(self, n):
        return [e[1] if e[0] == n else e[0] for e in self.edges if n in e]
    
    def dps(self, root):
        nodes, stack, is_cycle = [], [root]
        while stack:
            current_node = stack.pop()
            assert current_node not in nodes, 'Tree has a cycle!'
                
            nodes.append(current_node)
            for n in reversed(self.get_nearby_nodes(current_node)):
                if n not in nodes:
                    stack.append(n)
        return nodes
    
    def wps(self, root):
        nodes, queue = [], deque([root])
        while queue:
            current_node = queue.popleft()
            assert current_node not in nodes, 'Tree has a cycle!'
            
            nodes.append(current_node)
            for n in self.get_nearby_nodes(current_node):
                if n not in nodes:
                    queue.append(n)
        return nodes, is_cycle
        
    def display(self):
        from IPython.display import SVG, display
        import networkx as nx
        
        net_graph = nx.Graph()
        for e in self:
            net_graph.add_path(e)
        return SVG(nx.nx_agraph.to_agraph(net_graph).draw(prog='fdp', format='svg'))

class RootedTree(Tree):
    def __init__(self, root, edges=None):
        self.root = root
        super().__init__(edges)        
    
    def get_root(self):
        return self.root
    
    def get_parent(self, n):
        if n == self.root:
            return None
        for e in self.edges:
            if n == e[1]:
                return e[0]
        raise RuntimeWarning('parent is not found!')
    
    def get_decendant_nodes(self, n):
        return [e[1] for e in self.edges if n == e[0]]
    
    def dps(self, root):
        nodes, stack = [], [root]
        while stack:
            current_node = stack.pop()
            assert current_node not in nodes, 'Tree has a cycle!'
                
            nodes.append(current_node)
            for n in reversed(self.get_decendant_nodes(current_node)):
                stack.append(n)
        return nodes
    
    def wps(self, root):
        nodes, queue = [], deque([root])
        while queue:
            current_node = queue.popleft()
            assert current_node not in nodes, 'Tree has a cycle!'
            
            nodes.append(current_node)
            for n in self.get_decendant_nodes(current_node):
                queue.append(n)
        return nodes

n, q = map(int, inputs[0].split())
edges = [tuple(map(int, inputs[1+i].split())) for i in range(n-1)]
weights = [tuple(map(int, inputs[n+i].split())) for i in range(q)]

tree = RootedTree(root=1, edges=edges)

ans = defaultdict(int)
for node, w in weights:
    ans[node] += w

stack= [1]
while stack:
    current_node = stack.pop()
    w = ans[tree.get_parent(current_node)]
    if w is None:
        w = 0
    ans[current_node] += w
    current_node, ans[current_node]
    for node in reversed(tree.get_decendant_nodes(current_node)):
        stack.append(node)    

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
inputs = sys.stdin.readlines()

class Tree():
    def __init__(self, edges=None):
        self.nodes = set()
        self.edges = dict()
        if edges is not None:
            for e in edges:
                self.add_edge(e)
        
    def __iter__(self):
        return self.edges.__iter__()
    
    def __str__(self):
        return self.edges.__str__()
    
    def __repr__(self):
        return self.edges.__repr__()
    
    def add_node(self, x):
        self.nodes.add(x)
    
    def add_edge(self, x, cost=0):
        assert len(x) == 2, '{} is not appropriate edge!'.format(x)
        a, b = (x[0], x[1]) if x[0] < x[1] else (x[1], x[0])
        if a not in self.nodes:
            self.nodes.add(a)
        if b not in self.nodes:
            self.nodes.add(b)
        self.edges[(a, b)] = cost
    
    def degree(self, n):
        assert n in self.nodes, '{} is not appropriate node!'.format(n)
        return sum([(n in edge) for edge in self.edges])
    
    def get_edges(self, n):
        return [edge for edge in self.edges if n in edge]
    
    def get_nearby_nodes(self, n):
        return [e[1] if e[0] == n else e[0] for e in self.edges if n in e]
    
    def dps(self, root):
        nodes, stack, is_cycle = [], [root]
        while stack:
            current_node = stack.pop()
            assert current_node not in nodes, 'Tree has a cycle!'
                
            nodes.append(current_node)
            for n in reversed(self.get_nearby_nodes(current_node)):
                if n not in nodes:
                    stack.append(n)
        return nodes
    
    def wps(self, root):
        nodes, queue = [], deque([root])
        while queue:
            current_node = queue.popleft()
            assert current_node not in nodes, 'Tree has a cycle!'
            
            nodes.append(current_node)
            for n in self.get_nearby_nodes(current_node):
                if n not in nodes:
                    queue.append(n)
        return nodes, is_cycle
        
    def display(self):
        from IPython.display import SVG, display
        import networkx as nx
        
        net_graph = nx.Graph()
        for e in self:
            net_graph.add_path(e)
        return SVG(nx.nx_agraph.to_agraph(net_graph).draw(prog='fdp', format='svg'))

class RootedTree(Tree):
    def __init__(self, root, edges=None):
        self.root = root
        super().__init__(edges)        
    
    def get_root(self):
        return self.root
    
    def get_decendant_nodes(self, n):
        return [e[1] for e in self.edges if n == e[0]]
    
    def dps(self, root):
        nodes, stack = [], [root]
        while stack:
            current_node = stack.pop()
            assert current_node not in nodes, 'Tree has a cycle!'
                
            nodes.append(current_node)
            for n in reversed(self.get_decendant_nodes(current_node)):
                stack.append(n)
        return nodes
    
    def wps(self, root):
        nodes, queue = [], deque([root])
        while queue:
            current_node = queue.popleft()
            assert current_node not in nodes, 'Tree has a cycle!'
            
            nodes.append(current_node)
            for n in self.get_decendant_nodes(current_node):
                queue.append(n)
        return nodes

n, q = map(int, inputs[0].split())
edges = [tuple(map(int, inputs[1+i].split())) for i in range(n-1)]
weights = [tuple(map(int, inputs[n+i].split())) for i in range(q)]

tree = RootedTree(root=1, edges=edges)

weights_ = defaultdict(int)
for node, w in weights:
    weights_[node] += w

ans = defaultdict(int)
for node, w in weights_.items():
    for node in tree.dps(node):
        ans[node] += w

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

Submission status: Wrong Answer

Solution code:
import sys
inputs = sys.stdin.readlines()

class Tree():
    def __init__(self, edges=None):
        self.nodes = set()
        self.edges = dict()
        if edges is not None:
            for e in edges:
                self.add_edge(e)
        
    def __iter__(self):
        return self.edges.__iter__()
    
    def __str__(self):
        return self.edges.__str__()
    
    def __repr__(self):
        return self.edges.__repr__()
    
    def add_node(self, x):
        self.nodes.add(x)
    
    def add_edge(self, x, cost=0):
        assert len(x) == 2, '{} is not appropriate edge!'.format(x)
        a, b = (x[0], x[1]) if x[0] < x[1] else (x[1], x[0])
        if a not in self.nodes:
            self.nodes.add(a)
        if b not in self.nodes:
            self.nodes.add(b)
        self.edges[(a, b)] = cost
    
    def degree(self, n):
        assert n in self.nodes, '{} is not appropriate node!'.format(n)
        return sum([(n in edge) for edge in self.edges])
    
    def get_edges(self, n):
        return [edge for edge in self.edges if n in edge]
    
    def get_nearby_nodes(self, n):
        return [e[1] if e[0] == n else e[0] for e in self.edges if n in e]
    
    def dps(self, root):
        nodes, stack, is_cycle = [], [root]
        while stack:
            current_node = stack.pop()
            assert current_node not in nodes, 'Tree has a cycle!'
                
            nodes.append(current_node)
            for n in reversed(self.get_nearby_nodes(current_node)):
                if n not in nodes:
                    stack.append(n)
        return nodes
    
    def wps(self, root):
        nodes, queue = [], deque([root])
        while queue:
            current_node = queue.popleft()
            assert current_node not in nodes, 'Tree has a cycle!'
            
            nodes.append(current_node)
            for n in self.get_nearby_nodes(current_node):
                if n not in nodes:
                    queue.append(n)
        return nodes, is_cycle
        
    def display(self):
        from IPython.display import SVG, display
        import networkx as nx
        
        net_graph = nx.Graph()
        for e in self:
            net_graph.add_path(e)
        return SVG(nx.nx_agraph.to_agraph(net_graph).draw(prog='fdp', format='svg'))

class RootedTree(Tree):
    def __init__(self, root, edges=None):
        self.root = root
        super().__init__(edges)        
    
    def get_root(self):
        return self.root
    
    def get_decendant_nodes(self, n):
        return [e[1] for e in self.edges if n == e[0]]
    
    def dps(self, root):
        nodes, stack = [], [root]
        while stack:
            current_node = stack.pop()
            assert current_node not in nodes, 'Tree has a cycle!'
                
            nodes.append(current_node)
            for n in reversed(self.get_decendant_nodes(current_node)):
                stack.append(n)
        return nodes
    
    def wps(self, root):
        nodes, queue = [], deque([root])
        while queue:
            current_node = queue.popleft()
            assert current_node not in nodes, 'Tree has a cycle!'
            
            nodes.append(current_node)
            for n in self.get_decendant_nodes(current_node):
                queue.append(n)
        return nodes
      
n, q = map(int, inputs[0].split())
edges = [tuple(map(int, inputs[1+i].split())) for i in range(n-1)]
weights = [tuple(map(int, inputs[n+i].split())) for i in range(q)]

g = RootedTree(root=1, edges=edges)
ans = {node:0 for node in g.nodes}
for node, w in weights:
    for node in g.dps(node):
        ans[node] += w

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

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
oyako=[]
for i in range(n-1):
	ab=list(map(int,input().split()))
	ab[0]-=1
	ab[1]-=1
	#もっといい感じの書き方ないかな?
	oyako.append(ab)
nodes=[0]*n
for i in range(q):
	p,x=map(int,input().split())
	p-=1
	nodes[p]+=x
#oyakoを、親についての単調増加にしたい->デフォで先頭要素でのソートになるので安心
oyako.sort()
for ab in oyako:
	nodes[ab[1]]+=nodes[ab[0]]
	#綺麗にかけそうでこの書き方をしたけど大丈夫かな?
for node in nodes:
	print(node,end=' ')

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

def bfs(i):
    
    q = deque([])
    q.append((i-1))
    while q:
        
        num = q.popleft()
        for j in E[num]:
            score[j] += score[num]
            
            q.append((j))
            
    return score
print(*bfs(1))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

def bfs(i):
    s = score[i-1]
    q = deque([])
    q.append((i-1,s))
    while q:
        
        num,sco = q.popleft()
        for j in E[num]:
            score[j] += sco
            sco = score[j]
            q.append((j,sco))
    return score
print(*bfs(1))

Submission status: Wrong Answer

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

cnt = [0] * N
for i in range(Q):
    cnt[p[i] - 1] += x[i]
for i in range(N - 1):
    cnt[b[i] - 1] += cnt[a[i] - 1]
for i in cnt:
    print(i, end = ' ')

Submission status: Wrong Answer

Solution code:
#AtCorder用　自動木取得コード

#１行目がノードの数、２行目以降が２つの数字でノードを繋ぐ辺を表すとき、使える

#変数
#node_n :ノードの数
#edge   :エッジを、入力の順番でリストとして提供
#【注意】ノードクラスのリストは関数で取り出さないと、連動して変わってしまう


#関数
#・getroot()で根を取り出す
#・getleaf()で葉を取り出す
#・childに子のノードクラスのリストが格納
#・parentに親のノードクラスが格納






#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.counter=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self,n):
        self.tree=[]
        self.edge=[]
        self.node_n=n
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        for i in range(self.node_n-1):
            edge=[int(j) for j in input().split()]
            self.tree[edge[0]-1].child.append(self.tree[edge[1]-1])
            self.tree[edge[1]-1].parent=self.tree[edge[0]-1]
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]
    
    
n,q=[int(i) for i in input().split()]
tree=Tree(n)
nodes=tree.tree
opelist=[]
for i in range(q):
    opelist.append([int(j) for j in input().split()])



for ope in opelist:
    nodes[ope[0]-1].counter+=ope[1]

    

node=tree.getroot()

def dpm(node):
    children=node.child
    if children!=[]:
        for child in children:
            child.counter+=node.counter
            dpm(child)
            
dpm(node)

for i in range(n):
    if i==n-1:
        print(nodes[i].counter)
    else:
        print(nodes[i].counter,end=(" "))

Submission status: Wrong Answer

Solution code:
#AtCorder用　自動木取得コード

#１行目がノードの数、２行目以降が２つの数字でノードを繋ぐ辺を表すとき、使える

#変数
#node_n :ノードの数
#edge   :エッジを、入力の順番でリストとして提供
#【注意】ノードクラスのリストは関数で取り出さないと、連動して変わってしまう


#関数
#・getroot()で根を取り出す
#・getleaf()で葉を取り出す
#・childに子のノードクラスのリストが格納
#・parentに親のノードクラスが格納






#ノードクラス
class Node():
    def __init__(self):
        self.name=-1
        self.parent=-1
        self.child=[]
        self.counter=0
        
        
        
        
    #ノードに対する子供の数を取得
    def childnum(self):
        return len(self.child)

    

#木クラス
class Tree():
    
    
    #作成した瞬間、入力の数だけノードを作る。
    def __init__(self,n):
        self.tree=[]
        self.edge=[]
        self.node_n=n
        for i in range(self.node_n):
            a=Node()
            a.name=i
            self.tree.append(a)
        for i in range(self.node_n-1):
            edge=[int(j) for j in input().split()]
            self.tree[edge[0]-1].child.append(self.tree[edge[1]-1])
            self.tree[edge[1]-1].parent=self.tree[edge[0]-1]
       
     
    #根ノードを取得
    def getroot(self):
        return self.tree[0]
    
    #葉ノードのリストを取得
    def getleaf(self):
        leaf=[]
        for i in self.tree:
            if i.child==[]:
                leaf.append(i)
        return leaf
    
    
    #全ノードリストを取得
    def gettree(self):
        return self.tree[:]
    
    
n,q=[int(i) for i in input().split()]
tree=Tree(n)
nodes=tree.tree
opelist=[]
for i in range(q):
    opelist.append([int(j) for j in input().split()])



for ope in opelist:
    nodes[ope[0]-1].counter+=ope[1]

    

node=tree.getroot()

def dpm(node):
    children=node.child
    if children!=[]:
        for child in children:
            child.counter+=node.counter
            dpm(child)
            
dpm(node)

for node in nodes:
    print(node.counter,end=(" "))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

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

d = deque([1])
while d:
  node = d.popleft()
  children = tree[node]
  for child in children:
    counter[child] += counter[node]
    d.append(child)
    
  
print(' '.join(map(str, counter[1:])))

Submission status: Wrong Answer

Solution code:
from collections import deque

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

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

counter = [0] * N
for i in range(Q):
  p, x = map(int, input().split())
  d = deque([p-1])
  while d:
    node = d.pop()
    counter[node] += x
    d.extend(children[node])

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

Submission status: Wrong Answer

Solution code:
N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N - 1)]
PX = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N + 1)]
for A, B in AB:
  graph[A].append(B)
  graph[B].append(A)
graph = tuple(graph)
print("graph:", graph)
  
X = [0] * (N + 1)
for p, x in PX:
  X[p] += x
#print("X:", X)

stack = [1]
check = [0] * (N + 1)
check[1] = 1
cnt = [0] * (N + 1)
cnt[1] = X[1]

while stack:
  s = stack.pop()
  for g in graph[s]:
    if check[g] == 0:
      check[g] = 1
      cnt[g] = cnt[s] + X[g]
      stack.append(g)
print(*cnt[1::])

Submission status: Wrong Answer

Solution code:

def main():
    n, q = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    px = [list(map(int, input().split())) for _ in [0]*q]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d = list(sorted(enumerate(d), key=lambda x: x[1]))
    ans = [0]*n
    for p, x in px:
        ans[p-1] += x
    for i, j in d:
        for k in g[i]:
            if d[k][1] == j+1:
                ans[k] += ans[i]
    print(*ans)


main()

Submission status: Wrong Answer

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

graph=[[] for _ in [0]*n]
[graph[a].append(b) for a,b in ab if a<b]
[graph[b].append(a) for a,b in ab if a>b]

plus=[0 for _ in [0]*n]
for i,j in pq:
    plus[i]+=j

pos=[]
ans=[0 for _ in [0]*n]
temp=0
q=[0]
memo=[False for _ in [0]*n]

while q:
    i=q.pop(-1)
    if memo[i]==False:
        pos.append(i)
        temp+=plus[i]
        ans[i]=temp
    memo[i]=True

    while graph[i]:
        j=graph[i].pop(-1)
        if memo[j]==False:
            q.append(j)
            break
    else:
        temp-=plus[pos[-1]]
        pos.pop(-1)
        if pos!=[]:
            q.append(pos[-1])
print(*ans)

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, q = map(int, input().split())
    ab = [list(map(lambda x:int(x)-1, input().split())) for _ in [0]*(n-1)]
    pq = [list(map(int, input().split())) for _ in [0]*q]
    for i in range(q):
        pq[i][0] -= 1

    graph = [[] for _ in [0]*n]
    [graph[a].append(b) for a, b in ab]

    plus = [0 for _ in [0]*n]
    for i, j in pq:
        plus[i] += j

    pos = []
    ans = [0 for _ in [0]*n]
    temp = 0
    q = [0]
    memo = [False for _ in [0]*n]

    while q:
        i = q.pop(-1)
        if memo[i] == False:
            pos.append(i)
            temp += plus[i]
            ans[i] = temp
        memo[i] = True

        while graph[i]:
            j = graph[i].pop(-1)
            if memo[j] == False:
                q.append(j)
                break
        else:
            temp -= plus[pos[-1]]
            pos.pop(-1)
            if pos != []:
                q.append(pos[-1])
    print(*ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    input = stdin.readline

    n, q = map(int, input().split())
    ab = [list(map(lambda x:int(x)-1, input().split())) for _ in [0]*(n-1)]
    pq = [list(map(int, input().split())) for _ in [0]*q]
    for i in range(q):
        pq[i][0] -= 1

    graph = [[] for _ in [0]*n]
    [graph[a].append(b) for a, b in ab if a < b]
    [graph[b].append(a) for a, b in ab if a > b]

    plus = [0 for _ in [0]*n]
    for i, j in pq:
        plus[i] += j

    pos = []
    ans = [0 for _ in [0]*n]
    temp = 0
    q = [0]
    memo = [False for _ in [0]*n]

    while q:
        i = q.pop(-1)
        if memo[i] == False:
            pos.append(i)
            temp += plus[i]
            ans[i] = temp
        memo[i] = True

        while graph[i]:
            j = graph[i].pop(-1)
            if memo[j] == False:
                q.append(j)
                break
        else:
            temp -= plus[pos[-1]]
            pos.pop(-1)
            if pos != []:
                q.append(pos[-1])
    print(*ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    input=stdin.readline
    
    n,q=map(int,input().split())
    ab=[list(map(lambda x:int(x)-1,input().split())) for _ in [0]*(n-1)]
    pq=[list(map(int,input().split())) for _ in [0]*q]
    for i in range(q):
        pq[i][0]-=1

    graph=[[] for _ in [0]*n]
    [graph[a].append(b) for a,b in ab if a<b]
    [graph[b].append(a) for a,b in ab if a>b]

    plus=[0 for _ in [0]*n]
    for i,j in pq:
        plus[i]+=j

    pos=[]
    ans=[0 for _ in [0]*n]
    temp=0
    q=[0]
    memo=[False for _ in [0]*n]

    while q:
        i=q.pop(-1)
        if memo[i]==False:
            pos.append(i)
            temp+=plus[i]
            ans[i]=temp
        memo[i]=True

        while graph[i]:
            j=graph[i].pop(-1)
            if memo[j]==False:
                q.append(j)
                break
        else:
            temp-=plus[pos[-1]]
            pos.pop(-1)
            if pos!=[]:
                q.append(pos[-1])
    print(*ans)



main()

Submission status: Wrong Answer

Solution code:
N,Q = map(int,input().split())
scores = [0 for _ in range(N)]
flags = [1 for _ in range(N)]

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

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

from collections import deque
nextp = deque([0])
flags[0] = 0
while nextp:
    p = nextp.pop()
    for t in tree[p]:
        if flags[t]:
            scores[t] += scores[p]
            flags[t] = 0
            nextp.append(t)

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
a=[[]for i in range(n-1)]
b=[[]for i in range(n-1)]
ap=[i+1 for i in range(n)]
co=[0 for i in range(n)]

def check(p,ch):
  for i in range(n-1):
    if p==a[i]:
      ch[a[i]-1]=1
      ch[b[i]-1]=1
      ch=check(b[i],ch)
    if p==b[i]:
      ch[b[i]-1]=1
  return(ch)
for i in range(n-1):
  a[i],b[i]=map(int,input().split())
  
p=[[]for i in range(q)]
x=[[]for i in range(q)]
for i in range(q):
  p[i],x[i]=map(int,input().split())
  ch=[0 for i in range(n)]
  ch=check(p[i],ch) 
  for j in range(n):
    if ch[j]==1:
      co[j]+=x[i]
  
  
print(' '.join(map(str,co)))

Submission status: Wrong Answer

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

matrix = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        matrix[i][j]=1
points = [0]*n

for a,b in AB:
    matrix[a-1][b-1]=1
    matrix[b-1][a-1]=1
for p,x in PX:
    index = [i for i in range(len(matrix[p-1])) if matrix[p-1][i]==1 and i>=(p-1)]
    for i in index:
        points[i] += x
print(points)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,Q=map(int,input().split())
    c=[0]*N
    d={}
    for i in range(N-1):
        a,b=map(int,input().split())
        if a-1 in d:
            d[a-1].append(b-1)
        else:
            d[a-1]=[b-1]
        if b-1 in d:
            d[b-1].append(a-1)
        else:
            d[b-1]=[a-1]
    e=[0]*N
    def saiki(pn):
        for cn in d[pn]:
            if cn != e[pn]:
                e[cn]=pn
                saiki(cn)
        return
    saiki(0)
    d2={}
    for i in range(Q):
        p,x=map(int,input().split())
        if p-1 in d2:
            d2[p-1]+=x
        else:
            d2[p-1]=x
    if 0 in d2:
        c[0]+=d2[0]
    for i in range(1,N):
        if i in d2:
            c[i]+=d2[i]
        c[i]+=c[e[i]]
    print(*c)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,q=map(int,input().split())
a=[[]for i in range(n-1)]
b=[[]for i in range(n-1)]
ap=[1]
co=[0]
for i in range(n-1):
  a[i],b[i]=map(int,input().split())
  if a[i] not in ap :
    ap.append(a[i])
    co.append(0)
  if b[i] not in ap:
    ap.append(b[i])
    co.append(0)
ap.sort()

def count(c,x,ap,co):
  for i in range(n-1):
    if a[i]==c:
      if ch[ap.index(b[i])]==0:
        ch[ap.index(b[i])]=1
        co[ap.index(b[i])]+=x
        count(b[i],x,ap,co)
  return(co)      
p=[[]for i in range(q)]
x=[[]for i in range(q)]
for i in range(q):
  p[i],x[i]=map(int,input().split())
  ch=[0 for j in range(n)]
  for j in range(n-1):
    if a[j]==p[i]:
      if ch[ap.index(a[j])]==0:
        ch[ap.index(a[j])]=1
        co[ap.index(a[j])]+=x[i]
      if ch[ap.index(b[j])]==0:
        ch[ap.index(b[j])]=1
        co[ap.index(b[j])]+=x[i]
      co=count(b[j],x[i],ap,co)
  if ch[ap.index(p[i])]==0:
    co[ap.index(p[i])]+=x[i]

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N, Q = MAP()
	G = [[] for _ in range(N)]
	for _ in range(N-1):
		a, b = MAP()
		a -= 1
		b -= 1
		G[a].append(b)
	
	# print(G)

	T = [MAP() for _ in range(Q)]
	T = [[t[0]-1,t[1]] for t in T]
	P = [0]*N
	for t in T:
		s, p = t
		P[s] += p
	# print(P)

	# hq = ((0, 0)) # self, parent
	hq = [(0, 0)] # parent, self
	heapq.heapify(hq)
	while hq:
		par, x = heapq.heappop(hq)
		if x != 0:
			P[x] += P[par]
		for nx in G[x]:
			heapq.heappush(hq, (x, nx))
	
	print(' '.join(map(str, P)))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	N, Q = MAP()
	G = [[] for _ in range(N)]
	for _ in range(N-1):
		a, b = MAP()
		a -= 1
		b -= 1
		G[a].append(b)
	
	# print(G)

	T = [MAP() for _ in range(Q)]
	T = [[t[0]-1,t[1]] for t in T]
	P = [0]*N
	for t in T:
		s, p = t
		P[s] += p
	# print(P)

	q = deque()
	q.append((0, 0)) # self, parent
	while q:
		x, par = q.popleft()
		if x != 0:
			P[x] += P[par]
		for nx in G[x]:
			q.append((nx, x))
	
	print(' '.join(map(str, P)))

if __name__ == '__main__':
	main()