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 .

Solution (Python):
from collections import deque
import sys
sys.setrecursionlimit(10**9 + 7)


def dfs1(pos, par, e=1):
    """dfsを用いて前計算する"""
    for child in tree[pos]:
        if child == par:
            continue
        tmp = st_val[child]
        e *= (1 + tmp)
        e %= MOD
    st_val[pos] = e
    return st_val[pos]


def dfs2(pos, par, e=1):
    """全方位木DP"""
    for child in tree[pos]:
        if child == par:
            ind = compress[par][pos]
            tmp = ruiseki_l[par][ind] * ruiseki_r[par][len(tree[par]) - ind - 1]
        else:
            tmp = st_val[child]
        e *= (1 + tmp)
        e %= MOD
        ind = compress[pos][child]
        re_subtree_val[pos][ind] = 1 + tmp

    for i in range(len(tree[pos])):
        ruiseki_l[pos][i + 1] = ruiseki_l[pos][i] * re_subtree_val[pos][i]
        ruiseki_l[pos][i + 1] %= MOD
    for i in range(len(tree[pos])):
        ruiseki_r[pos][i + 1] = ruiseki_r[pos][i] * re_subtree_val[pos][-i-1]
        ruiseki_r[pos][i + 1] %= MOD
    ans[pos] = e



def topological_sort(root, par=-1):
    q = deque([(root, par)])
    res = [(root, par)]
    while q:
        pos, par = q.pop()
        for child in tree[pos]:
            if child == par:
                continue
            else:
                q.append((child, pos))
                res.append((child, pos))
    return res


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


preorder_list = topological_sort(0, par=-1)


st_val = [0] * n
for pos, par in reversed(preorder_list):
    dfs1(pos, par)


re_subtree_val = [[1] * len(tree[i]) for i in range(n)]


ruiseki_l = [[1] * (len(tree[i]) + 1) for i in range(n)]
ruiseki_r = [[1] * (len(tree[i]) + 1) for i in range(n)]

compress = [{v: j for j, v in enumerate(tree[i])} for i in range(n)]
ans = [0]*n
for pos, par in preorder_list:
    dfs2(pos, par)

for i in range(n):
    print(ans[i] % MOD)

Solution (Python):
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)

dp = {}

def dfs(u=0, pu=-1):
    res = 1
    for v in to[u]:
        if v == pu: continue
        res *= dfs(v, u) + 1
        res %= m
    if pu != -1: dp[(pu,u)] = res
    return res

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    dfs()
    
    que = deque()
    que.append([0, -1])
    while que:
        u, pu = que.popleft()
        tn = len(to[u])
        
        ll = [0] * tn
        rr = [0] * tn
        
        for i, v in enumerate(to[u]):
            ll[i] = rr[i] = dp[(u,v)] + 1
        
        for i in range(1, tn):
            ll[i] = (ll[i - 1] * ll[i]) % m
            rr[tn - 1 - i] = (rr[tn - i] * rr[tn - 1 - i]) % m
        
        ll += [1]
        rr += [1]
        
        for i, v in enumerate(to[u]):
            if v == pu: continue
            dp[(v,u)] = (ll[i - 1] * rr[i + 1]) % m
            que.append([v, u])
    
    
    for u in range(n):
        ans = 1
        for v in to[u]:
            ans = (ans * (dp[(u,v)] + 1)) % m
        print(ans)

main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N,MOD = map(int,readline().split())
m = map(int,read().split())
XY = zip(m,m)

mult = lambda x,y: x*y%MOD

graph = [[] for _ in range(N+1)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

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


dp1 = [0]*(N+1)

for v in order[::-1]:
    x = 1
    for w in graph[v]:
        x *= dp1[w]+1
        x %= MOD
    dp1[v] = x


dp2 = [1]*(N+1)

for v in order:
    p = parent[v]
    arr = [dp1[c]+1 if c != p else dp2[v] for c in graph[v]]
    
    from_left = [1] + list(itertools.accumulate(arr,mult))[:-1]
    from_right = list(itertools.accumulate(reversed(arr),mult))[-2::-1] + [1]
    prod = [x*y%MOD for x,y in zip(from_left,from_right)]
    for c,x in zip(graph[v],prod):
        if c != p:
            dp2[c] = 1+x

answer = '\n'.join(str(x*y%MOD) for x,y in zip(dp1[1:],dp2[1:]))
print(answer)

Solution (Python):
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)))

Solution (Python):

from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


def get_par_tree(tree: list, par: int) -> list:
    """親を求める"""
    n = len(tree)
    ans = [-1] * n
    visited = [False] * n
    visited[par] = True
    q = deque([par])
    while q:
        pos = q.popleft()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            visited[next_pos] = True
            ans[next_pos] = pos
            q.append(next_pos)
    return ans


def topological_sort_tree(tree: list, par) -> list:
    n = len(tree)
    ans = [par]
    visited = [False] * n
    visited[par] = True
    q = deque([par])
    while q:
        pos = q.popleft()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            visited[next_pos] = True
            ans.append(next_pos)
            q.append(next_pos)
    return ans


def dfs1():
    """その頂点の部分木での黒色で塗るパターンを求める"""
    visited = [False] * n
    for pos in tp_list[::-1]:
        visited[pos] = True
        for next_pos in graph[pos]:
            if visited[next_pos]:
                continue
            b1[next_pos] *= (1 + b1[pos])
            b1[next_pos] %= MOD


def dfs2():
    """全方位木DP"""
    for pos in tp_list:
        cnt = 0
        b = 1
        par = par_list[pos]
        for next_pos in graph[pos]:
            if next_pos == par:
                d = child_pos[par][pos]
                tmp_b = ruiseki_child_l[par][d] * ruiseki_child_r[par][-d-2]
                tmp_b %= MOD
                b *= (1 + tmp_b)
                b %= MOD
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + tmp_b)
                cnt += 1
            else:
                b *= (1 + b1[next_pos])
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + b1[next_pos])
                cnt += 1
                b %= MOD
        b2[pos] = b
        ruiseki_child_l[pos] += child_val[pos] 
        ruiseki_child_r[pos] += child_val[pos][::-1]
        for i in range(len(child_val[pos])):
            ruiseki_child_r[pos][i+1] = ruiseki_child_r[pos][i] * ruiseki_child_r[pos][i+1]
            ruiseki_child_l[pos][i+1] = ruiseki_child_l[pos][i] * ruiseki_child_l[pos][i+1]
            ruiseki_child_r[pos][i+1] %= MOD
            ruiseki_child_l[pos][i+1] %= MOD


n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
dag = [[] for i in range(n)]

for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[b].append(a)
    graph[a].append(b)

par_list = get_par_tree(graph, 0)
tp_list = topological_sort_tree(graph, 0)
b1 = [1] * n
dfs1()

child_pos = defaultdict(lambda :defaultdict(dict))
child_val = [[] for i in range(n)]
ruiseki_child_l = [[1] for i in range(n)]
ruiseki_child_r = [[1] for i in range(n)]
b2 = [0] * n
dfs2()

for num in b2:
    print(num % MOD)

Solution (Python):


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

n,MOD = [int(i) for i in input().split()]

to = [[] for _ in [0]*n]
for _ in range(n-1):
    x,y = [int(i)-1 for i in input().split()]
    to[x].append(y)
    to[y].append(x)


dp = [[0]*len(to_i) for to_i in to]
parent_index = [-9999]*n 
ans = [0]*n

def dfs(v, p):
    res = 1
    for i, vc in enumerate(to[v]):
        if vc == p:
            parent_index[v] = i
            continue
        dp[v][i] = dfs(vc, v)
        res *= dp[v][i]+1
        res %= MOD
    return res

def dfs2(v, res_p, p):
    deg = len(to[v])
    if p >= 0:
        dp[v][parent_index[v]] = res_p

    accl = [1]*(deg+1)
    accr = [1]*(deg+1)

    for i in range(1, deg+1):
        accl[i] = accl[i-1] * (dp[v][i-1] + 1) % MOD
        accr[-i-1] = accr[-i] * (dp[v][-i] + 1) % MOD

    ans[v] = accr[0]
    for i,vc in enumerate(to[v]):
        if vc == p: continue
        dfs2(vc, accl[i]*accr[i+1]%MOD, v)

dfs(0,-1)

dfs2(0,0,-1)

for i in ans:
    print(i)

Solution (Python):
import itertools
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N)]
for row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

ldp = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    
    graph[v].discard(parent)
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

dp = [None] * N
q = [(0,1)]
while q:
    v,x = q.pop()
    dp[v] = x*ldp[v][-1]%MOD
    for w,L,R in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        q.append((w,x*L*R%MOD+1))

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

Solution (Python):
import sys
        
def getpar(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[0] = -1
    par[p]  -1
    stack = [p]
    visited = set([p])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            stack.append(vf)
    return par

def topological_sort_tree(E, r):
    Q = [r]
    L = []
    visited = set([r])
    while Q:
        vn = Q.pop()
        L.append(vn)
        for vf in E[vn]:
            if vf not in visited:
                visited.add(vf)
                Q.append(vf)
    return L

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


        

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

P = getpar(Edge, 0)
L = topological_sort_tree(Edge, 0)
C = getcld(P)

dp1 = [1]*N
for l in L[N-1:0:-1]:
    p = P[l]
    dp1[p] = (dp1[p]*(dp1[l]+1)) % M

dp2 = [1]*N
dp2[0] = dp1[0]
info = [0]*(N+1)

vidx = [0]*N
vmull = [None]*N
vmulr = [None]*N
for i in range(N):
    Ci = C[i]
    res = [1]
    for j, c in enumerate(Ci, 1):
        vidx[c] = j
        res.append(res[-1] * (1+dp1[c]) % M)
    vmulr[i] = res + [1]
    res = [1]
    for c in Ci[::-1]:
        res.append(res[-1] * (1+dp1[c]) % M)
    vmull[i] = [1] + res[::-1]
for l in L[1:]:
    p = P[l]
    pp = P[p]
    vi = vidx[l]
    res = vmulr[p][vi-1] * vmull[p][vi+1] % M
    res = res*(1+info[pp]) % M
    dp2[l] = dp1[l]*(res+1) % M
    info[p] = res % M

print(*dp2, sep = '\n')

Solution (Python):


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

n,MOD = [int(i) for i in input().split()]

to = [[] for _ in [0]*n]
for _ in range(n-1):
    x,y = [int(i)-1 for i in input().split()]
    to[x].append(y)
    to[y].append(x)


dp = [[0]*len(to_i) for to_i in to]
parent_index = [-9999]*n 
ans = [0]*n

def dfs(v, p):
    res = 1
    for i, vc in enumerate(to[v]):
        if vc == p:
            parent_index[v] = i
            continue
        dp[v][i] = dfs(vc, v)
        res *= dp[v][i]+1
        res %= MOD
    return res

def dfs2(v, res_p, p):
    deg = len(to[v])
    if p >= 0:
        dp[v][parent_index[v]] = res_p

    accl = [1]*(deg+1)
    accr = [1]*(deg+1)

    for i in range(1, deg+1):
        accl[i] = accl[i-1] * (dp[v][i-1] + 1) % MOD
        accr[-i-1] = accr[-i] * (dp[v][-i] + 1) % MOD

    ans[v] = accr[0]
    for i,vc in enumerate(to[v]):
        if vc == p: continue
        dfs2(vc, accl[i]*accr[i+1]%MOD, v)

dfs(0,-1)

dfs2(0,0,-1)

for i in ans:
    print(i)

Solution (Python):
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):
        
        
        
        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)





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











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

Solution (Python):
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):
        
        
        
        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)





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











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

Solution (Python):
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):
        
        
        
        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)





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











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

Solution (Python):


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

def dfs(v, p = -1):
    deg[v] = len(U[v])
    dp[v] = [0] * deg[v]
    ans = 1
    for i in range(deg[v]):
        u = U[v][i]
        if u == p:
            par[v] = i
            continue
        dp[v][i] = dfs(u, v)
        ans *= dp[v][i] + 1
        ans %= M
    return(ans)

def bfs(v, ans_p = 0, p = -1):
    if p != -1:
        dp[v][par[v]] = ans_p
    lmul = [1] * (deg[v] + 1)
    rmul = [1] * (deg[v] + 1)
    for i in range(1, deg[v] + 1):
        lmul[i] = lmul[i - 1] * (dp[v][i - 1] + 1) % M
        rmul[-i - 1] = rmul[-i] * (dp[v][-i] + 1) % M
    ans[v] = rmul[0]
    for i in range(deg[v]):
        u = U[v][i]
        if u == p:
            continue
        bfs(u, lmul[i] * rmul[i + 1] % M, v)

N, M = map(int, input().split()) 
U = [list() for _ in range(N)]
for x, y in [map(int, input().split()) for _ in range(N - 1)]:
    U[x - 1].append(y - 1)
    U[y - 1].append(x - 1)
deg = [0] * N
par = [0] * N
dp = [None] * N
ans = [0] * N
dfs(0)
bfs(0)
print("\n".join([str(x) for x in ans]))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    if n == 1:
        return 1
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b = LI_()
        e[a].append(b)
        e[b].append(a)

    rr = [None] * n

    fm = [None] * n
    def f(i,p):
        r = 1
        for c in e[i]:
            if c != p:
                r *= f(c,i) + 1
                r %= m
        fm[i] = r
        return r

    def g(i,p,pp):
        l = len(e[i])
        v = e[i]
        ta = [(pp if u==p else (fm[u] if not fm[u] is None else f(u,i))) + 1 for u in v]

        if l == 1:
            rr[i] = ta[0] % m
            return

        aa = [None] * l
        aa[0] = ta[0]
        for j in range(1,l):
            aa[j] = aa[j-1] * ta[j] % m

        ba = [None] * l
        ba[-1] = ta[-1]
        for j in range(l-2,-1,-1):
            ba[j] = ba[j+1] * ta[j] % m

        rr[i] = ba[0] % m
        if v[0] != p:
            g(v[0],i,ba[1])
        for j,u in enumerate(v[1:-1]):
            if u != p:
                g(u,i,aa[j]*ba[j+2]%m)
        if v[-1] != p:
            g(v[-1],i,aa[-2])

    def h(i):
        l = len(e[i])
        v = e[i]
        ta = [(fm[u] if not fm[u] is None else f(u,i)) + 1 for u in v]

        if l == 1:
            rr[i] = ta[0] % m
            g(v[0],i,1)
            return

        aa = [None] * l
        aa[0] = ta[0]
        for j in range(1,l):
            aa[j] = aa[j-1] * ta[j] % m

        ba = [None] * l
        ba[-1] = ta[-1]
        for j in range(l-2,-1,-1):
            ba[j] = ba[j+1] * ta[j] % m

        rr[i] = ba[0] % m
        g(v[0],i,ba[1])
        for j,u in enumerate(v[1:-1]):
            g(u,i,aa[j]*ba[j+2]%m)
        g(v[-1],i,aa[-2])

    h(1)


    return '\n'.join(map(str, rr))



print(main())