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,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        ans[v] *= ans[u]+1
        ans[v] %=M
    if marker==0:
      stack.pop()
  return

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# Based on the following blog.
# https://null-mn.hatenablog.com/entry/2020/04/14/124151

from collections import defaultdict

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

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

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

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

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

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

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

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

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

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

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

    #     return self.g(r, u)

    # def __dfs2(self, u, p, a):
    #     for v in self.tree[u]:
    #         if v == p:
    #             self.dp[u][v] = a
    #             break
    #     pl = [0] * (len(self.tree[u]) + 1)
    #     pl[0] = self.ie
    #     for i, v in enumerate(self.tree[u]):
    #         pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

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

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

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

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

        return self.g(r, u)


def atcoder_dp_dp_v():
    # https://atcoder.jp/contests/dp/tasks/dp_v
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

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

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


def atcoder_abc60_f():
    # https://atcoder.jp/contests/abc160/tasks/abc160_f
    # https://atcoder.jp/contests/abc160/submissions/16667517
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]

    M = 10**9+7

    from functools import reduce

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

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

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

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

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

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


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

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

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

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

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



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

    print(*ans)


if __name__ == '__main__':
    atcoder_dp_dp_v()
    # atcoder_abc60_f()
    # codeforces_1324_f()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


from collections import defaultdict

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

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

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

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

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

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

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

            self.dp[u][p] = a

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

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

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

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

    #     return self.g(r, u)

    # def __dfs2(self, u, p, a):
    #     for v in self.tree[u]:
    #         if v == p:
    #             self.dp[u][v] = a
    #             break
    #     pl = [0] * (len(self.tree[u]) + 1)
    #     pl[0] = self.ie
    #     for i, v in enumerate(self.tree[u]):
    #         pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

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

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

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

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

        return self.g(r, u)


def atcoder_dp_dp_v():
    # https://atcoder.jp/contests/dp/tasks/dp_v
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

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

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


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

    M = 10**9+7

    from functools import reduce

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

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

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

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

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

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




if __name__ == '__main__':
    atcoder_dp_dp_v()
    # atcoder_abc60_f()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


from collections import defaultdict

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

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

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

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

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

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

            self.dp[u][p] = a

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

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

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

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

    #     return self.g(r, u)

    # def __dfs2(self, u, p, a):
    #     for v in self.tree[u]:
    #         if v == p:
    #             self.dp[u][v] = a
    #             break
    #     pl = [0] * (len(self.tree[u]) + 1)
    #     pl[0] = self.ie
    #     for i, v in enumerate(self.tree[u]):
    #         pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

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

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

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

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

        return r


def atcoder_dp_dp_v():
    # https://atcoder.jp/contests/dp/tasks/dp_v
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

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

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



if __name__ == '__main__':
    atcoder_dp_dp_v()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


from collections import defaultdict

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

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

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

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

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

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

            self.dp[u][p] = a

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

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

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


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

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

        return r


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

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

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



if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

#############
# Main Code #
#############

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

class Reroot():
    def __init__(self, graph):
        self.graph = copy.deepcopy(graph)
        ##### Settings #####
        self.unit = 1
        self.merge = lambda a, b: a * b % mod
        self.adj_bu = lambda a, i: a + 1
        self.adj_td = lambda a, i, p: a + 1
        self.adj_fin = lambda a, i: a
        ####################
        # トポソ
        P = [-1] * N # 親
        Q = deque([0])
        R = [] # 巡回した順番
        while Q:
            i = deque.popleft(Q)
            R.append(i)
            for a in self.graph[i]:
                if a != P[i]:
                    P[a] = i
                    # 親への辺を消す
                    self.graph[a].remove(i)
                    deque.append(Q, a)
        # bottom-up
        ME = [self.unit] * N # mergeを使う
        XX = [0] * N # dpする
        for i in R[1:][::-1]: # 巡回を逆順に辿る
            XX[i] = self.adj_bu(ME[i], i)
            p = P[i] # 親を取り出す
            ME[p] = self.merge(ME[p], XX[i]) # iの親要素とiの値をマージする
        XX[R[0]] = self.adj_fin(ME[R[0]], R[0])

        TD = [self.unit] * N
        for i in R: # 巡回した順番に
            ac = TD[i] # 左からDP
            for j in self.graph[i]: # 各子要素について
                TD[j] = ac
                ac = self.merge(ac, XX[j])  # マージする
            ac = self.unit
            for j in self.graph[i][::-1]:
                TD[j] = self.adj_td(self.merge(TD[j], ac), j, i)
                ac = self.merge(ac, XX[j])
                XX[j] = self.adj_fin(self.merge(ME[j], TD[j]), j)
        self.res = XX

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
def dfs(v,p):
    size[v]=len(G[v])
    dp[v]=[0]*size[v]
    res=1
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            p_i[v]=i
            continue
        R=dfs(nv,v)
        dp[v][i]=R
        res=res*(R+1)%MOD
    return res
    
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][p_i[v]]=res_p
    for i in range(size[v]):
        ans[v]=ans[v]*(dp[v][i]+1)%MOD
    dp_L=[1]*(size[v]+1)
    dp_R=[1]*(size[v]+1)
    for i in range(size[v]):
        dp_L[i+1]=dp_L[i]*(dp[v][i]+1)%MOD
    for i in reversed(range(size[v])):
        dp_R[i]=dp_R[i+1]*(dp[v][i]+1)%MOD
        
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            continue
        reroot(nv,dp_L[i]*dp_R[i+1]%MOD,v)

N,MOD=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
dp=[[] for i in range(N)]
size=[-1]*N
p_i=[-1]*N
dp_L=[[] for i in range(N)]
dp_R=[[] for i in range(N)]
ans=[1]*N

z_root=dfs(0,-1)
reroot(0,0,-1)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
def dfs(v,p):
    if res_v[v]!=-1:
        return res_v[v]
    size[v]=len(G[v])
    dp[v]=[0]*size[v]
    res=1
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            p_i[v]=i
            continue
        R=dfs(nv,v)
        dp[v][i]=R
        res=res*(R+1)%MOD
    return res
    
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][p_i[v]]=res_p
    for i in range(size[v]):
        ans[v]=ans[v]*(dp[v][i]+1)%MOD
    dp_L=[1]*(size[v]+1)
    dp_R=[1]*(size[v]+1)
    for i in range(size[v]):
        dp_L[i+1]=dp_L[i]*(dp[v][i]+1)%MOD
    for i in reversed(range(size[v])):
        dp_R[i]=dp_R[i+1]*(dp[v][i]+1)%MOD
        
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            continue
        reroot(nv,dp_L[i]*dp_R[i+1]%MOD,v)

N,MOD=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
res_v=[-1]*N
dp=[[] for i in range(N)]
size=[-1]*N
p_i=[-1]*N
dp_L=[[] for i in range(N)]
dp_R=[[] for i in range(N)]
ans=[1]*N

z_root=dfs(0,-1)
res_v[0]=z_root
reroot(0,0,-1)
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############


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

#############
# Functions #
#############

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

#####Shorten#####
def DD(arg): return defaultdict(arg)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

#############
# Main Code #
#############


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


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

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

bfs(graph, 0)

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

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

Submission status: Accepted

Solution code:
import sys
from collections import deque
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


def make_tree_0index(N):
    edge_dic = {}
    for _ in range(N-1):
        x, y = na()
        x -= 1
        y -= 1
        if x in edge_dic:
            edge_dic[x].append(y)
        else:
            edge_dic[x] = [y]
        if y in edge_dic:
            edge_dic[y].append(x)
        else:
            edge_dic[y] = [x]
    return edge_dic


N, M = na()
if N == 1:
    print(1)
    exit()
edge_dic = make_tree_0index(N)


parent_array = [-2] * N
parent_array[0] = -1
node1 = deque([0])
node2 = deque([0])
node3 = deque([0])

while(len(node1)):
    n = node1.popleft()
    for v in edge_dic[n]:
        if parent_array[v] == -2:
            parent_array[v] = n
            node1.append(v)
            node2.append(v)
            node3.append(v)

ans1 = [0] * N

while(len(node2)):
    n = node2.pop()
    ans1[n] = 1
    for v in edge_dic[n]:
        if parent_array[n] == v:
            continue
        ans1[n] = (ans1[n] * (ans1[v]+1)) % M

ans2 = [0] * N

subans2 = [0] * N

while(len(node3)):
    n = node3.popleft()
    ans2[n] = 1
    if n != 0:
        ans2[n] = (ans2[n] * ans2[parent_array[n]] * subans2[n] + 1) % M

    reverse = [1]
    right = 1
    for v in edge_dic[n][::-1]:
        if parent_array[n] == v:
            continue
        right = (right * (ans1[v] + 1)) % M
        reverse.append(right)
    reverse.pop()

    left = 1
    for v in edge_dic[n]:
        if parent_array[n] == v:
            continue
        right = reverse.pop()
        subans2[v] = (left * right) % M
        left = (left * (ans1[v]+1)) % M


ans = [a*b % M for a, b in zip(ans1, ans2)]
print("\n".join(map(str, ans)))