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:
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)]  # 1-indexed
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")

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    """ここから変更"""
    # op: 普通に根を固定した木DPで子の情報を親に集めるときの演算
    def op(a, b):
        return (a * (b + 1))%mod

    # cum_merge: 累積opどうしをマージするときの演算
    def cum_merge(a, b):
        return (a * b)%mod
    """ここまで変更"""

    # root=1でまず普通に木DPをする
    # 並行して各頂点につき、子の値の累積opを左右から求めておく
    # その後根から順番に、親からの寄与を求めていく(from_par)
    def Rerooting(adj):
        N = len(adj) - 1
        st = [1]
        seen = [0] * (N + 1)
        seen[1] = 1
        par = [0] * (N + 1)
        child = [[] for _ in range(N + 1)]
        seq = []
        while st:
            v = st.pop()
            seq.append(v)
            for u in adj[v]:
                if not seen[u]:
                    seen[u] = 1
                    par[u] = v
                    child[v].append(u)
                    st.append(u)
        seq.reverse()
        dp = [1] * (N + 1)
        left = [1] * (N + 1)
        right = [1] * (N + 1)
        for v in seq:
            tmp = 1
            for u in child[v]:
                left[u] = tmp
                tmp = op(tmp, dp[u])
            tmp = 1
            for u in reversed(child[v]):
                right[u] = tmp
                tmp = op(tmp, dp[u])
            dp[v] = tmp

        seq.reverse()
        from_par = [0] * (N + 1)
        for v in seq:
            if v == 1:
                continue
            from_par[v] = op(cum_merge(left[v], right[v]), from_par[par[v]])
            dp[v] = op(dp[v], from_par[v])

        return dp

    dp = Rerooting(adj)
    for i in range(1, N+1):
        print(dp[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# †全方位木DP†

import sys
input = lambda : sys.stdin.readline().strip()

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

from collections import deque
def dfs(root):
    que = deque()
    que.append((root, -1))
    order = []
    while que:
        cur,prev = que.popleft()
        order.append(cur)
        for to in G[cur]:
            if to != prev:
                que.append((to, cur))
    return order

order = dfs(0)

child = set()
down = [1]*n
for cur in reversed(order):
    tmp = 1
    for to in G[cur]:
        if to in child:
            tmp *= (down[to]+1)
            tmp %= mod
    down[cur] = tmp
    child.add(cur)

ans = [0]*n
que = deque()
que.append((0, -1, 1))
while que:
    cur, prev, parent = que.popleft()

    left = [1]
    for to in G[cur]:
        tmp = down[to]
        if to == prev:
            tmp = parent
        left.append(left[-1]*(tmp+1)%mod)

    right = [1]
    for to in reversed(G[cur]):
        tmp = down[to]
        if to == prev:
            tmp = parent
        right.append(right[-1]*(tmp+1)%mod)
    ans[cur] = left[-1]

    m = len(G[cur])
    for i, to in enumerate(G[cur]):
        if to != prev:
            que.append((to, cur, left[i]*right[m-i-1]))

print(*ans, 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)

BU = [0] * N
TD = [1] * N
for i in R[::-1]:
    a = 1
    for j in X[i]:
        a = a * (BU[j] + 1) % M
    BU[i] = a
for i in R:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    for j in range(c):
        AL[j+1] = AL[j] * (BU[X[i][j]] + 1) % M
    for j in range(c)[::-1]:
        AR[j] = AR[j+1] * (BU[X[i][j]] + 1) % M
    for j in range(c):
        TD[X[i][j]] = (TD[i] * AL[j] * AR[j+1] + 1) % M

for i in range(N):
    print(BU[i] * TD[i] % M)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

from collections import deque
from functools import reduce
f = lambda a: (a+1) % M
g = lambda a, b: a * b % M
init = 1

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])
T = []
while Q:
    i = deque.popleft(Q)
    T.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BU = [0] * N # Bottom Up
TD = [1] * N # Top Down
for i in T[::-1]:
    BU[i] = reduce(g, [f(BU[j]) for j in X[i]]) if len(X[i]) else init

for i in T:
    B = [1] * (len(X[i]) + 1)
    for k, j in enumerate(X[i]):
        B[k+1] = g(B[k], f(BU[j]))
    a = init
    for k in range(len(X[i]))[::-1]:
        j = X[i][k]
        TD[j] = f(g(TD[i], g(a, B[k])))
        a = g(a, f(BU[j]))

for t in [g(a, b) for a, b in zip(BU, TD)]:
    print(t)

Submission status: Accepted

Solution code:
from collections import deque
from functools import reduce
f = lambda a: (a+1) % M
g = lambda a, b: a * b % M
init = 1

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])
T = []
while Q:
    i = deque.popleft(Q)
    T.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BU = [0] * N # Bottom Up
TD = [1] * N # Top Down
for i in T[::-1]:
    BU[i] = reduce(g, [f(BU[j]) for j in X[i]]) if len(X[i]) else init

for i in T:
    B = [1] * (len(X[i]) + 1)
    for k, j in enumerate(X[i]):
        B[k+1] = g(B[k], f(BU[j]))
    a = init
    for k in range(len(X[i]))[::-1]:
        j = X[i][k]
        TD[j] = f(g(TD[i], g(a, B[k])))
        a = g(a, f(BU[j]))

for t in [g(a, b) for a, b in zip(BU, TD)]:
    print(t)

Submission status: Accepted

Solution code:
from collections import deque
from functools import reduce
def f(a):
    return (a + 1) % M
def g(a, b):
    return a * b % M
init = 1

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])
T = []
while Q:
    i = deque.popleft(Q)
    T.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BU = [0] * N # Bottom Up
TD = [1] * N # Top Down
for i in T[::-1]:
    BU[i] = reduce(g, [f(BU[j]) for j in X[i]]) if len(X[i]) else init

for i in T:
    B = [1] * (len(X[i]) + 1)
    for k, j in enumerate(X[i]):
        B[k+1] = g(B[k], f(BU[j]))
    a = init
    for k in range(len(X[i]))[::-1]:
        j = X[i][k]
        TD[j] = f(g(TD[i], g(a, B[k])))
        a = g(a, f(BU[j]))

for t in [g(a, b) for a, b in zip(BU, TD)]:
    print(t)

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)

A = [0] * N
AA = [1] * N
for i in R[::-1]:
    a = 1
    for j in X[i]:
        a = a * (A[j] + 1) % M
    A[i] = a
for i in R:
    B = [1] * (len(X[i]) + 1)
    for j in range(len(X[i])):
        B[j+1] = B[j] * (A[X[i][j]] + 1) % M
    a = 1
    for j in range(len(X[i]))[::-1]:
        t = a * B[j]
        a = a * (A[X[i][j]] + 1) % M
        AA[X[i][j]] = (AA[i] * t + 1) % M

for t in [a * aa % M for a, aa in zip(A, AA)]:
    print(t)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

    st = [1]
    seen = [0] * (N+1)
    seen[1] = 1
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while st:
        v = st.pop()
        seq.append(v)
        for u in adj[v]:
            if not seen[u]:
                seen[u] = 1
                par[u] = v
                child[v].append(u)
                st.append(u)
    seq.reverse()
    dp = [1] * (N+1)
    left = [1] * (N+1)
    right = [1] * (N+1)
    for v in seq:
        tmp = 1
        for u in child[v]:
            left[u] = tmp
            tmp = (tmp * (dp[u] + 1)) % mod
        tmp = 1
        for u in reversed(child[v]):
            right[u] = tmp
            tmp = (tmp * (dp[u] + 1)) % mod
        dp[v] = tmp

    seq.reverse()
    dp2 = [0] * (N+1)
    for v in seq:
        if v == 1:
            continue
        dp2[v] = ((left[v] * right[v])%mod * (dp2[par[v]]+1))%mod
        dp[v] = (dp[v] * (dp2[v]+1))%mod

    for i in range(1, N+1):
        print(dp[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
d = [list() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

queue=deque([1])
vs = set([1])
vs_bfs = list()
parents = [0] * (N+1)
while queue:
    v = queue.popleft()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        queue.append(u)

dp = [0 for _ in range(N+1)]
dpl = [1 for _ in range(N+1)]
dpr = [1 for _ in range(N+1)]
for v in vs_bfs[::-1]:
    t = 1
    for u in d[v]:
        if u == parents[v]:
            continue
        dpl[u] = t
        t = (t * (dp[u]+1)) % M
    t = 1
    for u in d[v][::-1]:
        if u == parents[v]:
            continue
        dpr[u] = t
        t = (t * (dp[u]+1)) % M
    dp[v] = t

dp2 = [0]*(N+1)
for v in vs_bfs:
    if v == 1:
        dp2[v] = 1
        continue
    p = parents[v]
    dp2[v] = (dp2[p] * (dpl[v]*dpr[v]) +1)% M
#    print(dp2[p] * (dpl[v]*dpr[v]))
#    dp2[v] = dp2[p] %M
r = [0]*N
for i in range(1, N+1):
    r[i-1] = str(dp[i] * dp2[i] % M)
print("\n".join(r))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    g = Graph(N)
    for xx, yy in zip(x, y):
        g.add_edge(xx-1, yy-1)
        g.add_edge(yy-1, xx-1)

    dp = [0]*N

    def dfs(node, par=-1):
        dp[node] = 1
        for child, _ in g.E[node]:
            if child == par:
                continue
            dp[node] *= dfs(child, node) + 1
            dp[node] %= M
        return dp[node]

    ans = [0]*N

    def dfs_2(node, par=-1):
        ans[node] = 1
        for child, _ in g.E[node]:
            ans[node] *= dp[child]+1
            ans[node] %= M

        # 一要素を覗いた積を求めるため、昇順の積、降順の積を求めておく
        K = len(g.E[node])
        left, right = [1]*K, [1]*K
        for i in range(K):
            t, w = g.E[node][i]
            left[i] = left[i-1]*(dp[t]+1)
            left[i] %= M
        for i in range(K-1, -1, -1):
            t, w = g.E[node][i]
            if i != K-1:
                right[i] = right[i+1]*(dp[t]+1)
            else:
                right[i] = dp[t]+1
            right[i] %= M

        for i in range(K):
            child, _ = g.E[node][i]
            if child == par:
                continue
            dp[node] = 1
            if i:
                dp[node] *= left[i-1]
            if i+1 < K:
                dp[node] *= right[i+1]
            dp[node] %= M
            dfs_2(child, node)
    dfs(0)
    dfs_2(0)

    for a in ans:
        print(a % M)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    x = [int()] * (N - 1)  # type: "List[int]"
    y = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


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

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



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


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

# 木上のdfsの行きがけ順
preorder_list = topological_sort(0, par=-1)

# subtreeから値を集める
st_val = [0] * n
for pos, par in reversed(preorder_list):
    dfs1(pos, par)

# rerootによって、subtreeから値を集める。
re_subtree_val = [[1] * len(tree[i]) for i in range(n)]

# 左右それぞれの累積
ruiseki_l = [[1] * (len(tree[i]) + 1) for i in range(n)]
ruiseki_r = [[1] * (len(tree[i]) + 1) for i in range(n)]

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

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

Submission status: Accepted

Solution code:
from collections import *
import sys

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

n, m = MI()
to = defaultdict(list)
# dp[u][v] uを根としたときのサブツリーvの値
dp = {}

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

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    dfs()
    # bfsでdfsとは逆向きのdpを完成させる
    que = deque()
    que.append([0, -1])
    while que:
        u, pu = que.popleft()
        tn = len(to[u])
        # 累積積のための配列
        ll = [0] * tn
        rr = [0] * tn
        # uのサブツリーの値+1を入れる
        for i, v in enumerate(to[u]):
            ll[i] = rr[i] = dp[(u,v)] + 1
        # 左右から累積積を作る
        for i in range(1, tn):
            ll[i] = (ll[i - 1] * ll[i]) % m
            rr[tn - 1 - i] = (rr[tn - i] * rr[tn - 1 - i]) % m
        # 配列の最初or最後のために最後に1を追加
        ll += [1]
        rr += [1]
        # uの子vを根とみたときのサブツリーuの値を求める
        for i, v in enumerate(to[u]):
            if v == pu: continue
            dp[(v,u)] = (ll[i - 1] * rr[i + 1]) % m
            que.append([v, u])
    # p2D(dp)
    # 各頂点について答えを出す
    for u in range(n):
        ans = 1
        for v in to[u]:
            ans = (ans * (dp[(u,v)] + 1)) % m
        print(ans)

main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

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

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

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

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

# 自身を黒く塗ったときの根側
dp1 = [0]*(N+1)

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

# 親側
dp2 = [1]*(N+1)

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)

def dfs1(v,p):
    val=1
    pre_mul=[1]
    rev_mul=[]
    for c in links[v]:
        if c==p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res=1+dfs1(c,v)
        val*=res
        val%=m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v]=val
    for i in range(len(rev_mul)-2,-1,-1):
        rev_mul[i]*=rev_mul[i+1]
        rev_mul[i]%=m
    rev_mul.append(1)
    pre_muls[v]=[pre_mul,rev_mul]
    return val

def dfs2(v,p,a):
    dp[v]=dp[v]*a%m
    pmv=pre_muls[v]
    for i,c in enumerate(links[v]):
        if c==p:
            continue
        pmc=pmv[0][i]*pmv[1][i+1]%m
        pmc=pmc*a%m
        dfs2(c,v,pmc+1)

n,m=map(int,input().split())
links=[[] for _ in range(n)]
dp=[0 for _ in range(n)]
pre_muls=[None for _ in range(n)]
for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].append(y)
    links[y].append(x)
dfs1(0,None)
dfs2(0,None,1)
print('\n'.join(map(str,dp)))

Submission status: Accepted

Solution code:
#全方位木DPによって求める
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


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


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


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


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


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

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

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

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

for num in b2:
    print(num % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

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


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

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

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

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

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

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

dfs(0,-1)
#print(dp)
dfs2(0,0,-1)
#print(dp)
for i in ans:
    print(i)

Submission status: Accepted

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

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

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

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v].discard(parent)
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

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

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

Submission status: Accepted

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

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

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


        

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

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

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

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

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


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

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

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

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

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

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

dfs(0,-1)
#print(dp)
dfs2(0,0,-1)
#print(dp)
for i in ans:
    print(i)