Problem:


Score : 100 points

Problem Statement

There is a tree with N vertices, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N - 1), the i-th edge connects Vertex x_i and y_i.

Taro has decided to paint each vertex in white or black, so that any black vertex can be reached from any other black vertex by passing through only black vertices.

You are given a positive integer M.
For each v (1 \leq v \leq N), answer the following question:

Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

2 \leq M \leq 10^9

1 \leq x_i, y_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N M
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}

Output

Print N lines.
The v-th (1 \leq v \leq N) line should contain the answer to the following question:

Assuming that Vertex v has to be black, find the number of ways in which the vertices can be painted, modulo M.

Sample Input 1

3 100
1 2
2 3

Sample Output 1

3
4
3

There are seven ways to paint the vertices, as shown in the figure below.
Among them, there are three ways such that Vertex 1 is black, four ways such that Vertex 2 is black and three ways such that Vertex 3 is black.

Sample Input 2

4 100
1 2
1 3
1 4

Sample Output 2

8
5
5
5

Sample Input 3

1 100

Sample Output 3

1

Sample Input 4

10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

Sample Output 4

0
0
1
1
1
0
1
0
1
1

Be sure to print the answers modulo M.



Sample input:
3 100
1 2
2 3


Sample output:
3
4
3

Submission status: Accepted

Solution code:
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:
            # 左からaccTDを更新
            ac = resTD[p]
            for v in self.edge[p]:
                accTD[v] = ac
                ac = self.merge(ac, resBU[v])

            # 右からaccTDを更新
            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()
        #self.subtree_size()
        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")

Submission status: Accepted

Solution code:
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:
            # 左からaccTDを更新
            ac = resTD[p]
            for v in self.edge[p]:
                accTD[v] = ac
                ac = self.merge(ac, resBU[v])

            # 右からaccTDを更新
            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")

Submission status: Accepted

Solution code:
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")

Submission status: Accepted

Solution code:
# 参考 -> https://atcoder.jp/contests/dp/submissions/8271798

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[i] : 頂点iを黒く塗ったときの子側の塗り方
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[i] : 頂点iを黒く塗ったときの親側の塗り方
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]]
  # それぞれの子(=c)について、自身を根とする下側の部分木を除いた積
  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 # (+1 : cより上側が全て白である場合を足し合わせる)

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
mod = m
# mod = 10**9+7

# 前準備
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

# calc1 の定義
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

# calc2 の定義
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

    # 根を固定したときの木DP(貰うDP)
    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]:  # 貰うDPしつつ，累積をとる
            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])  # 最後に親からの貰うDP

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

Submission status: Accepted

Solution code:
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')

Submission status: Accepted

Solution code:
# 全方位木DP
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)

##### Settings
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])

# print("ME =", ME) # Merge before adj
# print("XX =", XX) # Bottom-up after adj

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("TD =", TD) # Top-down after adj
# print("XX =", XX) # Final Result

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

Submission status: Accepted

Solution code:
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 = []
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
# print (DP1)

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
        # stack.append(G[x][i])

# print (DP2)

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

# print (DP1)
# print (DP2)

Submission status: Accepted

Solution code:
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 = []
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
# print (DP1)

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
        # stack.append(G[x][i])

# print (DP2)

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

# print (DP1)
# print (DP2)

Submission status: Accepted

Solution code:
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)
# print (DP1)

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

#next_とyとで2重ループになってO(N^2) (星型のとき)
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])

# print (DP2)

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

# print (DP1)
# print (DP2)

Submission status: Accepted

Solution code:
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
# print (DP1)

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

# print (DP2)

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

# print (DP1)
# print (DP2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

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

Submission status: Accepted

Solution code:
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)

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

Submission status: Accepted

Solution code:
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)

##### Settings
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)

Submission status: Accepted

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