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:
#!/usr/bin/env python3

from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N, M, edges):
    # convert bidirectional graph to tree
    root = 1
    parent = [-1] * (N + 1)
    to_visit = deque([root])
    bfs_visited_order = []
    while to_visit:
        cur = to_visit.popleft()
        bfs_visited_order.append(cur)
        for child in edges[cur]:
            if child == parent[cur]:
                continue
            parent[child] = cur
            edges[child].remove(cur)  # remove back-link
            to_visit.append(child)

    # up-edge: v -> parent[v]
    # default: if no child, one black, one white (1 + 1)
    # f(x) = prod(f(c) for c in children) + 1
    upedge = [0] * (N + 1)
    # stores multiply result (1 is unity)
    multiply_of_upedge = [1] * (N + 1)
    for cur in reversed(bfs_visited_order[1:]):
        # visit vertexes except root, in reversed order
        upedge[cur] = multiply_of_upedge[cur] + 1
        p = parent[cur]
        multiply_of_upedge[p] *= upedge[cur]
        multiply_of_upedge[p] %= M
    # root: multiply children and don't add one
    # the one is "all-white" pattern
    upedge[root] = multiply_of_upedge[root]
    final_result = upedge[:]

    # down-edge: parent[v] -> v
    downedge = [1] * (N + 1)
    for cur in bfs_visited_order:
        prod = 1
        # left-to-right accumlated products (* downedge[cur])
        for child in edges[cur]:
            downedge[child] = prod
            prod *= upedge[child]
            prod %= M
        # multiply right-to-left accumlated products
        prod = 1
        for child in reversed(edges[cur]):
            downedge[child] = (downedge[cur] * downedge[child] * prod) % M + 1
            prod *= upedge[child]
            prod %= M

        for child in edges[cur]:
            # update final result
            final_result[child] = (
                multiply_of_upedge[child]
                * downedge[child]) % M

    return final_result[1:]


def main():
    # parse input
    N, M = map(int, input().split())
    edges = defaultdict(list)
    for i in range(N - 1):
        x, y = map(int, input().split())
        edges[x].append(y)
        edges[y].append(x)

    #print(*solve(N, M, edges), sep="\n")
    for x in solve(N, M, edges):
        print(x)


# tests
T1 = """
3 100
1 2
2 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    3
    4
    3
    """


T2 = """
4 100
1 2
1 3
1 4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    8
    5
    5
    5
    """


T3 = """
1 100
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1
    """


T4 = """
10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    0
    0
    1
    1
    1
    0
    1
    0
    1
    1
    """


# def test_T5():
#     """
#     >>> edges = defaultdict(list)
#     >>> for i in range(100000 - 1):
#     ...     edges[i + 1].append(i + 2)
#     ...     edges[i + 2].append(i + 1)
#     >>> solve(100000, 5, edges)
#     """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N, M, edges):
    # convert bidirectional graph to tree
    root = 1
    parent = [-1] * (N + 1)
    to_visit = deque([root])
    bfs_visited_order = []
    while to_visit:
        cur = to_visit.popleft()
        bfs_visited_order.append(cur)
        for child in edges[cur]:
            if child == parent[cur]:
                continue
            parent[child] = cur
            edges[child].remove(cur)  # remove back-link
            to_visit.append(child)

    # up-edge: v -> parent[v]
    # default: if no child, one black, one white (1 + 1)
    # f(x) = prod(f(c) for c in children) + 1
    upedge = [0] * (N + 1)
    # stores multiply result (1 is unity)
    multiply_of_upedge = [1] * (N + 1)
    for cur in reversed(bfs_visited_order[1:]):
        # visit vertexes except root, in reversed order
        upedge[cur] = multiply_of_upedge[cur] + 1
        p = parent[cur]
        multiply_of_upedge[p] *= upedge[cur]
        multiply_of_upedge[p] %= M
    # root: multiply children and don't add one
    # the one is "all-white" pattern
    upedge[root] = multiply_of_upedge[root]
    final_result = upedge[:]

    # down-edge: parent[v] -> v
    downedge = [1] * (N + 1)
    for cur in bfs_visited_order:
        prod = downedge[cur]
        # left-to-right accumlated products (* downedge[cur])
        for child in edges[cur]:
            downedge[child] = prod
            prod *= upedge[child]
            prod %= M
        # multiply right-to-left accumlated products
        prod = 1
        for child in reversed(edges[cur]):
            downedge[child] = (downedge[child] * prod) % M + 1
            prod *= upedge[child]
            prod %= M
            # update final result
            final_result[child] = (
                multiply_of_upedge[child]
                * downedge[child]) % M

    return final_result[1:]


def main():
    # parse input
    N, M = map(int, input().split())
    edges = defaultdict(list)
    for i in range(N - 1):
        x, y = map(int, input().split())
        edges[x].append(y)
        edges[y].append(x)

    #print(*solve(N, M, edges), sep="\n")
    for x in solve(N, M, edges):
        print(x)


# tests
T1 = """
3 100
1 2
2 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    3
    4
    3
    """


T2 = """
4 100
1 2
1 3
1 4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    8
    5
    5
    5
    """


T3 = """
1 100
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1
    """


T4 = """
10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    0
    0
    1
    1
    1
    0
    1
    0
    1
    1
    """


# def test_T5():
#     """
#     >>> edges = defaultdict(list)
#     >>> for i in range(100000 - 1):
#     ...     edges[i + 1].append(i + 2)
#     ...     edges[i + 2].append(i + 1)
#     >>> solve(100000, 5, edges)
#     """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    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: a * b % m
adj_bu = lambda a, i: a + 1
adj_td = lambda a, i, p: a + 1
adj_fin = lambda a, i: a
#####

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

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])

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

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

Submission status: Accepted

Solution code:
import sys 
sys.setrecursionlimit(100000) 

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)

dp = [0]*N
fm_bm = [[] for _ in range(N)]

def tdc(p, v):
    if G[v] == [p]:
        dp[v] = 1
        return 1
    res = 1
    fm = [1]
    bm = []
    C = list(set(G[v]) - set([p]))
    for u in C:
        val = 1+tdc(v, u)
        val %= M
        res *= val
        res %= M
        fm.append(res)
        bm.append(val)
    dp[v] = res
    bm.append(1)
    for i in range(len(bm)-1, 0, -1):
        bm[i-1] *= bm[i]
        bm[i-1] %= M
    fm_bm[v] = [fm, bm]
    return dp[v]

r = 0       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[r]

def buc(p, v, a):
    if G[v] == [p]: return 0
    C = list(set(G[v]) - set([p]))
    fm, bm = fm_bm[v]
    for i, u in enumerate(C):
        rev_dp = fm[i]*bm[i+1]%M
        rev_dp = rev_dp*a%M+1 
        ans[u] = dp[u]*rev_dp%M
        buc(v, u, rev_dp)

buc(-1, r, 1)
print('\n'.join(map(str, ans)))

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:

from collections import deque
def resolve():
    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)

    P = [-1]*N
    q = deque([0])
    R = []
    while q:
        i = q.popleft()
        R.append(i)
        for to in G[i]:
            if to != P[i]:
                P[to] = i
                G[to].remove(i)
                q.append(to)

    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 # 最終結果。本問では、全部白みたいなのが認められないので、最終結果では1を足さないようにしています。

    # Bottom-Up 部分
    ME = [unit] * N
    dp1 = [0] * N
    for i in R[1:][::-1]:
        dp1[i] = adj_bu(ME[i], i)
        p = P[i]
        ME[p] = merge(ME[p], dp1[i])
    dp1[R[0]] = adj_fin(ME[R[0]], R[0])

    # Top-Down 部分
    TD = [unit] * N
    for i in R:
        # 左からDP（結果はTDに入れている）
        ac = TD[i]
        for j in G[i]:
            TD[j] = ac
            ac = merge(ac, dp1[j])
        # 右からDP（結果はacに入れている）
        ac = unit
        for j in G[i][::-1]:
            TD[j] = adj_td(merge(TD[j], ac), j, i)
            ac = merge(ac, dp1[j])
            dp1[j] = adj_fin(merge(ME[j], TD[j]), j)

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

topo = []
parent = [-1] * N
node = [0]
while node:
    s = node.pop()
    topo.append(s)
    for t in edge[s]:
        if t == parent[s]:
            continue
        parent[t] = s
        node.append(t)

memo = [1] * N
res = [1] * N
for s in reversed(topo):
    for t in edge[s]:
        if t == parent[s]:
            continue
        res[s] = res[s] * memo[t] % mod
    memo[s] = res[s] + 1


TD = [1] * N
for s in topo:
    acc = TD[s]
    for t in edge[s]:
        if t == parent[s]:
            continue
        TD[t] = acc
        acc = acc * memo[t] % mod
    acc = 1
    for t in reversed(edge[s]):
        if t == parent[s]:
            continue
        TD[t] = (TD[t] * acc + 1) % mod
        acc = acc * memo[t] % mod
        res[t] = res[t] * TD[t] % mod

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

Submission status: Accepted

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

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

def ReRooting(adjL):
    def merge(val1, val2):
        return val1 * val2 % MOD
    def calcValue(val1):
        return (val1 + 1) % MOD

    numV = len(adjL)
    vRoot = 0
    useds = [False] * numV
    useds[vRoot] = True
    vs = [vRoot]
    pars = [-1] * numV
    stack = [vRoot]
    while stack:
        v = stack.pop()
        for v2 in adjL[v]:
            if not useds[v2]:
                useds[v2] = True
                vs.append(v2)
                pars[v2] = v
                stack.append(v2)

    anss = [0] * numV
    dpUpFrom, dpDownTo, accLs, accRs = [1]*numV, [1]*numV, [1]*numV, [1]*numV
    for v in reversed(vs):
        vPar = pars[v]
        tmp = 1
        for v2 in adjL[v]:
            if v2 == vPar: continue
            accLs[v2] = tmp
            tmp = merge(tmp, dpUpFrom[v2])
        tmp = 1
        for v2 in reversed(adjL[v]):
            if v2 == vPar: continue
            accRs[v2] = tmp
            tmp = merge(tmp, dpUpFrom[v2])
        anss[v] = tmp
        dpUpFrom[v] = calcValue(tmp)

    for v in vs:
        vPar = pars[v]
        dpDownToV = dpDownTo[v]
        anss[v] = merge(anss[v], dpDownToV)
        for v2 in adjL[v]:
            if v2 == vPar: continue
            tmp = merge(accLs[v2], accRs[v2])
            tmp = merge(tmp, dpDownToV)
            dpDownTo[v2] = calcValue(tmp)
    return anss

anss = ReRooting(adjL)
print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,mod = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
root = 0
stack = []
dp = [[] for i in range(n+1)]
dpacc1 = [[] for i in range(n+1)]
dpacc2 = [[] for i in range(n+1)]
order = [[] for i in range(n+1)]
num = [0 for i in range(n+1)]
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
    num[i] = 1
  elif not root:
    root = i
    deg[i] += 1
while stack:
  x = stack.pop()
  if dp[x]:
    num[x] = 1
    for z in dp[x]:
      num[x] *= z
      num[x] %= mod
  for y in graph[x]:
    if deg[y] > 1:
      deg[y] -= 1
      dp[y].append(num[x]+1)
      order[y].append(x)
      if deg[y] == 1:
        stack.append(y)
stack = [root]
deg[root] -= 1
while stack:
  x = stack.pop()
  l = len(order[x])
  if dp[x]:
    for v in dp[x]:
      if not dpacc1[x]:
        dpacc1[x].append(v)
      else:
        dpacc1[x].append(dpacc1[x][-1]*v%mod)
    for v in dp[x][::-1]:
      if not dpacc2[x]:
        dpacc2[x].append(v)
      else:
        dpacc2[x].append(dpacc2[x][-1]*v%mod)
  for i,y in enumerate(order[x]):
    if deg[y] == 1:
      deg[y] -= 1
      if i == 0:
        val = dpacc2[x][l-2]
      elif i == l-1:
        val = dpacc1[x][l-2]
      else:
        val = dpacc1[x][i-1]*dpacc2[x][l-i-2]%mod
      dp[y].append(val+1)
      order[y].append(x)
      stack.append(y)
for i in range(1,n+1):
  ans = 1
  for x in dp[i]:
    ans *= x
    ans %= mod
  print(ans)

Submission status: Accepted

Solution code:
def ReRooting(n, e, identify):
  edges = [[] for _ in range(n)]
  indexedges = [[] for _ in range(n)]
  for u, v in e:
    indexedges[v].append(len(edges[u]))
    indexedges[u].append(len(edges[v]))
    edges[u].append(v)
    edges[v].append(u)
  dp = [identify]*n
  subdp = [len(edges[i])*[identify] for i in range(n)]
  parents = [-1]*n
  order = [0]
  for node in order:
    for mode in edges[node]:
      if mode == parents[node]:
        continue
      order.append(mode)
      parents[mode] = node
  def merge1(a, b):
    return a*b%mod
  def addnode1(a, id):
    return a+1
  for node in order[1::][::-1]:
    parent = parents[node]
    ans = identify
    indexparent = -1
    for j in range(len(edges[node])):
      mode = edges[node][j]
      if parent == mode:
        indexparent = j
        continue
      ans = merge1(ans, subdp[node][j])
    subdp[parent][indexedges[node][indexparent]] = addnode1(ans, node)
  def merge2(a,b):
    return a*b%mod
  def addnode2(a, id):
    return a+1
  for node in order:
    b = [identify]*len(edges[node])
    for i in range(len(edges[node])-1,0,-1):
      b[i-1] = merge2(b[i], subdp[node][i])
    bb = identify
    for i in range(len(edges[node])):
      ans = merge2(bb, b[i])
      subdp[edges[node][i]][indexedges[node][i]] = addnode2(ans, node)
      bb = merge2(bb, subdp[node][i])
    dp[node] = addnode2(bb, node)
  return dp
n,mod=map(int,input().split())
edges=[]*n
for _ in range(n-1):
  a,b=map(int,input().split())
  a-=1
  b-=1
  edges.append([a,b])
for i in ReRooting(n,edges,1):print(i-1)

Submission status: Accepted

Solution code:
def ReRooting(nodeCount, edges, identity, merge, addNode):
  adjacents = [[] for _ in range(nodeCount)]
  indexForAdjacents = [[] for _ in range(nodeCount)]
  for u,v in edges:
    indexForAdjacents[v].append(len(adjacents[u]))
    indexForAdjacents[u].append(len(adjacents[v]))
    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 = [0]
  for node in stack:
    order[index] = node
    index += 1
    for adjacent in adjacents[node]:
      if adjacent == parents[node]:
        continue
      stack.append(adjacent)
      parents[adjacent] = node
  for node in order[::-1]:
    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(accumsFromTail)-1, 0, -1):
      accumsFromTail[j-1] = merge(childSubtreeRes[node][j], accumsFromTail[j])
    accum = identity
    for j in range(len(accumsFromTail)):
      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

n, mod = map(int, input().split())
for i in ReRooting(n, [list(map(lambda x:int(x)-1,input().split()))for _ in range(n-1)], 1, lambda a,b:a*b%mod, lambda a,id:a+1):
  print(i-1)

Submission status: Accepted

Solution code:
def ReRooting(nodeCount, edges, identity, merge, addNode):
  adjacents = [[] for _ in range(nodeCount)]
  indexForAdjacents = [[] for _ in range(nodeCount)]
  for u,v in edges:
    indexForAdjacents[v].append(len(adjacents[u]))
    indexForAdjacents[u].append(len(adjacents[v]))
    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 = [0]
  for node in stack:
    order[index] = node
    index += 1
    for adjacent in adjacents[node]:
      if adjacent == parents[node]:
        continue
      stack.append(adjacent)
      parents[adjacent] = node
  for node in order[::-1]:
    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(accumsFromTail)-1, 0, -1):
      accumsFromTail[j-1] = merge(childSubtreeRes[node][j], accumsFromTail[j])
    accum = identity
    for j in range(len(accumsFromTail)):
      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

n, mod = map(int, input().split())
edge = []
for _ in range(n-1):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  edge.append((x, y))
def merge(a, b):
  return a*b % mod
def addNode(a, id):
  return a+1
for i in ReRooting(n, edge, 1, merge, addNode):
  print(i-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    #参考：https://qiita.com/Kiri8128/items/a011c90d25911bdb3ed3
    #というかマルパクリ...
    
    N,M=MI()
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        x,y=MI()
        x-=1
        y-=1
        adj[x].append(y)
        adj[y].append(x)
        
    import queue
    
    P=[-1]*N#親リスト
    Q=queue.Queue()#BFSに使う
    R=[]#BFSでトポソしたものを入れる
    
    Q.put(0)#0を根とする
    
    #トポソ########################
    while not Q.empty():
        v=Q.get()
        R.append(v)
        for nv in adj[v]:
            if nv!=P[v]:
                P[nv]=v
                adj[nv].remove(v)#親につながるを消しておく
                Q.put(nv)
                
    #setting#############
    
    #merge関数の単位元
    unit=1
    #子頂点を根とした木の結果をマージのための関数
    merge=lambda a,b: (a*b)%M
    
    
    #マージ後の調整用(bottom-up時)，今回，木の中の要素が全部白というパターンがあるので+1
    adj_bu=lambda a,v:a+1
    #マージ後の調整用(top-down時)
    adj_td=lambda a,v,p:a+1
    #マージ後の調整用(最終結果を求める時)，今回，全部白はダメなので，aをそのまま返す
    adj_fin=lambda a,i:a
    
    #今回の問題では，調整においてvやpは不要だが，必要な時もあるため，残している．
    
    #Bottom-up#############
    #merge関数を使ってMEを更新し，adjで調整してdpを埋める
    #MEは親ノード以外の値を集約したようなもの
    
    ME=[unit]*N
    dp=[0]*N
    
    
    for v in R[1:][::-1]:#根以外を後ろから
        dp[v]=adj_bu(ME[v],v)#BU時の調整
        p=P[v]
        ME[p]=merge(ME[p],dp[v])#親に，子の情報を伝えている．ME[p]の初期値はunit
        #print(v,p,dp[v],ME[p])
        
    #最後だけ個別に考える
    dp[R[0]]=adj_fin(ME[R[0]],R[0])
    
    #print(ME)
    #print(dp)
    
    #Top-down##########
    #TDは最終的に，Top-down時のdpを入れるが，途中においては左右累積和の左から累積させたものを入れておく
    #メモリの省略のため
    
    TD=[unit]*N
    
    for v in R:
        #左からDP（結果をTDに入れておく）
        ac=TD[v]
        for nv in adj[v]:
            TD[nv]=ac
            ac=merge(ac,dp[nv])
            
        #右からDP(結果をacに入れて行きながら進めていく)
        ac=unit
        for nv in adj[v][::-1]:
            TD[nv]=adj_td(merge(TD[nv],ac),nv,v)##TDときの調整
            ac=merge(ac,dp[nv])
            dp[nv]=adj_fin(merge(ME[nv],TD[nv]),nv)#最終調整
        
        
    for i in range(N):
        print(dp[i])
        
    
    
        

main()

Submission status: Accepted

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

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

ele_id = 1
# dp[v][i] = (頂点vから出るi番目の有向辺に関する部分木のDPの値)
# dp[v][i] = (c, m)
# c = 頂点vから出るi番目の有向辺に関する部分木の塗り方の数
# m = 頂点vから出るi番目の有向辺に関する部分木の頂点数
dp = [[ele_id] * len(graph[i]) for i in range(n)]
ans = [ele_id] * n

add_func = lambda x: x + 1
merge_func = lambda a, b: a * b % mod


def dfs1(v, v_p):
    dp_cum = ele_id
    for i, v_next in enumerate(graph[v]):
        if v_next == v_p:
            continue
        dp[v][i] = dfs1(v_next, v)
        dp_cum = merge_func(dp_cum, dp[v][i])
    return add_func(dp_cum)


def dfs2(v, v_p, dp_vp):
    for i, v_next in enumerate(graph[v]):
        if v_next == v_p:
            dp[v][i] = dp_vp

    dp_l = [ele_id] * (len(graph[v]) + 1)
    dp_r = [ele_id] * (len(graph[v]) + 1)
    for i in range(len(graph[v])):
        dp_l[i + 1] = merge_func(dp_l[i], dp[v][i])
    for i in reversed(range(len(graph[v]))):
        dp_r[i] = merge_func(dp_r[i + 1], dp[v][i])

    ans[v] = add_func(dp_l[-1])

    for i, v_next in enumerate(graph[v]):
        if v_next == v_p:
            continue
        dfs2(v_next, v, add_func(merge_func(dp_l[i], dp_r[i + 1])))


dfs1(0, -1)
# print(*dp, sep='\n')
dfs2(0, -1, ele_id)
for ans_i in ans:
    print(ans_i - 1)

Submission status: Accepted

Solution code:
# これは逆元を用いてやる？
# この問題の場合、逆元をうまく設定するのが難しいので
# 左右からのmergeになりそう
from collections import deque
import sys

input = sys.stdin.buffer.readline


n, m = map(int, input().split())
# 各々の頂点の次数
deg = [0] * (n + 1)
# 隣接リストにグラフをまとめる
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    deg[x] += 1
    deg[y] += 1

# dp1は葉向きに見たときの塗り方
# 自身が黒い時、下の候補はどうなるか？
dp1 = [0] * (n + 1)

# dp2は根向きに見たときの塗り方
# 自身が黒い時、親側の候補はどうなるか？
dp2 = [0] * (n + 1)

# 1回目
start = 1
par = [-1] * (n + 1)
que = deque([start])
topo = []
while que:
    v = que.popleft()
    topo.append(v)
    for i in range(deg[v]):
        u = graph[v][i]
        if par[v] == u:
            continue
        par[u] = v
        que.append(u)

# dpするついでにi=0からの積とi=deg[v]-1からの積を取っておくか。
dpl = [[] for _ in range(n + 1)]
dpr = [[] for _ in range(n + 1)]

# 頂点番号から何番目かがわかるようにしたいから辞書で持っておく？
edge_num = [{} for _ in range(n + 1)]

for v in topo[::-1]:
    temp = 1
    for i in range(deg[v]):
        u = graph[v][i]
        edge_num[v][u] = i  # edge_num[v]で頂点vに関する辞書。頂点uからidxが欲しいので記録
        if u == par[v]:
            dpl[v].append(temp)
            continue
        temp *= dp1[u] + 1
        temp %= m
        dpl[v].append(temp)
    dp1[v] = temp
    temp = 1
    for i in range(deg[v] - 1, -1, -1):
        u = graph[v][i]
        if u == par[v]:
            dpr[v].append(temp)
            continue
        temp *= dp1[u] + 1
        temp %= m
        dpr[v].append(temp)
# これで普通の木DPに加えて
# 左右からの累積積
# 頂点番号からidxへの辞書
# を獲得したはず

# dpは欲しい答えとしておく
# dp1とdp2から求める
dp = [0] * (n + 1)

for v in topo:
    # dp2の計算
    p = par[v]
    if p == -1:  # 例外、親がいない
        dp[v] = dp1[v]
        dp[v] %= m
        continue
    # 根側の処理
    # 自分以外の積を作りたい
    idx = edge_num[p][v]
    num = deg[p]
    dp2[v] = 1
    if idx - 1 >= 0:
        dp2[v] *= dpl[p][idx - 1]
        dp2[v] %= m
    if num - 2 - idx >= 0:
        dp2[v] *= dpr[p][num - 2 - idx]
        dp2[v] %= m
    # 根側の根側の処理
    pp = par[p]  # 親の親
    if pp != -1:  # 親の親がいるならば
        dp2[v] *= dp2[p] + 1  # 白=1か黒=dp2[pp]か
        dp2[v] %= m
    # dpの計算
    dp[v] = dp1[v] * (dp2[v] + 1)
    dp[v] %= m
print(*dp[1:], sep="\n")