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: Wrong Answer

Solution code:
'''
N頂点の木があり、i番目の辺は頂点x_iとy_iを結んでいる。
各頂点を白または黒で塗り、どの黒い頂点からどの黒い頂点へも黒い頂点のみをたどって到達できる時、
頂点vが黒であるような頂点の色の組み合わせは何通りか？Mで割ったあまりを求めよ。
graph_i
input:
3 100
1 2
2 3
output:
    3
    4
    3

'''
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


# endregion

# setting
unit = 1  # 単位元


def merge(a, b):
    # モノイド演算
    return a * b % M


def adj_bu(a, i):
    # bottom up DP
    return a + 1


def adj_td(a, i, p):
    # top down DP
    return a + 1


def adj_fin(a, i):
    # 最終結果
    return a
#####


n, M = inpl()
graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = inpl()
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
parent = [-1] * n
root = 0  # 0を根とする
queue = collections.deque([root])
sorted_graph = []  # トポロジカルソート

# トポロジカルソート
while queue:
    i = queue.popleft()
    sorted_graph.append(i)
    for a in graph[i]:
        if a != parent[i]:
            parent[a] = i
            graph[a].remove(i)  # graph：隣接リストから子リストにする
            queue.append(a)

# Bottom up DP

BU = [unit] * n  # acc[i]と対応
res = [0] * n
for i in sorted_graph[1:][::-1]:
    res[i] = adj_bu(BU[i], i)
    p = parent[i]
    BU[p] = merge(BU[p], res[i])
res[sorted_graph[0]] = adj_fin(BU[sorted_graph[0]], sorted_graph[0])  # 根だけ別で


# Top down DP

TD = [unit] * n
for i in sorted_graph:
    # 左からDP
    tmp = TD[i]
    for j in graph[i]:
        TD[j] = tmp
        tmp = merge(tmp, res[j])
    # 右からDP
    tmp = unit
    for j in graph[i][::-1]:
        TD[j] = adj_td(merge(TD[j], tmp), j, i)
        tmp = merge(tmp, res[j])
        res[j] = adj_fin(merge(BU[j], TD[j]), j)
print(TD)
# print(*res, sep="\n")
'''
各頂点に対して結果を出力するので全方位木を考える。
全方位木では子→親の木DPと親→子の木DPを使う。
acc[i][p]:ノードiにおける親pを除いた全方向からの累積
res[i][p]:acc[i][p]に調整を加えたもの
acc[i]:ノードiにおけるすべての方向からの集約
'''

Submission status: Wrong Answer

Solution code:
'''
N頂点の木があり、i番目の辺は頂点x_iとy_iを結んでいる。
各頂点を白または黒で塗り、どの黒い頂点からどの黒い頂点へも黒い頂点のみをたどって到達できる時、
頂点vが黒であるような頂点の色の組み合わせは何通りか？Mで割ったあまりを求めよ。
graph_i
input:
3 100
1 2
2 3
output:
    3
    4
    3

'''
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


# endregion

# setting
unit = 1  # 単位元


def merge(a, b):
    # モノイド演算
    return a * b % M


def adj_bu(a, i):
    # bottom up DP
    return a + 1


def adj_td(a, i, p):
    # top down DP
    return a + 1


def adj_fin(a, i):
    # 最終結果
    return a
#####


n, M = inpl()
graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = inpl()
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
parent = [-1] * n
root = 0  # 0を根とする
queue = collections.deque([root])
sorted_graph = []  # トポロジカルソート

# トポロジカルソート
while queue:
    i = queue.popleft()
    sorted_graph.append(i)
    for a in graph[i]:
        if a == parent[i]:
            continue
        parent[a] = i
        graph[a].remove(i)  # graph：隣接リストから子リストにする
        queue.append(a)

# Bottom up DP

BU = [unit] * n  # acc[i]と対応
res = [0] * n
for i in sorted_graph[1:][::-1]:
    res[i] = adj_bu(BU[i], i)
    p = parent[i]
    BU[p] = merge(BU[p], res[i])
res[sorted_graph[0]] = adj_fin(BU[sorted_graph[0]], sorted_graph[0])  # 根だけ別で


# Top down DP

TD = [unit] * n
for i in sorted_graph:
    # 左からDP
    tmp = TD[i]
    for j in graph[i]:
        TD[j] = tmp
        tmp = merge(tmp, res[i])
    # 右からDP
    tmp = unit
    for j in graph[i][::-1]:
        TD[j] = adj_td(merge(TD[j], tmp), j, i)
        tmp = merge(tmp, res[j])
        res[j] = adj_fin(merge(BU[j], TD[j]), j)

print(*res, sep="\n")
'''
各頂点に対して結果を出力するので全方位木を考える。
全方位木では子→親の木DPと親→子の木DPを使う。
acc[i][p]:ノードiにおける親pを除いた全方向からの累積
res[i][p]:acc[i][p]に調整を加えたもの
acc[i]:ノードiにおけるすべての方向からの集約
'''

Submission status: Wrong Answer

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

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = i+1,i+2
  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
    if marker==0:
      stack.pop()
  return ans

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack.pop()
    for u in edge[v]:
      if u==parent[v]:
        continue
      parent[u]=v
      ans[u] *= (ans[v] // (ans[u]+1))+1
      stack.append(u)
    ans[v] %= M
  return ans

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

Submission status: Wrong Answer

Solution code:

def resolve():
    def dfs1(topo, par):
        for idx in reversed(topo):
            for to in G[idx]:
                if to == par[idx]:
                    continue
                dist[idx] *= dist[to] + 1
                dist[idx] %= MOD

    def dfs2(idx, par):
        stack = [(idx, par)]

        while stack:
            idx, par = stack.pop()
            for to in G[idx]:
                ans[idx] *= dist[to] + 1
                ans[idx] %= MOD
            n = len(G[idx])
            lft = [0] * n
            rht = [0] * n
            for i in range(n):
                lft[i] = rht[i] = dist[G[idx][i]] + 1
            for i in range(1, n):
                lft[i] *= lft[i - 1]
                lft[i] %= MOD
            for i in range(n - 2, -1, -1):
                rht[i] *= rht[i + 1]
                rht[i] %= MOD
            for i in range(n):
                if G[idx][i] == par:
                    continue
                dist[idx] = 1
                if i:
                    dist[idx] *= lft[i - 1]
                    dist[idx] %= MOD
                if i + 1 < n:
                    dist[idx] *= rht[i + 1]
                    dist[idx] %= MOD
                stack.append((G[idx][i], idx))

    N, MOD = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        s, t = map(lambda x: int(x) - 1, input().split())
        G[s].append(t)
        G[t].append(s)

    topo = []
    P = [-1] * N
    node = [0]
    while node:
        v = node.pop()
        topo.append(v)
        for to in G[v]:
            if to == P[v]:
                continue
            P[to] = v
            node.append(to)

    dist = [1] * N
    ans = [1] * N
    dfs1(topo, P)
    dfs2(0, -1)
    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:

from functools import reduce
from itertools import accumulate,chain
def rerooting(N, adj, merge, identity, finalize):
    """
    merge: (T,T) -> T, (T, merge)はモノイド
    identity: 単位元
    finalize: T -> T

    以下の形で書けるdpは対応可能
    dp[u,v] = finalize(merge(dp[v,k] for k in adj[v] if k != u))
    ただし(u,v)は辺
    """

    order = [None]*N
    parent = [None]*N
    parent[0] = -1
    stack = [0]
    for i in range(N):
        v = stack.pop()
        order[i] = v
        for u in adj[v]:
            if parent[u] is None:
                parent[u] = v
                stack.append(u)

    # from leaf to parent
    dp_down = [None]*N
    for v in reversed(order[1:]):
        p = parent[v]
        dp_down[v] = finalize(reduce(merge,
            (dp_down[c] for c in adj[v] if c != p),
            identity))

    # from parent to leaf
    dp_up = [None]*N
    dp_up[0] = identity
    for v in order:
        p = parent[v]
        if len(adj[v]) == 1 and adj[v][0] == p:
            continue
        temp = tuple(chain((dp_up[v],),(dp_down[u] for u in adj[v] if u != p),(identity,)))
        left = tuple(accumulate(temp,merge))
        right = tuple(accumulate(reversed(temp),merge))
        i = 0
        for u in adj[v]:
            if u != p:
                dp_up[u] = finalize(merge(left[i],right[-i-2]))
                i += 1

    for v,l in enumerate(adj):
        order[v] = reduce(merge,
                    (dp_down[u] for u in adj[v] if u != parent[v]),
                    identity)
        order[v] = finalize(merge(order[v], dp_up[v]))

    return order

def solve(N,M,E):

    adj = [[] for _ in range(N)]
    for a,b in E:
        adj[a].append(b)
        adj[b].append(a)

    def merge(x,y):
        return (x*y)%M
    def finalize(x):
        return x+1

    res = rerooting(N,adj,merge,1,finalize)
    return [v-1 for v in res]


if __name__ == '__main__':
    N,M = map(int,input().split())
    E = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
    print(*solve(N,M,E),sep='\n')

Submission status: Wrong Answer

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 = [None for _ in range(N)]

def tdc(p, v):
    if G[v] == [p]:
        dp[v] = 1
        fm_bm[v] = [[], []]
        return 1
    res = 1
    fm = [1]
    bm = []
    for u in G[v]:
        if u == p: continue
        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

def buc(p, v, a):
    ans[v] = dp[v]*a%M
    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 
        buc(v, u, rev_dp)

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

Submission status: Wrong Answer

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 = []
    for u in G[v]:
        if u == p: continue
        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: Wrong Answer

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 = []
    for u in G[v]:
        if u == p: continue
        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
    fm, bm = fm_bm[v]
    C = list(set(G[v]) - set([p]))
    for i, u in enumerate(C):
        rev_dp = (fm[i]*bm[i+1]*a + 1)%M
        ans[u] = dp[u]*rev_dp%M
        buc(v, u, rev_dp)

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

Submission status: Wrong Answer

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 = []
    for u in G[v]:
        if u == p: continue
        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
    fm, bm = fm_bm[v]
    C = list(set(G[v]) - set([p]))
    for i, u in enumerate(C):
        if u == p: continue
        rev_dp = fm[i]*bm[i+1]*a + 1
        rev_dp %= M
        ans[u] = dp[u]*rev_dp
        ans[u] %= M
        buc(v, u, rev_dp)

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

Submission status: Wrong Answer

Solution code:
import sys 
sys.setrecursionlimit(100000) 
import queue

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 = {}
def rec(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+rec(v, u)) % M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 0       
rec(-1, r)

q = queue.Queue()
q.put(r)
ans = [0]*N
ans[r] = dp[(-1, r)]
parent = {r:-1}

while not q.empty():
    p = q.get()
    pf = [1]
    for v in G[p]:
        pf.append(pf[-1]*(dp[(p, v)]+1)%M)
    df = [1]
    for v in G[p][::-1]:
        df.append(df[-1]*(dp[(p, v)]+1)%M)
    for i in range(len(G[p])):
        v = G[p][i]
        if v != parent[p]:
            dp[(v, p)] = pf[i] * df[::-1][i+1] % M
            ans[v] = dp[(p, v)]*(1+dp[(v, p)]) % M
            q.put(v)
            parent[v] = p
        
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys 
sys.setrecursionlimit(100000) 
import queue

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
def rec(p, v):
    C = set(G[v]) - set([p])
    if len(C) == 0:
        dp[v] = 1
        return 1
    res = 1
    for u in C:
        res *= (1+rec(v, u))
    dp[v] = res % M
    return dp[v]

root = 0       
rec(None, root)

q = queue.Queue()
q.put(root)
ans = [0]*N
ans[root] = dp[root] % M

while not q.empty():
    p = q.get()
    for v in G[p]:
        if ans[v] > 0: continue
        ans[v] = int(dp[v]*(ans[p]/(1+dp[v])+1)) % M
        q.put(v)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import sys 
sys.setrecursionlimit(100000) 
import queue

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
def rec(p, v):
    C = set(G[v]) - set([p])
    if len(C) == 0:
        dp[v] = 1
        return 1
    res = 1
    for u in C:
        res *= (1+rec(v, u)) % M
    dp[v] = res % M
    return dp[v]

root = 0       
rec(None, root)

q = queue.Queue()
q.put(root)
ans = [0]*N
ans[root] = dp[root] % M

while not q.empty():
    p = q.get()
    for v in G[p]:
        if ans[v] > 0: continue
        ans[v] = int(dp[v]*(ans[p]/(1+dp[v])+1)) % M
        q.put(v)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
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(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

ws = {}
bs = {}
def sub(u, p):
    if (u,p) in ws:
        return ws[u,p], bs[u,p]
    w = 1
    b = 1
    for v in ns[u]:
        if v==p:
            continue
        ww,bb = sub(v, u)
        w += (bb-1)
        b *= (ww+bb)
    ws[u,p] = w
    bs[u,p] = b
    return w,b
ans = [None]*n
for u in range(n):
    ans[u] = sub(u, -1)[1] % M
write("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
# これだと左右からマージしていないから多分遅い？
from collections import deque
import sys

input = sys.stdin.buffer.readline


n, m = map(int, input().split())
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)

# 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 u in graph[v]:
        if par[v] == u:
            continue
        par[u] = v
        que.append(u)

for v in topo[::-1]:
    dp1[v] = 1
    for u in graph[v]:
        dp1[v] *= dp1[u] + 1

# 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
    dp2[v] = dp1[p]
    if par[p] != -1:
        dp2[v] *= dp2[par[p]] + 1
    dp2[v] //= dp1[v] + 1
    # dpの計算
    dp[v] = dp1[v] * (dp2[v] + 1)
    dp[v] %= m
print(*dp[1:], sep="\n")

Submission status: Wrong Answer

Solution code:
# これだと左右からマージしていないから多分遅い？
from collections import deque

n, m = map(int, input().split())
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)

# 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 u in graph[v]:
        if par[v] == u:
            continue
        par[u] = v
        que.append(u)

for v in topo[::-1]:
    dp1[v] = 1
    for u in graph[v]:
        dp1[v] *= dp1[u] + 1

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

for v in topo:
    p = par[v]
    dp2[v] = 1
    if p == -1:
        dp[v] = dp1[v]
        dp[v] %= m
        continue
    for u in graph[p]:
        if u == v:
            continue
        if u == par[p]:
            continue
        dp2[v] *= dp1[u] + 1
    if par[p] != -1:
        dp2[v] *= dp2[par[p]] + 1
    dp[v] = dp1[v] * (dp2[v] + 1)
    dp[v] %= m
print(*dp[1:], sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
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)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            que.append((child, node))
            rooted[node].append(child)
            rev_rooted[child].append(node)
            # print(node, child)

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

leaves = [node for node, children in enumerate(rooted) if not children]

dp = [1] * n
que = leaves.copy()
while que:
    node = que.pop()
    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)


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

Submission status: Wrong Answer

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


def solve(N: int, M: int, adj):
    sub = [0] * N

    def dfs(node, parent):
        r = 1
        for child in adj[node]:
            if child == parent:
                continue
            r = (r * (1 + dfs(child, node))) % M
        sub[node] = r
        return r

    dfs(0, -1)
    ans = [0] * N
    ans[0] = sub[0]

    def dfs2(node, parent):
        if parent != -1:
            ans[node] = sub[node]  # parent is white
            ans[node] += ans[parent] // (sub[node] + 1) * sub[node]

        for child in adj[node]:
            if child == parent:
                continue
            dfs2(child, node)

    dfs2(0, -1)
    return ans


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    adj = [[] for _ in range(N)]
    for i in range(N - 1):
        x = int(next(tokens)) - 1
        y = int(next(tokens)) - 1
        adj[x].append(y)
        adj[y].append(x)
    print(*solve(N, M, adj), sep="\n")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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)
    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 for nv in E[v]]
            right = [dp[nv] + 1 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] if cum_left[v] else 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: Wrong Answer

Solution code:
n,m,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for a,b in zip(*[iter(t)]*2):
  e[a-1]+=b-1,
  e[b-1]+=a-1,
o=[]
s=[0]
f=[1]*n
for v in s:
  o+=v,
  f[v]=0
  t=[]
  for w in e[v]:
    if f[w]:
      s+=w,
      t+=w,
  e[v]=t
dp1=[0]*n
for v in o[::-1]:
  t=1
  for w in e[v]:
    t=t*(dp1[w]+1)%m
  dp1[v]=t
dp2=[0]*n
dp2[0]=1
for v in o:
  t=dp2[v]*dp1[v]%m
  for w in e[v]:
    dp2[w]=t*pow(dp1[w]+1,m-2,m)+1
for dp1,dp2 in zip(dp1,dp2):
  print(dp1*dp2%m)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10 ** 7)

N, MOD = map(int, input().split())


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

DP1 = [-1] * (N + 1)
DP1[0] = 0
parent = [-1] * (N + 1)
parent[1] = 0

def dfs(x, p):
    tmp = 1
    for next_ in G[x]:
        if next_ == p:
            continue
        parent[next_] = x
        tmp *= (dfs(next_, x) + 1)
        tmp %= MOD
    DP1[x] = tmp
    return tmp

dfs(1, 0)
print (DP1)

DP2 = [1] * (N + 1)
stack = [1]

#next_とyとで2重ループになってO(N^2) (星型のとき)
while stack:
    x = stack.pop()

    # 累積積のパート

    #ここが同じ値を返すかチェックする
    n = len(G[x])
    lst1 = [1] * (n + 1)
    lst2 = [1] * (n + 1)
    for i in range(n):
        #親のときだけは違うルールで対処
        if G[x][i] == parent[x]:
            lst1[i + 1] = lst1[i] * DP2[x] % MOD
        else:
            lst1[i + 1] = lst1[i] * (DP1[G[x][i]] + 1) % MOD

        if G[x][n - 1 - i] == parent[x]:
            lst2[n - i - 1] = lst2[n - i] * DP2[x] % MOD
        else:
            lst2[n - i - 1] = lst2[n - i] * (DP1[G[x][n - 1 - i]] + 1) % MOD
    
    for i in range(n):
        if G[x][i] == parent[x]:
            continue
        tmp = lst1[i] * lst2[i + 1] % MOD
        tmp += 1 #白色の分
        DP2[G[x][i]] = tmp % MOD
        stack.append(G[x][i])

# print (DP2)

for i in range(1, N + 1):
    print ((DP1[i] * DP2[i]) % MOD)

# print (DP1)
# print (DP2)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10 ** 7)

N, MOD = map(int, input().split())


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

DP1 = [0] * (N + 1)

parent = [-1] * (N + 1)
parent[1] = 0

order = []

stack = [1]
while stack:
    x = stack.pop()
    order.append(x)
    for next_ in G[x]:
        if next_ == parent[x]:
            continue
        parent[next_] = x
        stack.append(next_)

for v in order[::-1]:
    tmp = 1
    for next_ in G[v]:
        tmp *= DP1[next_] + 1
        tmp %= MOD
    DP1[v] = tmp
# print (DP1)

DP2 = [1] * (N + 1)
# stack = [1]

#next_とyとで2重ループになってO(N^2) (星型のとき)
for x in order:


    # 累積積のパート
    #ここが同じ値を返すかチェックする
    n = len(G[x])
    lst1 = [1] * (n + 1)
    lst2 = [1] * (n + 1)
    for i in range(n):
        #親のときだけは違うルールで対処
        if G[x][i] == parent[x]:
            lst1[i + 1] = lst1[i] * DP2[x] % MOD
            lst2[n - i - 1] = lst2[n - i] * DP2[x] % MOD
            continue
        lst1[i + 1] = lst1[i] * (DP1[G[x][i]] + 1) % MOD
        lst2[n - i - 1] = lst2[n - i] * (DP1[G[x][n - 1 - i]] + 1) % MOD
    
    for i in range(n):
        if G[x][i] == parent[x]:
            continue
        tmp = lst1[i] * lst2[i + 1] % MOD
        tmp += 1 #白色の分
        DP2[G[x][i]] = tmp % MOD
        stack.append(G[x][i])

# print (DP2)

for i in range(1, N + 1):
    print ((DP1[i] * DP2[i]) % MOD)

# print (DP1)
# print (DP2)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10 ** 7)

N, MOD = map(int, input().split())


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

DP1 = [-1] * (N + 1)
DP1[0] = 0
parent = [-1] * (N + 1)
parent[1] = 0

def dfs(x, p):
    tmp = 1
    for next_ in G[x]:
        if next_ == p:
            continue
        parent[next_] = x
        tmp *= (dfs(next_, x) + 1)
        tmp %= MOD
    DP1[x] = tmp
    return tmp

dfs(1, 0)
# print (DP1)

DP2 = [1] * (N + 1)
# DP2[0] = 1
# DP2[1] = 1
stack = [1]

#next_とyとで2重ループになってO(N^2) (星型のとき)
while stack:
    x = stack.pop()
    n = len(G[x])
    lst1 = [1] * (n + 1)
    lst2 = [1] * (n + 1)
    for i in range(n):
        if G[x][i] == parent[x]:
            lst1[i + 1] = lst1[i] * DP2[x] % MOD
            lst2[n - i - 1] = lst2[n - i] * DP2[x] % MOD
            continue
        lst1[i + 1] = lst1[i] * (DP1[G[x][i]] + 1) % MOD
        lst2[n - i - 1] = lst2[n - i] * (DP1[G[x][n - 1 - i]] + 1) % MOD
    
    for i in range(n):
        if G[x][i] == parent[x]:
            continue
        tmp = lst1[i] * lst2[i + 1] % MOD
        tmp += 1 #白色の分
        DP2[G[x][i]] = tmp % MOD
        stack.append(G[x][i])

# print (DP2)

for i in range(1, N + 1):
    print ((DP1[i] * DP2[i]) % MOD)

# print (DP1)
# print (DP2)