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 .

Solution (Python):


from collections import defaultdict


import sys
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  

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):
    
    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)  
            to_visit.append(child)

    
    
    
    upedge = [0] * (N + 1)
    
    multiply_of_upedge = [1] * (N + 1)
    for cur in reversed(bfs_visited_order[1:]):
        
        upedge[cur] = multiply_of_upedge[cur] + 1
        p = parent[cur]
        multiply_of_upedge[p] *= upedge[cur]
        multiply_of_upedge[p] %= M
    
    
    upedge[root] = multiply_of_upedge[root]
    final_result = upedge[:]

    
    downedge = [1] * (N + 1)
    for cur in bfs_visited_order:
        prod = 1
        
        for child in edges[cur]:
            downedge[child] = prod
            prod *= upedge[child]
            prod %= M
        
        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]:
            
            final_result[child] = (
                multiply_of_upedge[child]
                * downedge[child]) % M

    return final_result[1:]


def main():
    
    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)

    
    for x in solve(N, M, edges):
        print(x)



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():
    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":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):


from collections import defaultdict


import sys
from collections import deque

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  

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):
    
    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)  
            to_visit.append(child)

    
    
    
    upedge = [0] * (N + 1)
    
    multiply_of_upedge = [1] * (N + 1)
    for cur in reversed(bfs_visited_order[1:]):
        
        upedge[cur] = multiply_of_upedge[cur] + 1
        p = parent[cur]
        multiply_of_upedge[p] *= upedge[cur]
        multiply_of_upedge[p] %= M
    
    
    upedge[root] = multiply_of_upedge[root]
    final_result = upedge[:]

    
    downedge = [1] * (N + 1)
    for cur in bfs_visited_order:
        prod = downedge[cur]
        
        for child in edges[cur]:
            downedge[child] = prod
            prod *= upedge[child]
            prod %= M
        
        prod = 1
        for child in reversed(edges[cur]):
            downedge[child] = (downedge[child] * prod) % M + 1
            prod *= upedge[child]
            prod %= M
            
            final_result[child] = (
                multiply_of_upedge[child]
                * downedge[child]) % M

    return final_result[1:]


def main():
    
    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)

    
    for x in solve(N, M, edges):
        print(x)



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():
    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":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

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


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

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

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n, M = map(int, input().split())
ns = defaultdict(list)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].append(v-1)
    ns[v-1].append(u-1)

bs = {}
cump0 = defaultdict(list)
cump1 = defaultdict(list)
def sub(u, p):
    if (p,u) in bs:
        return bs[p,u]
    b = 1
    ps = []
    for v in ns[u]:
        if v==p:
            continue
        bb = sub(v, u)
        b *= (1+bb)
        b %= M
        ps.append(bb)
    v0 = 1
    v1 = 1
    l = len(ps)
    for i in range(l):
        cump0[u].append(v0)
        cump1[u].append(v1)
        v0 *= ps[i]+1
        v1 *= ps[l-1-i]+1
        v0%=M;v1%=M
    cump0[u].append(v0)
    cump1[u].append(v1)
        
    bs[p,u] = b % M
    return b

ans = [None]*n
def sub2(u, p):
    i = 0
    for v in ns[u]:
        if v==p:
            continue
        b1 = bs[p,u]
        b2 = bs[u,v]
        b3 = bs[u,p]
        if p>=0:
            bb = (cump0[u][i] * cump1[u][-(i+2)] * (1+b3)) % M
        else:
            bb = (cump0[u][i] * cump1[u][-(i+2)]) % M
        bs[v,u] = bb
        ans[v] = bs[u,v] * (1+bb) % M
        sub2(v,u)
        i += 1
        
sub(0, -1)
bs[0,-1] = 1
ans[0] = bs[-1,0]
sub2(0,-1)



write("\n".join(map(str, ans)))

Solution (Python):

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 

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

    
    TD = [unit] * N
    for i in R:
        
        ac = TD[i]
        for j in G[i]:
            TD[j] = ac
            ac = merge(ac, dp1[j])
        
        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()

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

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

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

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

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

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

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    
    
    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()
    R=[]
    
    Q.put(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)
                
    
    
    
    unit=1
    
    merge=lambda a,b: (a*b)%M
    
    
    
    adj_bu=lambda a,v:a+1
    
    adj_td=lambda a,v,p:a+1
    
    adj_fin=lambda a,i:a
    
    
    
    
    
    
    
    ME=[unit]*N
    dp=[0]*N
    
    
    for v in R[1:][::-1]:
        dp[v]=adj_bu(ME[v],v)
        p=P[v]
        ME[p]=merge(ME[p],dp[v])
        
        
    
    dp[R[0]]=adj_fin(ME[R[0]],R[0])
    
    
    
    
    
    
    
    
    TD=[unit]*N
    
    for v in R:
        
        ac=TD[v]
        for nv in adj[v]:
            TD[nv]=ac
            ac=merge(ac,dp[nv])
            
        
        ac=unit
        for nv in adj[v][::-1]:
            TD[nv]=adj_td(merge(TD[nv],ac),nv,v)
            ac=merge(ac,dp[nv])
            dp[nv]=adj_fin(merge(ME[nv],TD[nv]),nv)
        
        
    for i in range(N):
        print(dp[i])
        
    
    
        

main()

Solution (Python):
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 = [[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)

dfs2(0, -1, ele_id)
for ans_i in ans:
    print(ans_i - 1)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n, m = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)
dp1 = [0] * n


def dfs1(i=0, r=-1):
    s = 1
    for j in e[i]:
        if j != r:
            s *= dfs1(j, i)
            s %= m
    dp1[i] = s
    return s + 1


dfs1()
dp2 = [0] * n
dp2[0] = dp1[0]


def dfs2(i=0, r=-1, s=1):
    a = [1]
    for j in e[i]:
        if j != r:
            a.append(a[-1] * (dp1[j]+1) % m)
    b = [1]
    for j in reversed(e[i]):
        if j != r:
            b.append(b[-1] * (dp1[j]+1) % m)
    b.reverse()

    k = 0
    for j in e[i]:
        if j != r:
            l = (a[k] * b[k + 1] * s + 1)%m
            dp2[j] = l * dp1[j] % m
            dfs2(j, i, l)
            k += 1


dfs2()
print("\n".join(map(str,dp2)))

Solution (Python):



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 = [0] * (n + 1)



dp2 = [0] * (n + 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)


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  
        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 = [0] * (n + 1)

for v in topo:
    
    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  
        dp2[v] %= m
    
    dp[v] = dp1[v] * (dp2[v] + 1)
    dp[v] %= m
print(*dp[1:], sep="\n")