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 itertools
import sys
import heapq
sys.setrecursionlimit(10**5 + 1)
n, m = map(int, input().split())

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

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

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

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


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

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


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

Submission status: Accepted

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


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

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

    def calc(self, v):
        # The following formula is calculated by bottom-up:
        self.result[self.parent[v]] *= self.result[v]+1
        self.result[self.parent[v]] %= m
        return None

    def wanted(self):
        # Edit the item you want by using self.depth, self.subsize, etc..
        # Default : self.parent
        return self.parent

    def rerooting(self) -> list:
        # Modify below if you want to use rerooting
        ans = [0]*n
        ans[self.root] = self.result[self.root]

        cum1 = [[1] for i in range(n)]  # 0 : additive, 1 : multiplicative
        cum2 = [[1] for i in range(n)]  # 0 : additive, 1 : multiplicative
        FromParent = [0]*n

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

            # accumulate nbhd's result from the left side
            for w in self.g[v]:
                if w != self.parent[v]:
                    cum1[v].append(cum1[v][-1]*(self.result[w]+1) % m)
                    s.append(w)
                else:
                    cum1[v].append(cum1[v][-1]*(FromParent[v]+1) % m)

            # accumulate nbhd's result from the right side
            for w in self.g[v][::-1]:
                if w != self.parent[v]:
                    cum2[v].append(cum2[v][-1]*(self.result[w]+1) % m)
                else:
                    cum2[v].append(cum2[v][-1]*(FromParent[v]+1) % m)
            cum2[v] = cum2[v][::-1]

            # calculate the sub-result for parent's subtree when you see the child as root.
            # get the answer for each child.
            for i, w in enumerate(self.g[v]):
                if w != self.parent[v]:
                    FromParent[w] = cum1[v][i]*cum2[v][i+1] % m
                    ans[w] = (FromParent[w]+1) * self.result[w]
                    ans[w] %= m
        return ans


n, m = map(int, input().split())
g = [[] for _ in range(n)]

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

T1 = Tree(n, g, 0)

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

Submission status: Accepted

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


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

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

    def calc(self, v):
        # The following formula is calculated by bottom-up:
        self.result[self.parent[v]] *= self.result[v]+1
        self.result[self.parent[v]] %= m
        return None

    def wanted(self):
        # Edit the result you want using self.depth, self.subsize, etc..
        # Default : self.parent
        return self.parent

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

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

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

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

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


n, m = map(int, input().split())
g = [[] for _ in range(n)]

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


T1 = Tree(n, g, 0)

ans = T1.rerooting()


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

Submission status: Accepted

Solution code:
def reroot(nodeCount, edges, identity, merge, addNode, root=0):
    adjacents = [list() for _ in range(nodeCount)]
    indexForAdjacents = [list() for _ in range(nodeCount)]
    for u, v in edges:
        indexForAdjacents[u].append(len(adjacents[v]))
        indexForAdjacents[v].append(len(adjacents[u]))
        adjacents[u].append(v)
        adjacents[v].append(u)
    childSubtreeRes = [[identity]*len(adjacents[i]) for i in range(nodeCount)]
    nodeRes = [identity]*nodeCount

    parents = [-1]*nodeCount
    order = [0]*nodeCount
    index = 0
    stack = [root]
    while stack:
        node = stack.pop()
        order[index] = node
        index += 1
        for adjacent in adjacents[node]:
            if adjacent == parents[node]:
                continue
            stack.append(adjacent)
            parents[adjacent] = node

    for node in reversed(order):
        parent = parents[node]
        result = identity
        parentIndex = -1
        for j in range(len(adjacents[node])):
            if adjacents[node][j] == parent:
                parentIndex = j
                continue
            result = merge(result, childSubtreeRes[node][j])
        if parentIndex >= 0:
            childSubtreeRes[parent][indexForAdjacents[node][parentIndex]] = addNode(result, node)

    for node in order:
        accumsFromTail = [identity]*len(adjacents[node])
        for j in range(len(adjacents[node]) - 1, 0, -1):
            accumsFromTail[j - 1] = merge(childSubtreeRes[node][j], accumsFromTail[j])
        accum = identity
        for j in range(len(adjacents[node])):
            result = addNode(merge(accum, accumsFromTail[j]), node)
            childSubtreeRes[adjacents[node][j]][indexForAdjacents[node][j]] = result
            accum = merge(accum, childSubtreeRes[node][j])
        nodeRes[node] = addNode(accum, node)
    return nodeRes

int1 = lambda x: int(x) - 1
n, mod = map(int, input().split())
merge = lambda u, v: u * v % mod
addNode = lambda val, id: val + 1
edges = [tuple(map(int1, input().split())) for _ in range(n-1)]
res = list(map(int1, reroot(n, edges, 1, merge, addNode)))
print(*res, sep='\n')

Submission status: Accepted

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

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]

    class rerooting():
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini, monoid, add):
            # 頂点iについて、jが根のときのDPの値を求める（アクセス時間を考慮してここで定義）
            def calc(i, j):
                root = tree_d[i][j]+1
                try:
                    return monoid(tc_l[i][root-1], tc_r[i][root])
                except:
                    return tc_l[i][root-1]
            size = len(tree)
            dp, order, q, anc = [ini]*size, [], [0], [-1]*n
            oa, qa, qp = order.append, q.append, q.pop
            tree_d = [{k: j for j, k in enumerate(i)} for i in g]
            g_size = [len(i) for i in g]
            tc_l = [[ini]*(i+1) for i in g_size]
            tc_r = [[ini]*i for i in g_size]

            # トポロジカル順序をorderに記録、0を根とする根付き木上のiの祖先をanc[i]とする
            while q:
                i = qp()
                a = anc[i]
                oa(i)
                for j in g[i]:
                    if j != a:
                        qa(j)
                        anc[j] = i

            # dpおよびtree_preに記録
            for i in order[:0:-1]:
                a = anc[i]
                d, t = add(a, i, dp[i]), tree_d[a][i]
                tc_l[a][t+1], tc_r[a][t], dp[a] = d, d, monoid(dp[a], d)

            # 頂点0のみ先に処理
            for j in range(1, g_size[0]+1):
                tc_l[0][j] = monoid(tc_l[0][j], tc_l[0][j-1])
            for j in range(g_size[0]-2, 0, -1):
                tc_r[0][j] = monoid(tc_r[0][j], tc_r[0][j+1])

            # 行きがけ順に処理
            for i in order[1:]:
                a = anc[i]
                d, c, length = tree_d[i][a], add(a, i, calc(a, i)), g_size[i]
                tc_l[i][d+1], tc_r[i][d] = c, c
                for j in range(1, length+1):
                    tc_l[i][j] = monoid(tc_l[i][j], tc_l[i][j-1])
                for j in range(length-2, 0, -1):
                    tc_r[i][j] = monoid(tc_r[i][j+1], tc_r[i][j])
                dp[i] = tc_l[i][-1]

            # アトリビュートに格納
            self.dp, self.tc_l, self.tc_r, self.tree_d, self.monoid = dp, tc_l, tc_r, tree_d, monoid

        # 頂点iについて、jが根のときのDPの値を求める

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

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

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


main()

Submission status: Accepted

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

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

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

        # monoid に対する cumulative sum を計算
        if cum_left[v] is None:
            k = len(E[v])
            left = [1] * (k + 1)
            right = [1] * (k + 1)
            for i in range(k):
                left[i + 1] = left[i] * (dp[E[v][i]] + 1) % MOD
            for i in range(k - 1, -1, -1):
                right[i] = right[i + 1] * (dp[E[v][i]] + 1) % MOD
            cum_left[v] = left
            cum_right[v] = right

        # dp[v] を v-rooted に modify
        dp[v] = cum_left[v][-1]

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

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

Submission status: Accepted

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

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

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

        # monoid に対する cumulative sum を計算
        if cum_left[v] is None:
            k = len(E[v])
            left = [1] * (k + 1)
            right = [1] * (k + 1)
            for i in range(k):
                left[i + 1] = left[i] * (dp[E[v][i]] + 1) % MOD
            for i in range(k - 1, -1, -1):
                right[i] = right[i + 1] * (dp[E[v][i]] + 1) % MOD
            cum_left[v] = left
            cum_right[v] = right

        # dp[v] を v-rooted に modify
        dp[v] = cum_left[v][-1]

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

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

Submission status: Accepted

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

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

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

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

        # monoid に対する cumulative sum を計算
        if cum_left[v] is None:
            left = [(dp[nv] + 1) % MOD for nv in E[v]]
            right = [(dp[nv] + 1) % MOD for nv in E[v]]
            k = len(E[v])
            for i in range(k - 1):
                left[i + 1] *= left[i]
                left[i + 1] %= MOD
            for i in range(k - 1, 0, -1):
                right[i - 1] *= right[i]
                right[i - 1] %= MOD
            cum_left[v] = left
            cum_right[v] = right
        dp[v] = cum_left[v][-1]

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

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

Submission status: Accepted

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

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

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

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

    # rerooting
    def rerooting(v, p):
        # rerooting を先に済ませる
        if p != -1 and v != -1:
            idx = nv_to_idx[p][v]
            p_res = 1
            if idx > 0:
                p_res *= cum_left[p][idx - 1]
            if idx < len(E[p]) - 1:
                p_res *= cum_right[p][idx + 1]
            dp[p] = p_res % MOD

        # monoid に対する cumulative sum を計算
        if cum_left[v] is None:
            left = [(dp[nv] + 1) % MOD for nv in E[v]]
            right = [(dp[nv] + 1) % MOD for nv in E[v]]
            k = len(E[v])
            for i in range(k - 1):
                left[i + 1] *= left[i]
                left[i + 1] %= MOD
            for i in range(k - 1, 0, -1):
                right[i - 1] *= right[i]
                right[i - 1] %= MOD
            cum_left[v] = left
            cum_right[v] = right
        dp[v] = cum_left[v][-1]

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

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

Submission status: Accepted

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

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

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

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

    # rerooting
    def rerooting(v, p):
        # rerooting を先に済ませる
        if p != -1 and v != -1:
            idx = nv_to_idx[p][v]
            p_res = 1
            if idx > 0:
                p_res *= cum_left[p][idx - 1]
            if idx < len(E[p]) - 1:
                p_res *= cum_right[p][idx + 1]
            dp[p] = p_res % MOD

        if v == -1:
            return
        # monoid に対する cumulative sum を計算
        if cum_left[v] is None:
            left = [(dp[nv] + 1) % MOD for nv in E[v]]
            right = [(dp[nv] + 1) % MOD for nv in E[v]]
            k = len(E[v])
            for i in range(k - 1):
                left[i + 1] *= left[i]
                left[i + 1] %= MOD
            for i in range(k - 1, 0, -1):
                right[i - 1] *= right[i]
                right[i - 1] %= MOD
            cum_left[v] = left
            cum_right[v] = right
        dp[v] = cum_left[v][-1]

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

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

Submission status: Accepted

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

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

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

import sys
input = sys.stdin.readline

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

T = Tree(N, E)

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

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

ti = 1
ei = 0

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

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

Submission status: Accepted

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

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

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

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

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

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