Problem:


Score : 100 points

Problem Statement

There is a tree with N vertices, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N - 1), the i-th edge connects Vertex x_i and y_i.

Taro has decided to paint each vertex in white or black, so that any black vertex can be reached from any other black vertex by passing through only black vertices.

You are given a positive integer M.
For each v (1 \leq v \leq N), answer the following question:

Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

2 \leq M \leq 10^9

1 \leq x_i, y_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}

Output

Print N lines.
The v-th (1 \leq v \leq N) line should contain the answer to the following question:

Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Sample Input 1

3 100
1 2
2 3

Sample Output 1

3
4
3

There are seven ways to paint the vertices, as shown in the figure below.
Among them, there are three ways such that Vertex 1 is black, four ways such that Vertex 2 is black and three ways such that Vertex 3 is black.

Sample Input 2

4 100
1 2
1 3
1 4

Sample Output 2

8
5
5
5

Sample Input 3

1 100

Sample Output 3

1

Sample Input 4

10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

Sample Output 4

0
0
1
1
1
0
1
0
1
1

Be sure to print the answers modulo M.



Sample input:
3 100
1 2
2 3


Sample output:
3
4
3

Submission status: Runtime Error

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

from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N, M, edges):
    cache = [-1] * ((N + 1) ** 2)
    for v in edges:
        if len(edges[v]) == 1:
            cache[v * (N + 1) + edges[v][0]] = (1, 1)

    def visit(parent, self):
        "return (white, black)"
        cacheindex = self * (N + 1) + parent
        ret = cache[cacheindex]
        if ret != -1:
            return ret

        total = 1
        one_black = 0
        for child in edges[self]:
            if child == parent:
                continue
            w, b = visit(self, child)
            total *= (w + b)
            one_black *= b

        if parent != 0:
            ret = (
                1,
                (1 + one_black * 2 + (total - one_black - 1)) % M
            )
            cache[cacheindex] = ret
            return ret
        else:
            return total
    return [visit(0, i + 1) % M for i in range(N)]


def main():
    # parse input
    N, M = map(int, input().split())
    edges = defaultdict(list)
    for i in range(N - 1):
        x, y = map(int, input().split())
        edges[x].append(y)
        edges[y].append(x)

    print(*solve(N, M, edges), sep="\n")


# tests
T1 = """
3 100
1 2
2 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    3
    4
    3
    """


T2 = """
4 100
1 2
1 3
1 4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    8
    5
    5
    5
    """


T3 = """
1 100
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1
    """


T4 = """
10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    0
    0
    1
    1
    1
    0
    1
    0
    1
    1
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Runtime Error

Solution code:
import sys 
sys.setrecursionlimit(1000000) 

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]*(nn+1)
    pb = [1]*(nn+1)
    for i in range(nn):
        u1 = G[v][i]
        u2 = G[v][-i-1]
        pf[i+1] = pf[i]*(dp[(v, u1)]+1)
        pb[i+1] = pb[i]*(dp[(v, u2)]+1)
        pf[i+1] %= M
        pb[i+1] %= M
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)
print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys 
sys.setrecursionlimit(1000000) 

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]
    for u in G[v]:
        pf.append(pf[-1]*(dp[(v, u)]+1)%M)
    pb = [1]
    for u in G[v][::-1]:
        pb.append(pb[-1]*(dp[(v, u)]+1)%M)
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)
print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys 
sys.setrecursionlimit(100000) 
import queue

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]
    for u in G[v]:
        pf.append(pf[-1]*(dp[(v, u)]+1)%M)
    pb = [1]
    for u in G[v][::-1]:
        pb.append(pb[-1]*(dp[(v, u)]+1)%M)
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)

            
print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys 
sys.setrecursionlimit(100000) 
import queue

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)


dp = {}
def rec(p, v):
    C = set(G[v]) - set([p])
    if len(C) == 0:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in C:
        res *= (1+rec(v, u))
    dp[(p, v)] = res
    return dp[(p, v)]

r = 0       
rec(-1, r)

q = queue.Queue()
q.put(r)
ans = [0]*N
ans[r] = dp[(-1, r)]

while not q.empty():
    p = q.get()
    for v in G[p]:
        if ans[v] > 0: continue
        ans[v] = int(dp[(p, v)]*(ans[p]/(1+dp[(p, v)])+1)) % M
        q.put(v)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
import queue
N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)


dp = [0]*N
def rec(p, v):
    C = set(G[v]) - set([p])
    if len(C) == 0:
        dp[v] = 1
        return 1
    res = 1
    for u in C:
        res *= (1+rec(v, u)) % M
    dp[v] = res % M
    return dp[v]

root = 0       
rec(None, root)

q = queue.Queue()
q.put(root)
ans = [0]*N
ans[root] = dp[root] % M

while not q.empty():
    p = q.get()
    for v in G[p]:
        if ans[v] > 0: continue
        ans[v] = int(dp[v]*(ans[p]/(1+dp[v])+1)) % M
        q.put(v)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n, M = map(int, input().split())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

N = M+4 # 必要なテーブルサイズ
g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

ws = {}
bs = {}
def sub(u, p):
    if (p,u) in ws:
        return ws[p,u], bs[p,u]
    w = 1
    b = 1
    for v in ns[u]:
        if v==p:
            continue
        ww,bb = sub(v, u)
        w += (bb-1)
        b *= (1+bb)
        b %= M
    ws[p,u] = w % M
    bs[p,u] = b % M
    return w,b
def sub2(u, p):
    for v in ns[u]:
        if v==p:
            continue
        w1, b1 = ws[p,u], bs[p,u]
        w2, b2 = ws[u,v], bs[u,v]
        w3, b3 = ws[u,p], bs[u,p]
        ww = w1 - (b2-1) + (b3-1)
        bb = b1 * (inverse[1+b2]) * (1+b3)
        ws[u,p], bs[u,p] = ww,bb
        
sub(0, -1)
ws[0,-1] = 1
bs[0,-1] = 1
sub2(0,-1)

ans = [None]*n
for u in range(n):
    ans[u] = sub(u, -1)[1] % M
write("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
def ReRooting(nodeCount, edges, identity, merge, addNode):
  adjacents = [[] for _ in range(nodeCount)]
  indexForAdjacents = [[] for _ in range(nodeCount)]
  for u,v in edges:
    indexForAdjacents[v].append(len(adjacents[u]))
    indexForAdjacents[u].append(len(adjacents[v]))
    adjacents[u].append(v)
    adjacents[v].append(u)
  childSubtreeRes = [[identity]*len(adjacents[i]) for i in range(nodeCount)]
  nodeRes = [identity]*nodeCount
  parents = [-1]*nodeCount
  order = [0]*nodeCount
  index = 0
  stack = [0]
  for node in stack:
    order[index] = node
    index += 1
    for adjacent in adjacents[node]:
      if adjacent == parents[node]:
        continue
      stack.append(adjacent)
      parents[adjacent] = node
  for node in order[::-1]:
    parent = parents[node]
    result = identity
    parentIndex = -1
    for j in range(len(adjacents[node])):
      if adjacents[node][j] == parent:
        parentIndex = j
        continue
      result = merge(result, childSubtreeRes[node][j])
    if parentIndex >= 0:
      childSubtreeRes[parent][indexForAdjacents[node][parentIndex]] = addNode(result, node)
  for node in order:
    accumsFromTail = [identity]*len(adjacents[node])
    accumsFromTail[len(accumsFromTail)-1] = identity
    for j in range(len(accumsFromTail)-1, 0, -1):
      accumsFromTail[j-1] = merge(childSubtreeRes[node][j], accumsFromTail[j])
    accum = identity
    for j in range(len(accumsFromTail)):
      result = addNode(merge(accum, accumsFromTail[j]), node)
      childSubtreeRes[adjacents[node][j]][indexForAdjacents[node][j]] = result
      accum = merge(accum, childSubtreeRes[node][j])
    nodeRes[node] = addNode(accum, node)
  return nodeRes

n, mod = map(int, input().split())
edge = []
for _ in range(n-1):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  edge.append((x, y))
def merge(a, b):
  return a*b % mod
def addNode(a, id):
  return a+1
for i in ReRooting(n, edge, 1, merge, addNode):
  print(i-1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def dfs1(v, pv):
    for nv in G[v]:
        if nv!=pv:
            st[v] *= dfs1(nv, v)+1
            st[v] %= M
    
    return st[v]
    
def dfs2(v, pv):
    cnt = 0
    l = []
    
    for nv in G[v]:
        if nv==pv:
            left = acc1[pv][idx[pv][v]]
            right = acc2[pv][idx[pv][v]+1]
            l.append((left*right+1)%M)
            rt[v] *= (left*right+1)%M
            rt[v] %= M
        else:
            l.append(st[nv]+1)
            rt[v] *= st[nv]+1
            rt[v] %= M
        
        idx[v][nv] = cnt
        cnt += 1
    
    acc1[v].append(1)
    
    for li in l:
        acc1[v].append(acc1[v][-1]*li%M)
    
    acc2[v].append(1)
    
    for li in l[::-1]:
        acc2[v].append(acc2[v][-1]*li%M)
    
    acc2[v].reverse()
    
    for nv in G[v]:
        if nv!=pv:
            dfs2(nv, v)
        
N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)

st = [1]*N
rt = [1]*N
dfs1(0, -1)

idx = defaultdict(lambda : defaultdict(int))
acc1 = defaultdict(list)
acc2 = defaultdict(list)
dfs2(0, -1)

for v in range(N):
    print(rt[v])

Submission status: Runtime Error

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


def solve(N: int, M: int, adj):
    sub = [0] * N

    def dfs(node, parent):
        r = 1
        for child in adj[node]:
            if child == parent:
                continue
            r = (r * (1 + dfs(child, node))) % M
        sub[node] = r
        return r

    dfs(0, -1)
    ans = [0] * N
    ans[0] = sub[0]

    def dfs2(node, parent):
        if parent != -1:
            ans[node] = sub[node]  # parent is white
            ans[node] += ans[parent] // (sub[node] + 1) * sub[node]

        for child in adj[node]:
            if child == parent:
                continue
            dfs2(child, node)

    dfs2(0, -1)
    return ans


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    adj = [[] for _ in range(N)]
    for i in range(N - 1):
        x = int(next(tokens)) - 1
        y = int(next(tokens)) - 1
        adj[x].append(y)
        adj[y].append(x)
    print(*solve(N, M, adj), sep="\n")


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def reroot(nodeCount, edges, identity, merge, addNode, root=0):
    adjacents = [list() for _ in range(nodeCount)]
    indexForAdjacents = [list() for _ in range(nodeCount)]
    for u, v in edges:
        indexForAdjacents[u].append(len(adjacents[v]))
        indexForAdjacents[v].append(len(adjacents[u]))
        adjacents[u].append(v)
        adjacents[v].append(u)
    childSubtreeRes = [[identity]*len(adjacents[i]) for i in range(nodeCount)]
    nodeRes = [identity]*nodeCount

    parents = [-1]*nodeCount
    order = [0]*nodeCount
    index = 0
    stack = [root]
    while stack:
        node = stack.pop()
        order[index] = node
        index += 1
        for adjacent in adjacents[node]:
            if adjacent == parents[node]:
                continue
            stack.append(adjacent)
            parents[adjacent] = node

    for node in reversed(order):
        parent = parents[node]
        result = identity
        parentIndex = -1
        for j in range(len(adjacents[node])):
            if adjacents[node][j] == parent:
                parentIndex = j
                continue
            result = merge(result, childSubtreeRes[node][j])
        childSubtreeRes[parent][indexForAdjacents[node][parentIndex]] = addNode(result, node)

    for node in order:
        accumsFromTail = [identity]*len(adjacents[node])
        for j in range(len(adjacents[node]) - 1, 0, -1):
            accumsFromTail[j - 1] = merge(childSubtreeRes[node][j], accumsFromTail[j])
        accum = identity
        for j in range(len(adjacents[node])):
            result = addNode(merge(accum, accumsFromTail[j]), node)
            childSubtreeRes[adjacents[node][j]][indexForAdjacents[node][j]] = result
            accum = merge(accum, childSubtreeRes[node][j])
        nodeRes[node] = addNode(accum, node)
    return nodeRes

int1 = lambda x: int(x) - 1
n, mod = map(int, input().split())
if n == 1:
  print(1)
  exit(0)
merge = lambda u, v: u * v % mod
addNode = lambda val, id: val + 1
edges = [tuple(map(int1, input().split())) for _ in range(n-1)]
res = list(map(int1, reroot(n, edges, 1, merge, addNode)))
print(*res, sep='\n')

Submission status: Runtime Error

Solution code:
import sys

input=sys.stdin.readline

N,M=map(int,input().split())
edge={i:[] for i in range(1,N+1)}
for _ in range(N-1):
    x,y=map(int,input().split())
    edge[x].append(y)
    edge[y].append(x)

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

q=set([1])
sub=set([])
while q:
    while q:
        x=q.pop()
        for i in edge[x]:
            if parent[i]==-1:
                parent[i]=x
                sub.add(i)

        if not q:
            q=sub
            sub=set([])
            break


memo={i:-1 for i in range(1,N+1)}
def dfs(num):
    if memo[num]!=-1:
        return memo[num]

    if edge[num]==[parent[num]]:
        return 1

    ans=1
    for i in edge[num]:
        if i!=parent[num]:
            ans=(ans*(dfs(i)+1))

    memo[num]=ans

    return memo[num]

answer={i:-1 for i in range(1,N+1)}
answer[1]=dfs(1)

def all(num):
    if answer[num]!=-1:
        return answer[num]

    x=all(parent[num])
    y=dfs(num)

    answer[num]=(x//(y+1)+1)*y

    return answer[num]

for i in range(1,N+1):
    print(all(i)%M)

Submission status: Runtime Error

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

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

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

G = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    G[x].append(y)
    G[y].append(x)

DP1 = [-1] * (N + 1)
DP1[0] = 1
parent = [-1] * (N + 1)
parent[1] = 0

def dfs(x, p):
    tmp = 1
    for next_ in G[x]:
        if next_ == p:
            continue
        parent[next_] = x
        tmp *= (dfs(next_, x) + 1)
        # tmp %= MOD
    DP1[x] = tmp
    return tmp

dfs(1, 0)
# print (DP1)

DP2 = [-1] * (N + 1)
DP2[0] = 1
DP2[1] = 1
stack = [1]

while stack:
    x = stack.pop()
    for next_ in G[x]:
        if DP2[next_] != -1:
            continue
        tmp = DP1[x]
        tmp //= (DP1[next_] + 1)
        tmp *= DP2[parent[next_]]
        tmp += 1 #白色の分
        DP2[next_] = tmp
        stack.append(next_)

# print (DP2)

for i in range(1, N + 1):
    print (DP1[i] * DP2[i] % MOD)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7
INF = 10 ** 10

MAXN = 100005
G = [[] for _ in range(MAXN)]
dp = [[] for _ in range(MAXN)]
deg = [0] * MAXN
parents = [-1] * MAXN
result = [0] * MAXN

def dfs1(v,mod,p = -1):
    ans = 1
    for i in range(deg[v]):
        e = G[v][i]
        if e == p:
            parents[e] = i
            continue
        dp[v][i][1] = dfs1(e,mod,v)
        ans *= dp[v][i][0] + dp[v][i][1]
        ans %= mod
    return ans%mod

def dfs2(v,mod,res_p = 1,p = -1):
    if p != -1:
        dp[v][parents[v]][1] = res_p
    cuml = [1] * (deg[v] + 1)
    cumr = [1] * (deg[v] + 1)
    for i in range(deg[v]):
        cuml[i + 1] = cuml[i] * (dp[v][i][0] + dp[v][i][1]) % mod
    for i in range(deg[v] - 1,-1,-1):
        cumr[i] = cumr[i + 1] * (dp[v][i][0] + dp[v][i][1]) % mod
    result[v] = cumr[0]
    for i in range(deg[v]):
        e = G[v][i]
        if e == p:
            continue
        dfs2(e,mod,cuml[i] * cumr[i + 1] % mod,v)

def main():
    n,m = map(int,input().split())
    for _ in range(n - 1):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        G[x].append(y)
        G[y].append(x)
    
    for i in range(n):
        deg[i] = len(G[i])
        dp[i] = [[1] * 2 for _ in range(deg[i])]
    
    dfs1(0,m)
    dfs2(0,m)
    for i in range(n):
        print(result[i])      

if __name__=='__main__':
    main()

Submission status: Runtime Error

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 accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, M = MAP()
mod = M

tree = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
	a, b = MAP()
	tree[a].append(b)
	tree[b].append(a)

root = 1
parent = [0]*(N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in tree[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

dp_d = [0]*(N+1)

for v in order[::-1]:
    x = 1
    for node in tree[v]:
        x = (x * (dp_d[node]+1))%mod
    dp_d[v] = x

dp_u = [0]*(N+1)
for v in order:
    p = parent[v]
    val = [dp_d[node]+1 if node != p else dp_u[v] for node in tree[v]]
    left = [1] + list(accumulate(val, lambda x, y: x*y%mod))[:-1] # 左累積和
    right = list(accumulate(val, lambda x, y: x*y%mod))[-2::-1] + [1] # 右累積和
    contrib = [x*y%mod for x, y in zip(left, right)]
    for node, c in zip(tree[v], contrib):
        if node != p:
            dp_u[node] = 1+c

ans = []
for xd, xu in zip(dp_d[1:], dp_u[1:]):
    ans.append(xd*xu%mod)
print(*ans, sep="\n")

Submission status: Runtime Error

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

def main():
    n,m = map(int,input().split())
    ans=[0]*n
    nodes=[[]for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        nodes[a-1].append(b-1)
        nodes[b-1].append(a-1)

    dp=[[]for _ in range(n)]
    dpl=[[]for _ in range(n)]
    dpr=[[]for _ in range(n)]
    aro=[-1]*n

    def rec(n,p):#黒の時のサブツリー
        aro[n]=p
        dp[n]=[1]*len(nodes[n])
        for i,M in enumerate(nodes[n]):
            if M==p:
                continue
            dp[n][i]=rec(M,n)+1
        dpr[n]=[1]*len(dp[n])#最後は1
        dpl[n]=[1]*len(dp[n])#最初は1
        for i in range(len(dp[n])-1):
            dpl[n][i]=(dp[n][i]*dpl[n][i-1])%m
        for i in range(len(dp[n])-1,0,-1):
            dpr[n][i]=(dp[n][i]*dpr[n][(i+1)%len(dp[n])])%m
        if len(dp[n])==1:
            return dp[n][0]
        return (dp[n][0]*dpr[n][1])
    def ansering(n,mult):
        for i,N in enumerate(nodes[n]):
            if N==aro[n]:
                continue
            MM=(dpl[n][i-1]*dpr[n][(i+1)%len(dp[n])]*mult+1)%m
            ansering(N,MM)
        if len(dp[n])==1:
            ans[n]=(dp[n][0]*mult)%m
        else:
            ans[n]=(dp[n][0]*dpr[n][1]*mult)%m
    if n==1:
        print(1)
    else:
        rec(0,-1)
        ansering(0,1)
        for i in ans:
            print(i)
main()

Submission status: Runtime Error

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

def main():
    n,m = map(int,input().split())
    ans=[0]*n
    nodes=[[]for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        nodes[a-1].append(b-1)
        nodes[b-1].append(a-1)

    dp=[[]for _ in range(n)]
    dpl=[[]for _ in range(n)]
    dpr=[[]for _ in range(n)]
    aro=[-1]*n

    def rec(n,p):#黒の時のサブツリー
        aro[n]=p
        dp[n]=[1]*len(nodes[n])
        for i,M in enumerate(nodes[n]):
            if M==p:
                continue
            dp[n][i]=rec(M,n)+1
        dpr[n]=[1]*len(dp[n])#最後は1
        dpl[n]=[1]*len(dp[n])#最初は1
        for i in range(len(dp[n])-1):
            dpl[n][i]=(dp[n][i]*dpl[n][i-1])%m
        for i in range(len(dp[n])-1,0,-1):
            dpr[n][i]=(dp[n][i]*dpr[n][(i+1)%len(dp[n])])%m
        if len(dp[n])==1:
            return dp[n][0]
        return (dp[n][0]*dpr[n][1])
    def ansering(n,mult):
        for i,N in enumerate(nodes[n]):
            if N==aro[n]:
                continue
            MM=(dpl[n][i-1]*dpr[n][(i+1)%len(dp[n])]*mult+1)%m
            ansering(N,MM)
        if len(dp[n])==1:
            ans[n]=(dp[n][0]*mult)%m
        else:
            ans[n]=(dp[n][0]*dpr[n][1]*mult)%m
    if n==1:
        print(1)
    else:
        rec(0,-1)
        ansering(0,1)
        for i in ans:
            print(i)
main()

Submission status: Runtime Error

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

n,m = map(int,input().split())
ans=[0]*n
nodes=[[]for _ in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)

dp=[[]for _ in range(n)]
dpl=[[]for _ in range(n)]
dpr=[[]for _ in range(n)]
aro=[-1]*n

def rec(n,p):#黒の時のサブツリー
    aro[n]=p
    dp[n]=[1]*len(nodes[n])
    for i,M in enumerate(nodes[n]):
        if M==p:
            continue
        dp[n][i]=rec(M,n)+1
    dpr[n]=[1]*len(dp[n])#最後は1
    dpl[n]=[1]*len(dp[n])#最初は1
    for i in range(len(dp[n])-1):
        dpl[n][i]=(dp[n][i]*dpl[n][i-1])%m
    for i in range(len(dp[n])-1,0,-1):
        dpr[n][i]=(dp[n][i]*dpr[n][(i+1)%len(dp[n])])%m
    if len(dp[n])==1:
        return dp[n][0]
    return (dp[n][0]*dpr[n][1])
def ansering(n,mult):
    for i,N in enumerate(nodes[n]):
        if N==aro[n]:
            continue
        MM=(dpl[n][i-1]*dpr[n][(i+1)%len(dp[n])]*mult+1)%m
        ansering(N,MM)
    if len(dp[n])==1:
        ans[n]=(dp[n][0]*mult)%m
    else:
        ans[n]=(dp[n][0]*dpr[n][1]*mult)%m
rec(0,-1)
ansering(0,1)
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


N, M = map(int, input().split())
tree = [[] for i in range(N+1)]
for i in range(N-1):
  x, y = map(int, input().split())
  tree[x].append(y)
  tree[y].append(x)

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
parents = [-1] * (N+1)
leaf_nodes = []

def solve1(node, parent):
  global dp1
  global parents
  global leaf_nodes
  parents[node] = parent
  if dp1[node] > 0:
    return dp1[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        continue
      
      t *= (solve1(child, node) + 1)
      t %= M
    
    if t == 1:
      leaf_nodes.append(node)
    
    dp1[node] = t
    return t


def solve2(node):
  global dp2
  global parents
  parent = parents[node]
  if dp2[node] > 0:
    return dp2[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        t *= (solve2(parent)//(dp1[node] + 1) + 1)
      else:
        t *= (dp1[child] + 1)
    
    dp2[node] = t
    return t
  

_ = solve1(1, 0)
for leaf in leaf_nodes:
  _ = solve2(leaf)


for ans in dp2[1:]:
  print(ans%M)

Submission status: Runtime Error

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

tree = [[] for i in range(N+1)]
for i in range(N-1):
  x, y = map(int, input().split())
  tree[x].append(y)
  tree[y].append(x)

dp1 = [0] * (N+1)
dp2 = [0] * (N+1)
parents = [-1] * (N+1)
leaf_nodes = []

def solve1(node, parent):
  global dp1
  global parents
  global leaf_nodes
  parents[node] = parent
  if dp1[node] > 0:
    return dp1[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        continue
      
      t *= (solve1(child, node) + 1)
      t %= M
    
    if t == 1:
      leaf_nodes.append(node)
    
    dp1[node] = t
    return t


def solve2(node):
  global dp2
  global parents
  parent = parents[node]
  if dp2[node] > 0:
    return dp2[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        t *= (solve2(parent)//(dp1[node] + 1) + 1)
        t %= M
      else:
        t *= (dp1[child] + 1)
        t %= M
    
    dp2[node] = t
    return t
  

_ = solve1(1, 0)
for leaf in leaf_nodes:
  _ = solve2(leaf)

print(*dp2[1:], sep='\n')

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=[set()for i in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    s[x-1].add(y-1)
    s[y-1].add(x-1)
if n==1:
   print(1)
   exit()
l=[None]*n
r=[None]*n
def dfs(a=0,b=None):
    s[a].discard(b)
    l[a]=[1]*(len(s[a])+1)
    r[a]=[1]*(len(s[a])+1)
    g=[dfs(i,a)+1for i in s[a]]
    for i,x in enumerate(g,1):
        l[a][i]=l[a][i-1]*x%m
    for i,x in enumerate(g,1):
        r[a][-i-1]=r[a][-i]*x%m
    return l[a][-1]
dfs()
dp=[None]*n
q=[(0,1)]
while q:
    x,y=q.pop()
    dp[x]=y*l[x][-1]%m
    for i,j,h in zip(s[x],l[x][:-1],r[x][1:]):
        q.append((i,y*j*h%m+1))
for i in dp:
    print(i)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
s=[set()for i in range(n)]
for i in range(n-1):
    x,y=map(int,input().split())
    s[x-1].add(y-1)
    s[y-1].add(x-1)
if n==1:
   print(1)
   exit()
l=[None]*n
r=[None]*n
def dfs(a=0,b=None):
    s[a].discard(b)
    l[a]=[1]*(len(s[a])+1)
    r[a]=[1]*(len(s[a])+1)
    g=[dfs(i,a)+1for i in s[a]]
    for i,x in enumerate(g,1):
        l[a][i]=l[a][i-1]*x%m
    for i,x in enumerate(g,1):
        r[a][-i-1]=r[a][-i-1]*x%m
    return l[a][-1]
dfs()
dp=[None]*n
q=[(0,1)]
while q:
    x,y=q.pop()
    dp[x]=y*l[x][-1]%m
    for i,j,h in zip(s[x],l[x][:-1],r[x][1:]):
        q.append((i,y*j*h%m+1))
for i in dp:
    print(i)