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):
class ReRooting(object):
    """ 全方位木DP """
    def merge(self, a, b):
        """ 二項演算 a・b """
        return a * b % M

    def adj_bu(self, accBU, v:int):
        """
        Bottom-Upの単項演算 g(accBU[v])

        v: 頂点
        """
        return accBU + 1

    def adj_td(self, accTD, v:int, p:int):
        """
        Top-Downの単項演算 g(accTD[v])

        v: 頂点
        p: 親
        """
        return accTD + 1

    def adj_fin(self, acc, v:int):
        """
        最終結果の単項演算 g(acc[v])

        v: 頂点
        """
        return acc

    def __init__(self, V:int, e:int):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
        self.SIZE = [1] * self.V
    
    def subtree_size(self):
        """ 部分木のサイズを求める """
        for v in reversed(self.order[1:]):
            self.SIZE[self.par[v]] += self.SIZE[v]

    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 """
        root = self.order[0]
        accBU = [self.e] * self.V
        resBU = [self.e] * self.V

        for v in reversed(self.order):
            resBU[v] = self.adj_bu(accBU[v], v)

            if v == root: break

            p = self.par[v]
            accBU[p] = self.merge(accBU[p], resBU[v])
        return accBU, resBU
    
    def top_down(self, resBU:list):
        """ Top-Down DP """
        accTD = [self.e] * self.V
        resTD = [self.e] * self.V

        for p in self.order:
            
            ac = resTD[p]
            for v in self.edge[p]:
                accTD[v] = ac
                ac = self.merge(ac, resBU[v])

            
            ac = self.e
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                ac = self.merge(ac, resBU[v])
                
                resTD[v] = self.adj_td(accTD[v], v, p)
        return resTD
    
    def solve(self):
        self.topological_sort()
        
        accBU, resBU = self.bottom_up()
        resTD = self.top_down(resBU)
        res = [self.adj_fin(self.merge(a, b), v) for v,(a,b) in enumerate(zip(accBU, resTD))]
        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")

Solution (Python):
class ReRooting(object):
    """ 全方位木DP """
    def merge(self, a, b):
        """ 二項演算 a・b """
        return a * b % M

    def adj_bu(self, a, v:int):
        """
        Bottom-Upの単項演算 g(a)

        v: 頂点
        """
        return a + 1

    def adj_td(self, a, v:int, p:int):
        """
        Top-Downの単項演算 g(a)

        v: 頂点
        p: 親
        """
        return a + 1

    def adj_fin(self, a, v:int):
        """
        最終結果の単項演算 g(a)

        v: 頂点
        """
        return a

    def __init__(self, V:int, e:int):
        """
        V: 頂点数
        e: 単位元
        """
        self.V = V
        self.e = 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 """
        root = self.order[0]
        accBU = [self.e] * self.V
        resBU = [self.e] * self.V

        for v in reversed(self.order):
            resBU[v] = self.adj_bu(accBU[v], v)

            if v == root: break

            p = self.par[v]
            accBU[p] = self.merge(accBU[p], resBU[v])
        return accBU, resBU
    
    def top_down(self, resBU:list):
        """ Top-Down DP """
        accTD = [self.e] * self.V
        resTD = [self.e] * self.V

        for p in self.order:
            
            ac = resTD[p]
            for v in self.edge[p]:
                accTD[v] = ac
                ac = self.merge(ac, resBU[v])

            
            ac = self.e
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                ac = self.merge(ac, resBU[v])
                resTD[v] = self.adj_td(accTD[v], v, p)
        return resTD
    
    def solve(self):
        self.topological_sort()
        accBU, resBU = self.bottom_up()
        resTD = self.top_down(resBU)

        res = [self.adj_fin(self.merge(a, b), v) for v,(a,b) in enumerate(zip(accBU, resTD))]

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

Solution (Python):
from collections import deque

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


par = [-1] * N
TS = []
que = deque([0])
while que:
    v = que.popleft()
    TS.append(v)
    for w in edge[v]:
        if w == par[v]: continue
        par[w] = v
        edge[w].remove(v)
        que.append(w)


unit = 1
merge = lambda a, b: a * b % M
adj_bu = lambda a, v: a + 1
adj_td = lambda a, v, p: a + 1
adj_fin = lambda a, v: a


accBU = [unit] * N
res = [0] * N
for v in reversed(TS[1:]):
    res[v] = adj_bu(accBU[v], v)
    p = par[v]
    accBU[p] = merge(accBU[p], res[v])
res[TS[0]] = adj_fin(accBU[TS[0]], TS[0])


resTD = [unit] * N
for p in TS:
    tmp = resTD[p]
    for v in edge[p]:
        resTD[v] = tmp
        tmp = merge(tmp, res[v])
    tmp = unit
    for v in reversed(edge[p]):
        resTD[v] = adj_td(merge(resTD[v], tmp), v, p)
        tmp = merge(tmp, res[v])
        res[v] = adj_fin(merge(accBU[v], resTD[v]), v)

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

Solution (Python):


import itertools
import sys
input = sys.stdin.readline

N, MOD = map(int, input().split())
XY = [list(map(int, input().split())) for i in range(N-1)]
prod = lambda x, y: x*y%MOD

tree = [[] for i in range(N)]
for x, y in XY:
  tree[x-1].append(y-1)
  tree[y-1].append(x-1)

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


dp_down = [0] * N
for node in order[::-1]: 
  res = 1
  for child in tree[node]:
    res *= dp_down[child] + 1
    res %= MOD
  dp_down[node] = res


dp_up = [1] * N
for node in order: 
  par = parent[node]
  arr = [dp_down[c]+1 if c!=par else dp_up[node] for c in tree[node]]
  
  left = [1] + list(itertools.accumulate(arr, prod))[:-1]
  right = list(itertools.accumulate(reversed(arr), prod))[-2::-1] + [1]
  upper_cases = [l*r%MOD for l, r in zip(left, right)]
  for c, res in zip(tree[node], upper_cases):
    if c != par:
      dp_up[c] = res + 1 

ans = [d*u%MOD for d, u in zip(dp_down, dp_up)]
print(*ans, sep='\n')

Solution (Python):
n,m = map(int,input().split())
mod = m



import sys
input = sys.stdin.readline
from collections import deque

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

ini = 1

def calc(a,b):
    p = a * b % mod
    return p


def calc1(c,p):
    p_num = ini
    for i in graph[c]:
        if i == p:
            continue
        p_num = calc(p_num, dp1[i])
    p_num += 1
    dp1[c] = p_num % mod


def calc2(p):
    arr = [dp1[c] if c != parent[p] else dp2[p] for c in graph[p]]

    left = [ini]
    for i in arr[:-1]:
        left.append( calc(left[-1], i ) )
    right = [ini]
    for i in arr[:0:-1]:
        right.append( calc(right[-1], i) )
    right = right[::-1]

    prod = []
    for a,b in zip(left,right):
        prod.append(calc(a,b))

    for c,x in zip(graph[p], prod):
        if(c != parent[p]):
            dp2[c] = (x + 1)%mod




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


dp1 = [None] * (n+1)
for i in order[::-1]:
    calc1(i, parent[i])


dp2 = [None] * (n+1)
dp2[root] = ini
for i in order:
    calc2(i)

for i in range(1,n+1):
    ans = calc(dp1[i]-1, dp2[i])
    print(ans)

Solution (Python):
n,m,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for a,b in zip(*[iter(t)]*2):
  e[a-1]+=b-1,
  e[b-1]+=a-1,
o=[]
s=[0]
f=[1]*n
for v in s:
  o+=v,
  f[v]=0
  t=[]
  for w in e[v]:
    if f[w]:
      s+=w,
      t+=w,
  e[v]=t
dp1=[0]*n
c=[[]for _ in range(n)]
for v in o[::-1]:
  x,y=[1],[1]
  for w in e[v]:x+=x[-1]*(dp1[w]+1)%m,
  for w in e[v][::-1]:y+=y[-1]*(dp1[w]+1)%m,
  dp1[v]=x[-1]
  c[v]=x,y[-2::-1]
dp2=[1]+[0]*n
for v in o:
  for w,x,y in zip(e[v],*c[v]):dp2[w]=(dp2[v]*x*y+1)%m
for x,y in zip(dp1,dp2):print(x*y%m)

Solution (Python):
n,m,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for a,b in zip(*[iter(t)]*2):
  e[a-1]+=b-1,
  e[b-1]+=a-1,
o=[]
s=[0]
f=[1]*n
for v in s:
  o+=v,
  f[v]=0
  t=[]
  for w in e[v]:
    if f[w]:
      s+=w,
      t+=w,
  e[v]=t
dp1=[0]*n
c=[[]for _ in range(n)]
for v in o[::-1]:
  c1,c2=[1],[1]
  for w in e[v]:
    c1+=c1[-1]*(dp1[w]+1)%m,
  for w in e[v][::-1]:
    c2+=c2[-1]*(dp1[w]+1)%m,
  dp1[v]=c1[-1]
  c[v]=c1,c2[-2::-1]
dp2=[0]*n
dp2[0]=1
for v in o:
  t=dp2[v]
  for w,c1,c2 in zip(e[v],*c[v]):
    dp2[w]=(t*c1*c2+1)%m
for dp1,dp2 in zip(dp1,dp2):
  print(dp1*dp2%m)

Solution (Python):
class ReRooting:
    """
    0-indexed
    """
    def __init__(self, size, root=0, identDp=1, identCum=1):
        """
        identDp: 木DP用 lift(a, identDp) = a
        identCum: 累積用 merge(a, identCum) = a
        """
        self.size = size
        self.edges = [[] for _ in range(self.size + 1)]
        self.root = root
        self.identDp = identDp
        self.identCum = identCum

    def addEdge(self, fr, to):
        self.edges[fr].append(to)
        self.edges[to].append(fr)

    
    def lift(self, top, bottom):
        return top * (bottom + 1) % M

    
    def merge(self, left, right):
        return left * right % M

    def sol(self):
        N = self.size
        edges = self.edges

        st = [self.root]
        parent = [-1] * (N + 1)
        child = [[] for _ in range(N + 1)]
        order = []
        while st:
            v = st.pop()
            order.append(v)
            for to in edges[v]:
                if parent[v] == to:
                    continue
                parent[to] = v
                child[v].append(to)
                st.append(to)

        dp = [self.identDp] * (N + 1)
        left = [self.identCum] * (N + 1)
        right = [self.identCum] * (N + 1)
        for v in order[::-1]:  
            tmp = self.identCum
            for ch in child[v]:
                left[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            tmp = self.identCum
            for ch in reversed(child[v]):
                right[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            dp[v] = tmp

        fromParent = [0] * (N + 1)
        for v in order:
            if v == self.root:
                continue
            fromParent[v] = self.lift(self.merge(left[v], right[v]), fromParent[parent[v]])
            dp[v] = self.lift(dp[v], fromParent[v])  

        return dp[:N]

N, M = map(int, input().split())
tree = ReRooting(N, 0, 1, 1)

for _ in range(N - 1):
    fr, to = map(int, input().split())
    tree.addEdge(fr - 1, to - 1)

ans = tree.sol()
print(*ans, sep='\n')

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
N,M = map(int,input().split())
XY = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for i,(x,y) in enumerate(XY):
    x,y = x-1,y-1
    es[x].append((y,i))
    es[y].append((x,i))
if N==1:
    print(1)
    exit()

dpdn = [-1]*(N-1)
parent = [-1]*N
def dfs(v,p=-1):
    ret = 1
    for to,i in es[v]:
        if to==p: continue
        parent[to] = v
        r = dfs(to,v)
        dpdn[i] = r
        ret *= r
    ret += 1
    ret %= M
    return ret
dfs(0)

dpup = [-1]*(N-1)
from collections import deque
q = deque([(0,-1)])
while q:
    v,e = q.popleft()
    lc = [1]
    for _,i in es[v]:
        if i==e: continue
        lc.append((lc[-1] * dpdn[i]) % M)
    rc = [1]
    for _,i in reversed(es[v]):
        if i==e: continue
        rc.append((rc[-1] * dpdn[i]) % M)
    rc.reverse()
    p = 1 if e==-1 else dpup[e]
    j = 0
    for to,i in es[v]:
        if i==e: continue
        dpup[i] = (p * lc[j] * rc[j+1] + 1) % M
        j += 1
        q.append((to,i))

ans = []
for v in range(N):
    r = 1
    for to,i in es[v]:
        if to==parent[v]:
            r *= dpup[i]
        else:
            r *= dpdn[i]
    r %= M
    ans.append(r)
print(*ans, sep='\n')

Solution (Python):

import sys
input = sys.stdin.readline
from collections import deque

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

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)


unit = 1
merge = lambda a, b: a * b % mod
adj_bu = lambda a, i: a + 1
adj_td = lambda a, i, p: a + 1
adj_fin = lambda a, i: a


ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in R[1:][::-1]:
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i])
XX[R[0]] = adj_fin(ME[R[0]], R[0])




for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])
    ac = unit
    for j in X[i][::-1]:
        TD[j] = adj_td(merge(TD[j], ac), j, i)
        ac = merge(ac, XX[j])
        XX[j] = adj_fin(merge(ME[j], TD[j]), j)




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

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



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


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

DP1 = [0] * (N + 1)

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

order = []
order_append = order.append

stack = [1]
stack_pop = stack.pop
stack_append = stack.append

while stack:
    x = stack_pop()
    order_append(x)
    for next_ in G[x]:
        if next_ == parent[x]:
            continue
        parent[next_] = x
        stack_append(next_)

for v in order[::-1]:
    tmp = 1
    for next_ in G[v]:
        tmp *= DP1[next_] + 1
        tmp %= MOD
    DP1[v] = tmp


DP2 = [1] * (N + 1)

for x in order:
    
    
    n = len(G[x])
    p = parent[x]
    lst1 = [1] * (n + 1)
    lst2 = [1] * (n + 1)
    for i in range(n):
        
        if G[x][i] == p:
            lst1[i + 1] = lst1[i] * DP2[x] % MOD
        else:
            lst1[i + 1] = lst1[i] * (DP1[G[x][i]] + 1) % MOD

        if G[x][n - 1 - i] == p:
            lst2[n - i - 1] = lst2[n - i] * DP2[x] % MOD
        else:
            lst2[n - i - 1] = lst2[n - i] * (DP1[G[x][n - 1 - i]] + 1) % MOD
    
    for i in range(n):
        if G[x][i] == p:
            continue
        tmp = lst1[i] * lst2[i + 1] % MOD
        tmp += 1 
        DP2[G[x][i]] = tmp
        



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

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



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


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

DP1 = [0] * (N + 1)

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

order = []
order_append = order.append

stack = [1]
stack_pop = stack.pop
stack_append = stack.append

while stack:
    x = stack_pop()
    order_append(x)
    for next_ in G[x]:
        if next_ == parent[x]:
            continue
        parent[next_] = x
        stack_append(next_)

for v in order[::-1]:
    tmp = 1
    for next_ in G[v]:
        tmp *= DP1[next_] + 1
        tmp %= MOD
    DP1[v] = tmp


DP2 = [1] * (N + 1)

for x in order:
    
    
    n = len(G[x])
    lst1 = [1] * (n + 1)
    lst2 = [1] * (n + 1)
    for i in range(n):
        
        if G[x][i] == parent[x]:
            lst1[i + 1] = lst1[i] * DP2[x] % MOD
        else:
            lst1[i + 1] = lst1[i] * (DP1[G[x][i]] + 1) % MOD

        if G[x][n - 1 - i] == parent[x]:
            lst2[n - i - 1] = lst2[n - i] * DP2[x] % MOD
        else:
            lst2[n - i - 1] = lst2[n - i] * (DP1[G[x][n - 1 - i]] + 1) % MOD
    
    for i in range(n):
        if G[x][i] == parent[x]:
            continue
        tmp = lst1[i] * lst2[i + 1] % MOD
        tmp += 1 
        DP2[G[x][i]] = tmp
        



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

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

sys.setrecursionlimit(10 ** 7)

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


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

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

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

dfs(1, 0)


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


while stack:
    x = stack.pop()

    

    
    n = len(G[x])
    lst1 = [1] * (n + 1)
    lst2 = [1] * (n + 1)
    for i in range(n):
        
        if G[x][i] == parent[x]:
            lst1[i + 1] = lst1[i] * DP2[x] % MOD
        else:
            lst1[i + 1] = lst1[i] * (DP1[G[x][i]] + 1) % MOD

        if G[x][n - 1 - i] == parent[x]:
            lst2[n - i - 1] = lst2[n - i] * DP2[x] % MOD
        else:
            lst2[n - i - 1] = lst2[n - i] * (DP1[G[x][n - 1 - i]] + 1) % MOD
    
    for i in range(n):
        if G[x][i] == parent[x]:
            continue
        tmp = lst1[i] * lst2[i + 1] % MOD
        tmp += 1 
        DP2[G[x][i]] = tmp % MOD
        stack.append(G[x][i])



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

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

sys.setrecursionlimit(10 ** 7)

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


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

DP1 = [0] * (N + 1)

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

order = []

stack = [1]
while stack:
    x = stack.pop()
    order.append(x)
    for next_ in G[x]:
        if next_ == parent[x]:
            continue
        parent[next_] = x
        stack.append(next_)

for v in order[::-1]:
    tmp = 1
    for next_ in G[v]:
        tmp *= DP1[next_] + 1
        tmp %= MOD
    DP1[v] = tmp


DP2 = [1] * (N + 1)

for x in order:
    
    
    n = len(G[x])
    lst1 = [1] * (n + 1)
    lst2 = [1] * (n + 1)
    for i in range(n):
        
        if G[x][i] == parent[x]:
            lst1[i + 1] = lst1[i] * DP2[x] % MOD
        else:
            lst1[i + 1] = lst1[i] * (DP1[G[x][i]] + 1) % MOD

        if G[x][n - 1 - i] == parent[x]:
            lst2[n - i - 1] = lst2[n - i] * DP2[x] % MOD
        else:
            lst2[n - i - 1] = lst2[n - i] * (DP1[G[x][n - 1 - i]] + 1) % MOD
    
    for i in range(n):
        if G[x][i] == parent[x]:
            continue
        tmp = lst1[i] * lst2[i + 1] % MOD
        tmp += 1 
        DP2[G[x][i]] = tmp % MOD
        stack.append(G[x][i])



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

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

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

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

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

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

if __name__=='__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
 
N, M = map(int, input().split())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)


unit = 1
merge = lambda a, b, m: a * b % m
adj_bu = lambda a, i: a + 1
adj_td = lambda a, i: a + 1


ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in R[1:][::-1]:
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i], M)
XX[R[0]] = adj_bu(ME[R[0]], R[0])

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j], M)
    ac = unit
    for j in X[i][::-1]:
        TD[j] = adj_td(merge(TD[j], ac, M), i)
        ac = merge(ac, XX[j], M)
        XX[j] = adj_bu(merge(ME[j], TD[j], M), j)

print(*[x - 1 for x in XX], sep = "\n")

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
 
N, M = map(int, input().split())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)


unit = 1
merge = lambda a, b: a * b % M
adj_bu = lambda a, i: a + 1
adj_td = lambda a, i: a + 1


ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in R[1:][::-1]:
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i])
XX[R[0]] = adj_bu(ME[R[0]], R[0])

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])
    ac = unit
    for j in X[i][::-1]:
        TD[j] = adj_td(merge(TD[j], ac), i)
        ac = merge(ac, XX[j])
        XX[j] = adj_bu(merge(ME[j], TD[j]), j)

print(*[x - 1 for x in XX], sep = "\n")

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque

nn = 200200
mod = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % mod
fainv[-1] = pow(fa[-1], mod-2, mod)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % mod

inv = lambda i: fainv[i] * fa[i-1] % mod

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

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)


unit = 1
td_unit = 1
merge = lambda a, b: a * b % mod
adj_bu = lambda a, i=-1: a + 1
adj_td = lambda a, i=-1: a + 1
calc = lambda i: merge(BU[i]-1, TD[i])


SI = [1] * N
for i in R[1:][::-1]:
    SI[P[i]] += SI[i]

BU = [unit] * N
TD = [td_unit] * N
for i in R[1:][::-1]:
    BU[i] = adj_bu(BU[i], i)
    p = P[i]
    BU[p] = merge(BU[p], BU[i])
BU[R[0]] = adj_bu(BU[R[0]], R[0])

AX = [0] * N
for i in R:
    ac = unit
    for j in X[i]:
        AX[j] = ac
        ac = merge(ac, BU[j])
    ac = unit
    for j in X[i][::-1]:
        AX[j] = merge(AX[j], ac)
        TD[j] = adj_td(merge(merge(unit, TD[i]), AX[j]), j)
        ac = merge(ac, BU[j])

ANS = [calc(i) for i in range(N)]
print(*ANS)

Solution (Python):
import sys
input=sys.stdin.readline
from collections import deque
def main():
    n,mod=map(int,input().split())
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(int,input().split())
        x-=1; y-=1
        Edges[x].append(y)
        Edges[y].append(x)
    Stack=[0]
    Par=[-1]*n
    Order=[]
    while Stack:
        v=Stack.pop()
        Order.append(v)
        for c in Edges[v]:
            if c!=Par[v]:
                Stack.append(c)
                Par[c]=v
    child = set()
    DP=[1]*n
    for v in Order[::-1]:
        for to in Edges[v]:
            if to==Par[v]:
                continue
            DP[v]*=DP[to]+1
            DP[v]%=mod
    Ans=[0]*n
    que=deque()
    que.append((0,-1,1))
    while que:
        v,par,par_cnt=que.popleft()
        Left=[1]
        for to in Edges[v]:
            tmp=DP[to]
            if to==par:
                tmp=par_cnt
            Left.append(Left[-1]*(tmp+1)%mod)
        Right=[1]
        for to in reversed(Edges[v]):
            tmp=DP[to]
            if to==par:
                tmp=par_cnt
            Right.append(Right[-1]*(tmp+1)%mod)
        Ans[v]=Left[-1]
        m=len(Edges[v])
        for i,to in enumerate(Edges[v]):
            if to!=par:
                que.append((to,v,Left[i]*Right[m-i-1]%mod))
    print(*Ans,sep="\n")

if __name__=='__main__':
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')

N, M = MAP()
mod = M

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

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

dp_d = [0]*(N+1)

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

dp = [1 for _ in range(n)]
def dfs1(x, p):
	for c in adj[x]:
		if c == p:
			continue
		dfs1(c, x)
		dp[x] *= dp[c]+1
		dp[x] %= m
	return

dfs1(0, -1)
ans = [0 for _ in range(n)]
ans[0] = dp[0]
def dfs2(x, p):
	l = len(adj[x])
	cuml = [1 for _ in range(l+2)]
	cumr = [1 for _ in range(l+2)]
	for i in range(l):
		cuml[i+1] = (cuml[i] * (dp[adj[x][i]] + 1)) % m
	for i in range(l-1, -1, -1):
		cumr[i+1] = (cumr[i+2] * (dp[adj[x][i]] + 1)) % m
	pres_x = dp[x]
	for i, c in enumerate(adj[x]):
		if c == p:
			continue
		pres_c = dp[c]
		dp[x] = (cuml[i] * cumr[i+2]) % m
		dp[c] *= dp[x] + 1
		dp[c] %= m
		ans[c] = dp[c]
		dfs2(c, x)
		dp[x] = pres_x
		dp[c] = pres_c
	return

dfs2(0, -1)
print(*ans, sep="\n")