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: Accepted

Solution code:
def main():
    n, mod = [int(x) for x in input().split()]

    coupl = [[] for _ in range(n)]
    for _ in range(n-1):
        u,v = [int(x)-1 for x in input().split()]
        coupl[u].append(v)
        coupl[v].append(u)

    subtree_memo = [-1]*n
    @bootstrap
    def subtrees_with_black_root(node, parent):
        if subtree_memo[node] == -1:
            ways = 1
            for nei in coupl[node]:
                if nei != parent:
                    ways = ways * (1 + \
                            (yield subtrees_with_black_root(nei, node)) \
                            ) % mod
            subtree_memo[node] = ways
        yield subtree_memo[node]

    
    ans = [-1]*n
    @bootstrap
    def solve(node, parent, ways_to_color_parent_black):
        # tell all children of node
        # the number of ways it is possible 
        # to color their parent (node) black
        A = []
        for nei in coupl[node]:
            if nei != parent:
                A.append(1 + (yield subtrees_with_black_root(nei, node)))
            else:
                A.append(1 + ways_to_color_parent_black)

        prefix = [1]
        for a in A:
            prefix.append(prefix[-1] * a % mod)
        suffix = [1]
        for a in reversed(A):
            suffix.append(suffix[-1] * a % mod)

        for i, nei in enumerate(coupl[node]):
            if nei != parent:
                yield solve(nei, node, prefix[i] * suffix[~i-1] % mod)
        ans[node] = (yield subtrees_with_black_root(node, parent)) \
                * (ways_to_color_parent_black + 1) % mod
        yield
    solve(0, -1, 0)

    print ' '.join(str(x) for x in ans)


# Magic stackless recursion =D
# Should be fast enough for > 10^6 
# recursive calls in < 1 s in PyPy
from types import GeneratorType
def bootstrap(func, stack=[]):
    def wrapped_function(*args, **kwargs):
        if stack:
            return func(*args, **kwargs)
        else:
            call = func(*args, **kwargs)
            while True:
                if type(call) is GeneratorType:
                    stack.append(call)
                    call = next(call)
                else:
                    stack.pop()
                    if not stack:
                        break
                    call = stack[-1].send(call)
            return call

    return wrapped_function


######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using bytestrings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__== "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, mod = [int(x) for x in input().split()]

    coupl = [[] for _ in range(n)]
    for _ in range(n-1):
        u,v = [int(x)-1 for x in input().split()]
        coupl[u].append(v)
        coupl[v].append(u)

    subtree_memo = [-1]*n
    @bootstrap
    def subtrees_with_black_root(node, parent):
        if subtree_memo[node] == -1:
            ways = 1
            for nei in coupl[node]:
                if nei != parent:
                    ways = ways * (1 + \
                            (yield subtrees_with_black_root(nei, node)) \
                            ) % mod
            subtree_memo[node] = ways
        yield subtree_memo[node]

    ways_to_color_parent_black = [0]*n
    @bootstrap
    def tell_children(node, parent):
        # tell all children of node
        # the number of ways it is possible 
        # to color their parent (node) black
        A = []
        for nei in coupl[node]:
            if nei != parent:
                A.append(1 + (yield subtrees_with_black_root(nei, node)))
            else:
                A.append(1 +  ways_to_color_parent_black[node])

        prefix = [1]
        for a in A:
            prefix.append(prefix[-1] * a % mod)
        suffix = [1]
        for a in reversed(A):
            suffix.append(suffix[-1] * a % mod)

        for i, nei in enumerate(coupl[node]):
            if nei != parent:
                ways_to_color_parent_black[nei] = prefix[i] * suffix[~i-1] % mod
        
        for nei in coupl[node]:
            if nei != parent:    
                yield tell_children(nei, node)
        yield
    tell_children(0, -1)

    ans = [-1]*n
    @bootstrap
    def solve(node, parent):
        ans[node] = (yield subtrees_with_black_root(node, parent)) \
                * (1 + ways_to_color_parent_black[node]) % mod
        
        for nei in coupl[node]:
            if nei != parent:    
                yield solve(nei, node)
        yield
    solve(0, -1)

    print ' '.join(str(x) for x in ans)


# Magic stackless recursion =D
# Should be fast enough for > 10^6 
# recursive calls in < 1 s in PyPy
from types import GeneratorType
def bootstrap(func, stack=[]):
    def wrapped_function(*args, **kwargs):
        if stack:
            return func(*args, **kwargs)
        else:
            call = func(*args, **kwargs)
            while True:
                if type(call) is GeneratorType:
                    stack.append(call)
                    call = next(call)
                else:
                    stack.pop()
                    if not stack:
                        break
                    call = stack[-1].send(call)
            return call

    return wrapped_function


######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using bytestrings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__== "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, mod = [int(x) for x in input().split()]

    coupl = [[] for _ in range(n)]
    for _ in range(n-1):
        u,v = [int(x)-1 for x in input().split()]
        coupl[u].append(v)
        coupl[v].append(u)

    subtree_memo = [-1]*n
    @bootstrap
    def subtrees_with_black_root(node, parent):
        if subtree_memo[node] == -1:
            ways = 1
            for nei in coupl[node]:
                if nei != parent:
                    ways = ways * (1 + \
                            (yield subtrees_with_black_root(nei, node)) \
                            ) % mod
            subtree_memo[node] = ways
        yield subtree_memo[node]

    ways_to_color_parent_black = [0]*n
    @bootstrap
    def tell_children(node, parent):
        # tell all children of node
        # the number of ways it is possible 
        # to color their parent (node) black
        A = []
        for nei in coupl[node]:
            if nei != parent:
                A.append(1 + (yield subtrees_with_black_root(nei, node)))
            else:
                A.append(1 +  ways_to_color_parent_black[node])

        prefix = [1]
        for a in A:
            prefix.append(prefix[-1] * a % mod)
        suffix = [1]
        for a in reversed(A):
            suffix.append(suffix[-1] * a % mod)

        for i, nei in enumerate(coupl[node]):
            if nei != parent:
                ways_to_color_parent_black[nei] = prefix[i] * suffix[~i-1] % mod
                yield tell_children(nei, node)
        yield
    tell_children(0, -1)

    ans = [-1]*n
    @bootstrap
    def solve(node, parent):
        ans[node] = (yield subtrees_with_black_root(node, parent)) \
                * (1 + ways_to_color_parent_black[node]) % mod
        
        for nei in coupl[node]:
            if nei != parent:    
                yield solve(nei, node)
        yield
    solve(0, -1)

    print ' '.join(str(x) for x in ans)


# Magic stackless recursion =D
# Should be fast enough for > 10^6 
# recursive calls in < 1 s in PyPy
from types import GeneratorType
def bootstrap(func, stack=[]):
    def wrapped_function(*args, **kwargs):
        if stack:
            return func(*args, **kwargs)
        else:
            call = func(*args, **kwargs)
            while True:
                if type(call) is GeneratorType:
                    stack.append(call)
                    call = next(call)
                else:
                    stack.pop()
                    if not stack:
                        break
                    call = stack[-1].send(call)
            return call

    return wrapped_function


######## Python 2 and 3 footer by Pajenegod and c1729

# Note because cf runs old PyPy3 version which doesn't have the sped up
# unicode strings, PyPy3 strings will many times be slower than pypy2.
# There is a way to get around this by using bytestrings in PyPy3
# but its syntax is different which makes it kind of a mess to use.

# So on cf, use PyPy2 for best string performance.

py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange

import os, sys
from io import IOBase, BytesIO

BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')

if __name__== "__main__":
    main()

Submission status: Accepted

Solution code:


n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)


cola = [(0, -1)]
qind = 0
while qind < len(cola):
    u, pu = cola[qind]
    qind += 1
    for v in tree[u]:
        if v != pu:
            cola.append((v, u))

dp = [1] * n
for i in range(n - 1, -1, -1):
    u, pu = cola[i]
    for v in tree[u]:
        if v != pu:
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

resp = [0] * n
pval = [1] * n
for j in range(n):
    u, pu = cola[j]
    resp[u] = (dp[u] * pval[u]) % MOD

    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval[u]
    for i in range(len(chlds)):
        v = chlds[i]
        pval[v] = (1 + pref * cumulr[i]) % MOD
        pref *= (dp[v] + 1)
        pref %= MOD

for i in range(n):
    print(resp[i])

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100000)


def dfs1(v, p):
    val = 1
    pre_mul = [1]
    rev_mul = []
    for c in links[v]:
        if c == p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res = 1 + dfs1(c, v)
        val *= res
        val %= m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v] = val
    for i in range(len(rev_mul) - 2, -1, -1):
        rev_mul[i] *= rev_mul[i + 1]
        rev_mul[i] %= m
    rev_mul.append(1)
    pre_muls[v] = [pre_mul, rev_mul]
    return val


def dfs2(v, p, a):
    dp[v] = dp[v] * a % m
    pmv = pre_muls[v]
    for i, c in enumerate(links[v]):
        if c == p:
            continue
        pmc = pmv[0][i] * pmv[1][i + 1] % m
        pmc = pmc * a % m
        dfs2(c, v, pmc + 1)


n, m = map(int, input().split())
links = [[] for _ in range(n)]
dp = [0 for _ in range(n)]
pre_muls = [None for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].append(y)
    links[y].append(x)
dfs1(0, None)
dfs2(0, None, 1)
print('\n'.join(map(str, dp)))

Submission status: Accepted

Solution code:
import sys
from collections import deque

readline = sys.stdin.readline

N, M = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, readline().split())
    G[x-1].append((y-1, 2*i))
    G[y-1].append((x-1, 2*i+1))

G0 = [None]*N
V = [(0, -1)]
used = [0]*N
used[0] = 1
que = deque([0])
while que:
    v = que.popleft()
    g = []
    for e in G[v]:
        w, d = e
        if used[w]:
            continue
        g.append(e)
        V.append(e)
        used[w] = 1
        que.append(w)
    G0[v] = g

memo = [0]*(2*N+1)
for v, e in reversed(V):
    r = 1
    for w, d in G0[v]:
        r = r * (1 + memo[d]) % M
    memo[e] = r

lv = [0]*(2*N); rv = [0]*(2*N)
for v, e in V:
    s = 1 + memo[e ^ 1]
    for w, d in G0[v]:
        lv[d] = s
        s = s * (1 + memo[d]) % M
    s = 1
    for w, d in reversed(G0[v]):
        rv[d] = s
        s = s * (1 + memo[d]) % M
    for w, d in G0[v]:
        memo[d ^ 1] = lv[d] * rv[d] % M

ans = []
for v in range(N):
    r = 1
    for w, d in G[v]:
        r = r * (1 + memo[d]) % M
    ans.append("%d\n" % r)
sys.stdout.writelines(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate, combinations
from functools import lru_cache

M = mod = 100000000019
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




n, m = li()

if n == 1:
    print(1 % m)
    exit()

g = defaultdict(set)

for i in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


for i in g:
    if len(g[i]) == 1:
        root = i
        break

dp = [0] * (n + 1)

def dfs(root = 1, par = -1):
    global dp
    currval = 1
    atleast1 = 0
    for j in g[root]:
        if j != par:
            atleast1 = 1
            currval = (currval * (1 + dfs(j, root))) % mod
    
    if not atleast1:ans = 1 % mod
    else:ans = (currval) % mod

    dp[root] = ans
    return ans

def dfs2(root, par):
    # print(root, par, dp[root], dp[par])


    dp[root] = dp[root] * (dp[par] * inv_mod(dp[root] + 1) + 1  )
    dp[root] = dp[root] % mod
    for j in g[root]:
        if j != par:dfs2(j, root)



dfs(root, -1)



dfs2(g[root].pop(), root)



for i in dp[1:]:print(i % m)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate, combinations
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




n, m = li()

if n == 1:
    print(1 % m)
    exit()

g = defaultdict(set)

for i in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


for i in g:
    if len(g[i]) == 1:
        root = i
        break

dp = [0] * (n + 1)

def dfs(root = 1, par = -1):
    global dp
    currval = 1
    atleast1 = 0
    for j in g[root]:
        if j != par:
            atleast1 = 1
            currval = (currval * (1 + dfs(j, root))) % mod
    
    if not atleast1:ans = 1 % mod
    else:ans = (currval) % mod

    dp[root] = ans
    return ans

def dfs2(root, par):
    # print(root, par, dp[root], dp[par])


    dp[root] = dp[root] * (dp[par] * inv_mod(dp[root] + 1) + 1  )
    dp[root] = dp[root] % mod
    for j in g[root]:
        if j != par:dfs2(j, root)



dfs(root, -1)



dfs2(g[root].pop(), root)



for i in dp[1:]:print(i % m)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate, combinations
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


mod = 10 ** 9 + 7

n, m = li()

if n == 1:
    print(1 % mod)
    exit()

g = defaultdict(set)

for i in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


for i in g:
    if len(g[i]) == 1:
        root = i
        break

dp = [0] * (n + 1)

def dfs(root = 1, par = -1):
    global dp
    currval = 1
    atleast1 = 0
    for j in g[root]:
        if j != par:
            atleast1 = 1
            currval = (currval * (1 + dfs(j, root))) % mod
    
    if not atleast1:ans = 1 % mod
    else:ans = (currval) % mod

    dp[root] = ans
    return ans

def dfs2(root, par):
    # print(root, par, dp[root], dp[par])


    dp[root] = dp[root] * (dp[par] * inv_mod(dp[root] + 1) + 1  )
    dp[root] = dp[root] % mod
    for j in g[root]:
        if j != par:dfs2(j, root)



dfs(root, -1)



dfs2(g[root].pop(), root)



for i in dp[1:]:print(i % m)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate, combinations
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




n, m = li()

if n == 1:
    print(1 % mod)
    exit()

g = defaultdict(set)

for i in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


for i in g:
    if len(g[i]) == 1:
        root = i
        break

dp = [0] * (n + 1)

def dfs(root = 1, par = -1):
    global dp
    currval = 1
    atleast1 = 0
    for j in g[root]:
        if j != par:
            atleast1 = 1
            currval = (currval * (1 + dfs(j, root))) % mod
    
    if not atleast1:ans = 1 % mod
    else:ans = (currval) % mod

    dp[root] = ans
    return ans

def dfs2(root, par):
    # print(root, par, dp[root], dp[par])


    dp[root] = dp[root] * (dp[par] * inv_mod(dp[root] + 1) + 1  )
    dp[root] = dp[root] % mod
    for j in g[root]:
        if j != par:dfs2(j, root)



dfs(root, -1)



dfs2(g[root].pop(), root)



for i in dp[1:]:print(i % m)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate, combinations
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]




n, mod = li()

if n == 1:
    print(1 % mod)
    exit()

g = defaultdict(set)

for i in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


for i in g:
    if len(g[i]) == 1:
        root = i
        break

dp = [0] * (n + 1)

def dfs(root = 1, par = -1):
    global dp
    currval = 1
    atleast1 = 0
    for j in g[root]:
        if j != par:
            atleast1 = 1
            currval = (currval * (1 + dfs(j, root))) % mod
    
    if not atleast1:ans = 1 % mod
    else:ans = (currval) % mod

    dp[root] = ans
    return ans

def dfs2(root, par):
    dp[root] = (dp[root] * (dp[par] //(dp[root] + 1) + 1) % mod) % mod

    for j in g[root]:
        if j != par:dfs2(j, root)




dfs(root, -1)


# for i in range(1, n + 1):
#     print(i, dp[i])

# print('\n\n')
dfs2(g[root].pop(), root)



for i in dp[1:]:print(i)

Submission status: Runtime Error

Solution code:
def dfs(v,p):
    if res_v[v]!=-1:
        return res_v[v]
    size[v]=len(G[v])
    dp[v]=[0]*size[v]
    res=1
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            p_i[v]=i
            continue
        R=dfs(nv,v)
        dp[v][i]=R
        res=res*(R+1)%MOD
    return res
    
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][p_i[v]]=res_p
    for i in range(size[v]):
        ans[v]=ans[v]*(dp[v][i]+1)%MOD
    dp_L=[1]*(size[v]+1)
    dp_R=[1]*(size[v]+1)
    for i in range(size[v]):
        dp_L[i+1]=dp_L[i]*(dp[v][i]+1)%MOD
    for i in reversed(range(size[v])):
        dp_R[i]=dp_R[i+1]*(dp[v][i]+1)%MOD
        
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            continue
        reroot(nv,dp_L[i]*dp_R[i+1]%MOD,v)

N,MOD=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
res_v=[-1]*N
dp=[[] for i in range(N)]
size=[-1]*N
p_i=[-1]*N
dp_L=[[] for i in range(N)]
dp_R=[[] for i in range(N)]
ans=[1]*N

z_root=dfs(0,-1)
res_v[0]=z_root
reroot(0,0,-1)
print(*ans,sep='\n')