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):
'''
N頂点の木があり、i番目の辺は頂点x_iとy_iを結んでいる。
各頂点を白または黒で塗り、どの黒い頂点からどの黒い頂点へも黒い頂点のみをたどって到達できる時、
頂点vが黒であるような頂点の色の組み合わせは何通りか？Mで割ったあまりを求めよ。
graph_i
input:
3 100
1 2
2 3
output:
    3
    4
    3

'''

import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter

from functools import lru_cache
import copy


input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7




def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])





unit = 1  


def merge(a, b):
    
    return a * b % M


def adj_bu(a, i):
    
    return a + 1


def adj_td(a, i, p):
    
    return a + 1


def adj_fin(a, i):
    
    return a



n, M = inpl()
graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = inpl()
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
parent = [-1] * n
root = 0  
queue = collections.deque([root])
sorted_graph = []  


while queue:
    i = queue.popleft()
    sorted_graph.append(i)
    for a in graph[i]:
        if a != parent[i]:
            parent[a] = i
            graph[a].remove(i)  
            queue.append(a)



BU = [unit] * n  
res = [0] * n
for i in sorted_graph[1:][::-1]:
    res[i] = adj_bu(BU[i], i)
    p = parent[i]
    BU[p] = merge(BU[p], res[i])
res[sorted_graph[0]] = adj_fin(BU[sorted_graph[0]], sorted_graph[0])  




TD = [unit] * n
for i in sorted_graph:
    
    tmp = TD[i]
    for j in graph[i]:
        TD[j] = tmp
        tmp = merge(tmp, res[j])
    
    tmp = unit
    for j in graph[i][::-1]:
        TD[j] = adj_td(merge(TD[j], tmp), j, i)
        tmp = merge(tmp, res[j])
        res[j] = adj_fin(merge(BU[j], TD[j]), j)
print(*res, sep="\n")
'''
各頂点に対して結果を出力するので全方位木を考える。
全方位木では子→親の木DPと親→子の木DPを使う。
acc[i][p]:ノードiにおける親pを除いた全方向からの累積
res[i][p]:acc[i][p]に調整を加えたもの
acc[i]:ノードiにおけるすべての方向からの集約
'''

Solution (Python):
import sys,os,io

input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: 
        marker = 1
        parent[u]=v
        stack.append(u)
      else: 
        ans[v] *= ans[u]+1
        ans[v] %=M
    if marker==0:
      stack.pop()
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  while stack:
    v = stack.pop()
    cum1 = [1]*(len(edge[v])+1)
    cum2 = [1]*(len(edge[v])+1)
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        cum1[i+1] = cum1[i]*(p_value[v]+1)%M
      else:
        cum1[i+1] = cum1[i]*(ans[u]+1)%M
    for i,u in enumerate(edge[v][::-1]):
      if u==parent[v]:
        cum2[-i-2] = cum2[-i-1]*(p_value[v]+1)%M
      else:
        cum2[-i-2] = cum2[-i-1]*(ans[u]+1)%M
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = cum1[i]*cum2[i+1]%M
      ans[u] *= (p_value[u]+1)
      ans[u] %= M
      stack.append(u)
    ans[v] %= M
  return

ans = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

Solution (Python):
import sys,os,io
input = sys.stdin.readline


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

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: 
        marker = 1
        parent[u]=v
        stack.append(u)
      else: 
        ans[v] *= ans[u]+1
        ans[v] %=M
    if marker==0:
      stack.pop()
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  while stack:
    v = stack.pop()
    cum1 = [1]*(len(edge[v])+1)
    cum2 = [1]*(len(edge[v])+1)
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        cum1[i+1] = cum1[i]*(p_value[v]+1)%M
      else:
        cum1[i+1] = cum1[i]*(ans[u]+1)%M
    for i,u in enumerate(edge[v][::-1]):
      if u==parent[v]:
        cum2[-i-2] = cum2[-i-1]*(p_value[v]+1)%M
      else:
        cum2[-i-2] = cum2[-i-1]*(ans[u]+1)%M
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = cum1[i]*cum2[i+1]%M
      ans[u] *= (p_value[u]+1)
      ans[u] %= M
      stack.append(u)
    ans[v] %= M
  return

ans = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

Solution (Python):
import sys,os,io
input = sys.stdin.readline


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

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: 
        marker = 1
        parent[u]=v
        stack.append(u)
      else: 
        ans[v] *= ans[u]+1
        ans[v] %=M
    if marker==0:
      stack.pop()
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  while stack:
    v = stack.pop()
    cum1 = [1]*(len(edge[v])+1)
    cum2 = [1]*(len(edge[v])+1)
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        cum1[i+1] = cum1[i]*(p_value[v]+1)%M
      else:
        cum1[i+1] = cum1[i]*(ans[u]+1)%M
    for i,u in enumerate(edge[v][::-1]):
      if u==parent[v]:
        cum2[-i-2] = cum2[-i-1]*(p_value[v]+1)%M
      else:
        cum2[-i-2] = cum2[-i-1]*(ans[u]+1)%M
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = cum1[i]*cum2[i+1]%M
      ans[u] *= (p_value[u]+1)
      ans[u] %= M
      stack.append(u)
    ans[v] %= M
  return

ans = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

Solution (Python):





from collections import defaultdict

class ReRooting:
    def __init__(self, f, g, merge, ie):
        self.tree = defaultdict(list)
        self.f = f
        self.g = g
        self.merge = merge
        self.ie = ie
        self.dp = defaultdict(dict)

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    def __dfs1(self, u, p):
        o = []
        s = [(u, -1)]
        while s:
            u, p = s.pop()
            o.append((u, p))
            for v in self.tree[u]:
                if v == p:
                    continue
                s.append((v, u))

        for u, p in reversed(o):
            r = self.ie
            for v in self.tree[u]:
                if v == p:
                    continue
                r = self.merge(r, self.f(self.dp[u][v], v))

            self.dp[p][u] = self.g(r, u)

    def __dfs2(self, u, p, a):
        s = [(u, p, a)]

        while s:
            u, p, a = s.pop()
            self.dp[u][p] = a

            pl = [0] * (len(self.tree[u]) + 1)
            pl[0] = self.ie
            for i, v in enumerate(self.tree[u]):
                pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

            pr = [0] * (len(self.tree[u]) + 1)
            pr[-1] = self.ie
            for i, v in reversed(list(enumerate(self.tree[u]))):
                pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

            for i, v in enumerate(self.tree[u]):
                if v == p:
                    continue
                r = self.merge(pl[i], pr[i+1])
                s.append((v, u, self.g(r, u)))

    
    
    
    
    
    
    

    

    
    
    
    
    
    
    
    
    

    
    
    
    

    
    
    
    
    

    def build(self, root=1):
        self.__dfs1(root, -1)
        self.__dfs2(root, -1, self.ie)

    def slv(self, u):
        r = self.ie
        for v in self.tree[u]:
            r = self.merge(r, self.f(self.dp[u][v], v))

        return self.g(r, u)


def atcoder_dp_dp_v():
    
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, y: x
    g = lambda x, y: x + 1
    merge = lambda x, y: (x * y) % M
    rr = ReRooting(f, g, merge, 1)
    for x, y in XY:
        rr.add_edge(x, y)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)-1)


def atcoder_abc60_f():
    
    
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]

    M = 10**9+7

    from functools import reduce

    fact = [1]
    for i in range(1, 10**6):
        fact.append(fact[-1]*i % M)

    def f(x, _):
        c = x[0]
        s = x[1]
        c *= pow(fact[s], M-2, M)
        c %= M
        return (c, s)

    def g(x, _):
        c = x[0]
        s = x[1]
        c *= fact[s]
        c %= M
        return (c, s+1)

    def merge(x, y):
        return (x[0]*y[0]%M, x[1]+y[1])

    rr = ReRooting(f, g, merge, (1, 0))
    for a, b in AB:
        rr.add_edge(a, b)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)[0])


def codeforces_1324_f():
    N = int(input())
    A = list(map(int, input().split()))
    UV = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, v: max(x, 0)

    def g(x, v):
        return x + (1 if A[v-1] == 1 else -1)

    def merge(x, y):
        return x + y

    rr = ReRooting(f, g, merge, 0)
    for u, v in UV:
        rr.add_edge(u, v)



    rr.build()
    
    ans = []
    for u in range(1, N+1):
        ans.append(rr.slv(u))

    print(*ans)


if __name__ == '__main__':
    atcoder_dp_dp_v()

Solution (Python):



from collections import defaultdict

class ReRooting:
    def __init__(self, f, g, merge, ie):
        self.tree = defaultdict(list)
        self.f = f
        self.g = g
        self.merge = merge
        self.ie = ie
        self.dp = defaultdict(dict)

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    def __dfs1(self, u, p):
        o = []
        s = [(u, -1)]
        while s:
            u, p = s.pop()
            o.append((u, p))
            for v in self.tree[u]:
                if v == p:
                    continue
                s.append((v, u))

        for u, p in reversed(o):
            r = self.ie
            for v in self.tree[u]:
                if v == p:
                    continue
                
                r = self.merge(r, self.f(self.dp[u][v], v))

            self.dp[p][u] = self.g(r, u)

    def __dfs2(self, u, p, a):
        s = [(u, p, a)]

        while s:
            u, p, a = s.pop()

            self.dp[u][p] = a

            pl = [0] * (len(self.tree[u]) + 1)
            pl[0] = self.ie
            for i, v in enumerate(self.tree[u]):
                pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

            pr = [0] * (len(self.tree[u]) + 1)
            pr[-1] = self.ie
            for i, v in reversed(list(enumerate(self.tree[u]))):
                pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

            for i, v in enumerate(self.tree[u]):
                if v == p:
                    continue
                r = self.merge(pl[i], pr[i+1])
                s.append((v, u, self.g(r, v)))

    
    
    
    
    
    
    

    

    
    
    
    
    
    
    
    
    

    
    
    
    

    
    
    
    
    

    def build(self, root=1):
        self.__dfs1(root, -1)
        self.__dfs2(root, -1, self.ie)

    def slv(self, u):
        r = self.ie
        for v in self.tree[u]:
            r = self.merge(r, self.f(self.dp[u][v], v))

        return self.g(r, u)


def atcoder_dp_dp_v():
    
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, y: x
    g = lambda x, y: x + 1
    merge = lambda x, y: (x * y) % M
    rr = ReRooting(f, g, merge, 1)
    for x, y in XY:
        rr.add_edge(x, y)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)-1)


def atcoder_abc60_f():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]

    M = 10**9+7

    from functools import reduce

    fact = [1]
    for i in range(1, 10**6):
        fact.append(fact[-1]*i % M)

    def f(x, _):
        c = x[0]
        s = x[1]
        c *= pow(fact[s], M-2, M)
        c %= M
        return (c, s)

    def g(x, _):
        c = x[0]
        s = x[1]
        c *= fact[s]
        c %= M
        return (c, s+1)

    def merge(x, y):
        return (x[0]*y[0]%M, x[1]+y[1])

    rr = ReRooting(f, g, merge, (1, 0))
    for a, b in AB:
        rr.add_edge(a, b)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)[0])




if __name__ == '__main__':
    atcoder_dp_dp_v()

Solution (Python):



from collections import defaultdict

class ReRooting:
    def __init__(self, f, g, merge, ie):
        self.tree = defaultdict(list)
        self.f = f
        self.g = g
        self.merge = merge
        self.ie = ie
        self.dp = defaultdict(dict)

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    def __dfs1(self, u, p):
        o = []
        s = [(u, -1)]
        while s:
            u, p = s.pop()
            o.append((u, p))
            for v in self.tree[u]:
                if v == p:
                    continue
                s.append((v, u))

        for u, p in reversed(o):
            r = self.ie
            for v in self.tree[u]:
                if v == p:
                    continue
                
                r = self.merge(r, self.f(self.dp[u][v], v))
            self.dp[p][u] = self.g(r, u)

    def __dfs2(self, u, p, a):
        s = [(u, p, a)]

        while s:
            u, p, a = s.pop()

            self.dp[u][p] = a

            pl = [0] * (len(self.tree[u]) + 1)
            pl[0] = self.ie
            for i, v in enumerate(self.tree[u]):
                pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

            pr = [0] * (len(self.tree[u]) + 1)
            pr[-1] = self.ie
            for i, v in reversed(list(enumerate(self.tree[u]))):
                pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

            for i, v in enumerate(self.tree[u]):
                if v == p:
                    continue
                r = self.merge(pl[i], pr[i+1])
                s.append((v, u, self.g(r, v)))

    
    
    
    
    
    
    

    

    
    
    
    
    
    
    
    
    

    
    
    
    

    
    
    
    
    

    def build(self, root=1):
        self.__dfs1(root, -1)
        self.__dfs2(root, -1, self.ie)

    def slv(self, u):
        r = self.ie
        for v in self.tree[u]:
            r = self.merge(r, self.f(self.dp[u][v], v))

        return r


def atcoder_dp_dp_v():
    
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, y: x
    g = lambda x, y: x + 1
    merge = lambda x, y: (x * y) % M
    rr = ReRooting(f, g, merge, 1)
    for x, y in XY:
        rr.add_edge(x, y)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u))



if __name__ == '__main__':
    atcoder_dp_dp_v()

Solution (Python):



from collections import defaultdict

class ReRooting:
    def __init__(self, f, g, merge, ie):
        self.tree = defaultdict(list)
        self.f = f
        self.g = g
        self.merge = merge
        self.ie = ie
        self.dp = defaultdict(dict)

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    def __dfs1(self, u, p):
        o = []
        s = [(u, -1)]
        while s:
            u, p = s.pop()
            o.append((u, p))
            for v in self.tree[u]:
                if v == p:
                    continue
                s.append((v, u))

        for u, p in reversed(o):
            r = self.ie
            for v in self.tree[u]:
                if v == p:
                    continue
                
                r = self.merge(r, self.f(self.dp[u][v], v))
            self.dp[p][u] = self.g(r, u)

    def __dfs2(self, u, p, a):
        s = [(u, p, a)]

        while s:
            u, p, a = s.pop()

            self.dp[u][p] = a

            pl = [0] * (len(self.tree[u]) + 1)
            pl[0] = self.ie
            for i, v in enumerate(self.tree[u]):
                pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

            pr = [0] * (len(self.tree[u]) + 1)
            pr[-1] = self.ie
            for i, v in reversed(list(enumerate(self.tree[u]))):
                pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

            for i, v in enumerate(self.tree[u]):
                if v == p:
                    continue
                r = self.merge(pl[i], pr[i+1])
                s.append((v, u, self.g(r, v)))


    def build(self, root=1):
        self.__dfs1(root, -1)
        self.__dfs2(root, -1, self.ie)

    def slv(self, u):
        r = self.ie
        for v in self.tree[u]:
            r = self.merge(r, self.f(self.dp[u][v], v))

        return r


def main():
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, y: x
    g = lambda x, y: x + 1
    merge = lambda x, y: (x * y) % M
    rr = ReRooting(f, g, merge, 1)
    for x, y in XY:
        rr.add_edge(x, y)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u))



if __name__ == '__main__':
    main()

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





N, mod = getNM()
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = getNM()
    X[x - 1].append(y - 1)
    X[y - 1].append(x - 1)

class Reroot():
    def __init__(self, graph):
        self.graph = copy.deepcopy(graph)
        
        self.unit = 1
        self.merge = lambda a, b: a * b % mod
        self.adj_bu = lambda a, i: a + 1
        self.adj_td = lambda a, i, p: a + 1
        self.adj_fin = lambda a, i: a
        
        
        P = [-1] * N 
        Q = deque([0])
        R = [] 
        while Q:
            i = deque.popleft(Q)
            R.append(i)
            for a in self.graph[i]:
                if a != P[i]:
                    P[a] = i
                    
                    self.graph[a].remove(i)
                    deque.append(Q, a)
        
        ME = [self.unit] * N 
        XX = [0] * N 
        for i in R[1:][::-1]: 
            XX[i] = self.adj_bu(ME[i], i)
            p = P[i] 
            ME[p] = self.merge(ME[p], XX[i]) 
        XX[R[0]] = self.adj_fin(ME[R[0]], R[0])

        TD = [self.unit] * N
        for i in R: 
            ac = TD[i] 
            for j in self.graph[i]: 
                TD[j] = ac
                ac = self.merge(ac, XX[j])  
            ac = self.unit
            for j in self.graph[i][::-1]:
                TD[j] = self.adj_td(self.merge(TD[j], ac), j, i)
                ac = self.merge(ac, XX[j])
                XX[j] = self.adj_fin(self.merge(ME[j], TD[j]), j)
        self.res = XX

tree = Reroot(X)
for i in tree.res:
    print(i)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
def dfs(v,p):
    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)
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)
reroot(0,0,-1)
print(*ans,sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
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')

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]
N,MOD = IL()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count






order = []
d = [INF] * N
def bfs(graph, start):
  N = len(graph)
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    order.append(u)
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      q.append(v)


graph = [[] for i in range(N)]

for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)

bfs(graph, 0)

dp = [0 for i in range(N)]
cum = [None for i in range(N)]
for x in order[::-1]:
  cum1 = [1]
  for y in graph[x]:
    if d[x] < d[y]:
      cum1.append((cum1[-1]*(dp[y]+1))%MOD)
  cum2 = [1]
  for y in graph[x][::-1]:
    if d[x] < d[y]:
      cum2.append((cum2[-1]*(dp[y]+1))%MOD)
  dp[x] = cum1[-1]
  cum[x] = [cum1,cum2]

factor = [1 for i in range(N)]
for x in order:
  i = 0
  for y in graph[x]:
    if d[x] < d[y]:
      dpinved = cum[x][0][i] * cum[x][1][len(cum[x][0])-2-i]
      factor[y] = (dpinved*factor[x]+1)%MOD
      i += 1
      
for i in range(N):
  print((dp[i]*factor[i])%MOD)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


n, mod = LI()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

dp = [-1] * n
par = [-1] * n
def f(u):
    ret = 1
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        ret = ret * f(v)
    dp[u] = ret
    if u: return ret + 1

f(0)
ans = [0] * n
ans[0] = dp[0]
par_acc = [1] * n
dp2 = [1] * n
q = deque([0])
while q:
    u = q.pop()
    ans[u] = dp[u] * dp2[u] % mod
    L1 = [1]
    L2 = []
    D = {}
    cnt = 0
    for v in G[u]:
        if par[u] == v:
            continue
        L1 += [dp[v] + 1]
        L2 += [dp[v] + 1]
        D[cnt] = v
        q += [v]
        cnt += 1
    L2 += [1]
    if len(L1) > 2:
        for i in range(len(L1) - 2):
            L1[i + 2] = L1[i + 2] * L1[i + 1] % mod
            L2[-i - 3] = L2[-i - 3] * L2[-i - 2] % mod
    for j in D:
        dp2[D[j]] = (L1[j] * L2[j + 1] * dp2[u] + 1) % mod

print(*ans, sep="\n")