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

input = sys.stdin.buffer.readline


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

deg = [0] * (n + 1)

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



dp1 = [0] * (n + 1)



dp2 = [0] * (n + 1)


start = 1
par = [-1] * (n + 1)
que = deque([start])
topo = []
while que:
    v = que.popleft()
    topo.append(v)
    for i in range(deg[v]):
        u = graph[v][i]
        if par[v] == u:
            continue
        par[u] = v
        que.append(u)


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


edge_num = [{} for _ in range(n + 1)]

for v in topo[::-1]:
    temp = 1
    for i in range(deg[v]):
        u = graph[v][i]
        edge_num[v][u] = i  
        if u == par[v]:
            dpl[v].append(temp)
            continue
        temp *= dp1[u] + 1
        temp %= m
        dpl[v].append(temp)
    dp1[v] = temp
    temp = 1
    for i in range(deg[v] - 1, -1, -1):
        u = graph[v][i]
        if u == par[v]:
            dpr[v].append(temp)
            continue
        temp *= dp1[u] + 1
        temp %= m
        dpr[v].append(temp)







dp = [0] * (n + 1)

for v in topo:
    
    p = par[v]
    if p == -1:  
        dp[v] = dp1[v]
        dp[v] %= m
        continue
    
    
    idx = edge_num[p][v]
    num = deg[p]
    dp2[v] = 1
    if idx - 1 >= 0:
        dp2[v] *= dpl[p][idx - 1]
        dp2[v] %= m
    if num - 2 - idx >= 0:
        dp2[v] *= dpr[p][num - 2 - idx]
        dp2[v] %= m
    
    pp = par[p]  
    if pp != -1:  
        dp2[v] *= dp2[p] + 1  
        dp2[v] %= m
    
    dp[v] = dp1[v] * (dp2[v] + 1)
    dp[v] %= m
print(*dp[1:], sep="\n")

Solution (Python):
import itertools
import sys
import heapq
sys.setrecursionlimit(10**5 + 1)
n, m = map(int, input().split())

graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(lambda x: int(x) - 1, input().split())

    graph[a].append(b)
    graph[b].append(a)

rooted = [[] for _ in range(n)]
rev_rooted = [[] for _ in range(n)]
que = [(0, -1, 0)]
bfs_target = []
while que:
    node, parent, distance = que.pop()
    heapq.heappush(bfs_target, (-distance, node))
    for child in graph[node]:
        if child != parent:
            que.append((child, node, distance + 1))
            rooted[node].append(child)
            rev_rooted[child].append(node)
            

def mod(v):
    if v >= m:
        return v % m
    return v


dp = [1] * n
while bfs_target:
    node = heapq.heappop(bfs_target)[1]
    for parent in rev_rooted[node]:
        dp[parent] = mod(dp[parent] * (dp[node] + 1))
        que.append(parent)

rev_dp = [0] * n
que = [0]
while que:
    node = que.pop()
    cp = [1]
    rev_cp = [1]
    for i, child in enumerate(rooted[node]):
        cp.append(mod(cp[i] * (dp[child] + 1)))
    for i, child in enumerate(reversed(rooted[node])):
        rev_cp.append(mod(rev_cp[i] * (dp[child] + 1)))
    rev_cp = rev_cp[::-1]
    for i, child in enumerate(rooted[node]):
        rev_dp[child] = mod(cp[i] * rev_cp[i + 1] * (rev_dp[node] + 1))
        que.append(child)



for v1, v2 in zip(dp, rev_dp):
    print(mod(v1 * (v2 + 1)))

Solution (Python):
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

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

deg = [0] * N
dp = [None] * N
parents = [0] * N
ans = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    res = 1
    dp[v] = [0] * deg[v]
    for i,e in enumerate(G[v]):
        if e == p:
            parents[v] = i
            continue
        dp[v][i] = dfs(e,v)
        res *= dp[v][i] + 1
        res %= MOD
    return res

def bfs(v,res_p = 0,p = -1):
    if p != -1:
        dp[v][parents[v]] = res_p
    dpl = [1]*(deg[v] + 1)
    dpr = [1]*(deg[v] + 1)
    for i in range(deg[v]):
        dpl[i + 1] = dpl[i]*(dp[v][i] + 1)%MOD
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*(dp[v][i] + 1)%MOD
    ans[v] = dpr[0]
    for i in range(deg[v]):
        e = G[v][i]
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]%MOD,v)

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

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


class Tree:
    def __init__(self, crdinal, adjgrph, root):
        self.n = crdinal
        self.g = adjgrph
        self.root = root
        self.parent = [-1]*self.n
        self.depth = [-1]*self.n
        self.subsize = [1]*self.n
        self.result = [1]*self.n  

        s = [self.root]
        while s:
            v = s.pop()
            if self.depth[v] == -1:
                if v == self.root:
                    self.depth[v] = 0
                else:
                    self.depth[v] = self.depth[self.parent[v]] + 1
                    s.append(v)
                for w in self.g[v]:
                    if self.depth[w] == -1:
                        self.parent[w] = v
                        s.append(w)
            else:
                self.subsize[self.parent[v]] += self.subsize[v]
                self.calc(v)

    def calc(self, v):
        
        self.result[self.parent[v]] *= self.result[v]+1
        self.result[self.parent[v]] %= m
        return None

    def wanted(self):
        
        
        return self.parent

    def rerooting(self) -> list:
        
        ans = [0]*n
        ans[self.root] = self.result[self.root]

        cum1 = [[1] for i in range(n)]  
        cum2 = [[1] for i in range(n)]  
        FromParent = [0]*n

        s = [self.root]
        while s:
            v = s.pop()

            
            for w in self.g[v]:
                if w != self.parent[v]:
                    cum1[v].append(cum1[v][-1]*(self.result[w]+1) % m)
                    s.append(w)
                else:
                    cum1[v].append(cum1[v][-1]*(FromParent[v]+1) % m)

            
            for w in self.g[v][::-1]:
                if w != self.parent[v]:
                    cum2[v].append(cum2[v][-1]*(self.result[w]+1) % m)
                else:
                    cum2[v].append(cum2[v][-1]*(FromParent[v]+1) % m)
            cum2[v] = cum2[v][::-1]

            
            
            for i, w in enumerate(self.g[v]):
                if w != self.parent[v]:
                    FromParent[w] = cum1[v][i]*cum2[v][i+1] % m
                    ans[w] = (FromParent[w]+1) * self.result[w]
                    ans[w] %= m
        return ans


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)

T1 = Tree(n, g, 0)

for x in T1.rerooting():
    print(x)

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


class Tree:
    def __init__(self, crdinal, adjgrph, root):
        self.n = crdinal
        self.g = adjgrph
        self.root = root
        self.parent = [-1]*self.n
        self.depth = [-1]*self.n
        self.subsize = [1]*self.n
        self.result = [1]*self.n  

        s = [self.root]
        while s:
            v = s.pop()
            if self.depth[v] == -1:
                if v == self.root:
                    self.depth[v] = 0
                else:
                    self.depth[v] = self.depth[self.parent[v]] + 1
                    s.append(v)
                for w in self.g[v]:
                    if self.depth[w] == -1:
                        self.parent[w] = v
                        s.append(w)
            else:
                self.subsize[self.parent[v]] += self.subsize[v]
                self.calc(v)

    def calc(self, v):
        
        self.result[self.parent[v]] *= self.result[v]+1
        self.result[self.parent[v]] %= m
        return None

    def wanted(self):
        
        
        return self.parent

    def rerooting(self) -> list:
        cum1 = [[1] for i in range(n)]  
        cum2 = [[1] for i in range(n)]  
        FromParent = [0]*n

        ans = [0]*n
        ans[0] = self.result[0]

        s = [self.root]
        while s:
            v = s.pop()
            if v != self.root:
                ans[v] = (FromParent[v]+1)*self.result[v]
                ans[v] %= m

            for w in self.g[v]:
                if w != self.parent[v]:
                    cum1[v].append(cum1[v][-1]*(self.result[w]+1) % m)
                    s.append(w)
                else:
                    cum1[v].append(cum1[v][-1]*(FromParent[v]+1) % m)
            for w in self.g[v][::-1]:
                if w != self.parent[v]:
                    cum2[v].append(cum2[v][-1]*(self.result[w]+1) % m)
                else:
                    cum2[v].append(cum2[v][-1]*(FromParent[v]+1) % m)
            cum2[v] = cum2[v][::-1]

            for i, w in enumerate(self.g[v]):
                FromParent[w] = cum1[v][i]*cum2[v][i+1] % m
        return ans


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)


T1 = Tree(n, g, 0)

ans = T1.rerooting()


for x in T1.rerooting():
    print(x)

Solution (Python):
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])
        if parentIndex >= 0:
            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())
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')

Solution (Python):
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    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]

    class rerooting():
        
        def __init__(self, tree, ini, monoid, add):
            
            def calc(i, j):
                root = tree_d[i][j]+1
                try:
                    return monoid(tc_l[i][root-1], tc_r[i][root])
                except:
                    return tc_l[i][root-1]
            size = len(tree)
            dp, order, q, anc = [ini]*size, [], [0], [-1]*n
            oa, qa, qp = order.append, q.append, q.pop
            tree_d = [{k: j for j, k in enumerate(i)} for i in g]
            g_size = [len(i) for i in g]
            tc_l = [[ini]*(i+1) for i in g_size]
            tc_r = [[ini]*i for i in g_size]

            
            while q:
                i = qp()
                a = anc[i]
                oa(i)
                for j in g[i]:
                    if j != a:
                        qa(j)
                        anc[j] = i

            
            for i in order[:0:-1]:
                a = anc[i]
                d, t = add(a, i, dp[i]), tree_d[a][i]
                tc_l[a][t+1], tc_r[a][t], dp[a] = d, d, monoid(dp[a], d)

            
            for j in range(1, g_size[0]+1):
                tc_l[0][j] = monoid(tc_l[0][j], tc_l[0][j-1])
            for j in range(g_size[0]-2, 0, -1):
                tc_r[0][j] = monoid(tc_r[0][j], tc_r[0][j+1])

            
            for i in order[1:]:
                a = anc[i]
                d, c, length = tree_d[i][a], add(a, i, calc(a, i)), g_size[i]
                tc_l[i][d+1], tc_r[i][d] = c, c
                for j in range(1, length+1):
                    tc_l[i][j] = monoid(tc_l[i][j], tc_l[i][j-1])
                for j in range(length-2, 0, -1):
                    tc_r[i][j] = monoid(tc_r[i][j+1], tc_r[i][j])
                dp[i] = tc_l[i][-1]

            
            self.dp, self.tc_l, self.tc_r, self.tree_d, self.monoid = dp, tc_l, tc_r, tree_d, monoid

        

        def DP_part(self, i, j):
            root = self.tree_d[i][j]+1
            try:
                return self.monoid(self.tc_l[i][root-1], self.tc_r[i][root])
            except:
                return self.tc_l[i][root-1]

    def monoid1(x, y): return x*y % m
    def add1(i, j, x): return x+1

    r1 = rerooting(g, 1, monoid1, add1)
    for i in r1.dp:
        print(i)


main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, MOD = map(int,input().split())
    E = [[] for _ in range(n)]
    nv_to_idx = [{} for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        nv_to_idx[u][v] = len(E[u])
        nv_to_idx[v][u] = len(E[v])
        E[u].append(v)
        E[v].append(u)

    
    dp = [1] * n
    stack = [(0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            dp[p] = dp[p] * (dp[~v] + 1) % MOD

    
    def rerooting(v, p):
        
        if p != -1:
            idx = nv_to_idx[p][v]
            dp[p] = cum_left[p][idx] * cum_right[p][idx + 1] % MOD

        
        if cum_left[v] is None:
            k = len(E[v])
            left = [1] * (k + 1)
            right = [1] * (k + 1)
            for i in range(k):
                left[i + 1] = left[i] * (dp[E[v][i]] + 1) % MOD
            for i in range(k - 1, -1, -1):
                right[i] = right[i + 1] * (dp[E[v][i]] + 1) % MOD
            cum_left[v] = left
            cum_right[v] = right

        
        dp[v] = cum_left[v][-1]

    ans = [None] * n
    stack = [(0, -1)]
    cum_left = [None] * n
    cum_right = [None] * n
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            ans[v] = dp[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    print(*ans, sep = '\n')
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, MOD = map(int,input().split())
    E = [[] for _ in range(n)]
    nv_to_idx = [{} for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        nv_to_idx[u][v] = len(E[u])
        nv_to_idx[v][u] = len(E[v])
        E[u].append(v)
        E[v].append(u)

    
    dp = [1] * n
    deg = [len(E[v]) - 1 for v in range(n)]
    deg[0] += 1
    stack = [(0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            if deg[~v] == 0:
                dp[p] = dp[p] * (dp[~v] + 1) % MOD
            deg[p] -= 1

    
    def rerooting(v, p):
        
        if p != -1:
            idx = nv_to_idx[p][v]
            dp[p] = cum_left[p][idx] * cum_right[p][idx + 1] % MOD

        
        if cum_left[v] is None:
            k = len(E[v])
            left = [1] * (k + 1)
            right = [1] * (k + 1)
            for i in range(k):
                left[i + 1] = left[i] * (dp[E[v][i]] + 1) % MOD
            for i in range(k - 1, -1, -1):
                right[i] = right[i + 1] * (dp[E[v][i]] + 1) % MOD
            cum_left[v] = left
            cum_right[v] = right

        
        dp[v] = cum_left[v][-1]

    ans = [None] * n
    stack = [(0, -1)]
    cum_left = [None] * n
    cum_right = [None] * n
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            ans[v] = dp[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    print(*ans, sep = '\n')
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, MOD = map(int,input().split())
    if n == 1:
        print(1)
        return

    E = [[] for _ in range(n)]
    nv_to_idx = [{} for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        nv_to_idx[u][v] = len(E[u])
        nv_to_idx[v][u] = len(E[v])
        E[u].append(v)
        E[v].append(u)

    
    dp = [1] * n
    deg = [len(E[v]) - 1 for v in range(n)]
    deg[0] += 1
    stack = [(0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            if deg[~v] == 0:
                dp[p] = dp[p] * (dp[~v] + 1) % MOD
            deg[p] -= 1

    
    def rerooting(v, p):
        
        if p != -1:
            idx = nv_to_idx[p][v]
            p_res = 1
            if idx > 0:
                p_res *= cum_left[p][idx - 1]
            if idx < len(E[p]) - 1:
                p_res *= cum_right[p][idx + 1]
            dp[p] = p_res % MOD

        
        if cum_left[v] is None:
            left = [(dp[nv] + 1) % MOD for nv in E[v]]
            right = [(dp[nv] + 1) % MOD for nv in E[v]]
            k = len(E[v])
            for i in range(k - 1):
                left[i + 1] *= left[i]
                left[i + 1] %= MOD
            for i in range(k - 1, 0, -1):
                right[i - 1] *= right[i]
                right[i - 1] %= MOD
            cum_left[v] = left
            cum_right[v] = right
        dp[v] = cum_left[v][-1]

    ans = [None] * n
    stack = [(0, -1)]
    cum_left = [None] * n
    cum_right = [None] * n
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            ans[v] = dp[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    print(*ans, sep = '\n')
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, MOD = map(int,input().split())
    if n == 1:
        print(1)
        return

    E = [[] for _ in range(n)]
    nv_to_idx = [{} for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        nv_to_idx[u][v] = len(E[u])
        nv_to_idx[v][u] = len(E[v])
        E[u].append(v)
        E[v].append(u)

    
    topological_sort = []
    parent = [None] * n
    stack = [(0, -1)]
    while stack:
        v, p = stack.pop()
        parent[v] = p
        topological_sort.append(v)
        for nv in E[v]:
            if nv == p:
                continue
            stack.append((nv, v))
    topological_sort.reverse()

    
    dp = [None] * n
    for v in topological_sort:
        res = 1
        for nv in E[v]:
            if nv == parent[v]:
                continue
            res = res * (dp[nv] + 1) % MOD
        dp[v] = res

    
    def rerooting(v, p):
        
        if p != -1 and v != -1:
            idx = nv_to_idx[p][v]
            p_res = 1
            if idx > 0:
                p_res *= cum_left[p][idx - 1]
            if idx < len(E[p]) - 1:
                p_res *= cum_right[p][idx + 1]
            dp[p] = p_res % MOD

        
        if cum_left[v] is None:
            left = [(dp[nv] + 1) % MOD for nv in E[v]]
            right = [(dp[nv] + 1) % MOD for nv in E[v]]
            k = len(E[v])
            for i in range(k - 1):
                left[i + 1] *= left[i]
                left[i + 1] %= MOD
            for i in range(k - 1, 0, -1):
                right[i - 1] *= right[i]
                right[i - 1] %= MOD
            cum_left[v] = left
            cum_right[v] = right
        dp[v] = cum_left[v][-1]

    ans = [None] * n
    stack = [(~0, -1), (0, -1)]
    cum_left = [None] * n
    cum_right = [None] * n
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            ans[v] = dp[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    print(*ans, sep = '\n')
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n, MOD = map(int,input().split())
    if n == 1:
        print(1)
        return

    E = [[] for _ in range(n)]
    nv_to_idx = [{} for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        nv_to_idx[u][v] = len(E[u])
        nv_to_idx[v][u] = len(E[v])
        E[u].append(v)
        E[v].append(u)
    deg = [len(E[v]) - 1 for v in range(n)]
    deg[0] += 1

    topological_sort = []
    parent = [None] * n
    stack = [(~0, -1), (0, -1)] 
    while stack:
        v, p = stack.pop()
        if v >= 0:
            parent[v] = p
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            if deg[~v] == 0:
                topological_sort.append(~v)
            deg[p] -= 1

    
    dp = [None] * n
    for v in topological_sort:
        res = 1
        for nv in E[v]:
            if nv == parent[v]:
                continue
            res = res * (dp[nv] + 1) % MOD
        dp[v] = res

    
    def rerooting(v, p):
        
        if p != -1 and v != -1:
            idx = nv_to_idx[p][v]
            p_res = 1
            if idx > 0:
                p_res *= cum_left[p][idx - 1]
            if idx < len(E[p]) - 1:
                p_res *= cum_right[p][idx + 1]
            dp[p] = p_res % MOD

        if v == -1:
            return
        
        if cum_left[v] is None:
            left = [(dp[nv] + 1) % MOD for nv in E[v]]
            right = [(dp[nv] + 1) % MOD for nv in E[v]]
            k = len(E[v])
            for i in range(k - 1):
                left[i + 1] *= left[i]
                left[i + 1] %= MOD
            for i in range(k - 1, 0, -1):
                right[i - 1] *= right[i]
                right[i - 1] %= MOD
            cum_left[v] = left
            cum_right[v] = right
        dp[v] = cum_left[v][-1]

    ans = [None] * n
    ans[0] = dp[0]
    stack = [(~0, -1), (0, -1)]
    cum_left = [None] * n
    cum_right = [None] * n
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            ans[v] = dp[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    print(*ans, sep = '\n')
resolve()

Solution (Python):
class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)

    def rerooting(self, func, merge, ti, ei):
        dp = [ti for _ in range(self.n)]
        lt = [ei for _ in range(self.n)]
        rt = [ei for _ in range(self.n)]
        inv = [ei for _ in range(self.n)]
        self.setroot(0)
        for node in self.order[::-1]:
            tmp = ti
            for adj in self.tree[node]:
                if self.parent[adj] == node:
                    lt[adj] = tmp
                    tmp = func(tmp, dp[adj])
            tmp = ti
            for adj in self.tree[node][::-1]:
                if self.parent[adj] == node:
                    rt[adj] = tmp
                    tmp = func(tmp, dp[adj])
            dp[node] = tmp
        for node in self.order:
            if node == 0:
                continue
            merged = merge(lt[node], rt[node])
            par = self.parent[node]
            inv[node] = func(merged, inv[par])
            dp[node] = func(dp[node], inv[node])
        return dp

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N, E)

def func(node, adj):
    return node * (adj + 1) % M

def merge(lt, rt):
    return lt * rt % M

ti = 1
ei = 0

D = T.rerooting(func, merge, ti, ei)

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

Solution (Python):
class ReRooting(object):
    """ 全方位木DP """
    def processing(self, in_:list, v:int):
        """ 単項演算(加工) f """
        return [in_[0] + 1]
    
    def merge(self, in1:list, in2:list):
        """ 二項演算(マージ) ・ """
        return [in1[0] * in2[0] % M]

    def adjustment(self, in_:list, v:int):
        """ 単項演算(調整) g """
        return in_
    
    def solve(self):
        """
        計算結果を返す
        
        Ex. [cnt for cnt, _ in self.calc()]
        """
        return [res for [res] in self.calc()]

    def __init__(self, V:int, e:list):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
    
    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    self.edge[w].remove(v)
                    que.append(w)
    
    def bottom_up(self):
        """ Bottom-Up DP """
        accBU = [self.e for _ in range(self.V)]
        resBU = [None] * self.V
        for v in reversed(self.order):
            for c in self.edge[v]:
                accBU[v] = self.merge(accBU[v], self.processing(resBU[c], c))
            resBU[v] = self.adjustment(accBU[v], v)
        return accBU, resBU
    
    def top_down(self, resBU:list):
        """ Top-Down DP """
        accTD = [self.e for _ in range(self.V)]
        resTD = [self.e for _ in range(self.V)]

        for p in self.order:
            ac = self.e if (p == self.order[0]) else self.processing(resTD[p], p)
            for v in self.edge[p]:
                accTD[v] = ac[:]
                ac = self.merge(ac, self.processing(resBU[v], v))
            
            ac = self.e
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                resTD[v] = self.adjustment(accTD[v], v)
                ac = self.merge(ac, self.processing(resBU[v], v))
        return resTD
    
    def calc(self):
        self.topological_sort()
        accBU, resBU = self.bottom_up()
        resTD = self.top_down(resBU)

        res = [None] * self.V
        for v in self.order:
            res[v] = self.e if (v == self.order[0]) else self.processing(resTD[v], v)
            res[v] = self.merge(accBU[v], res[v])
            res[v] = self.adjustment(res[v], v)
        return res


N, M = map(int, input().split())
 
RR = ReRooting(N, [1])
for _ in range(N - 1):
    x, y = map(int, input().split())
    RR.add_edge(x - 1, y - 1)
 
print(*RR.solve(), sep="\n")