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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
G = [[]for i in range(n)]
for i in range(n - 1):
    x, y = map(lambda z: int(z) - 1,input().split())
    G[x].append(y)
    G[y].append(x)

ans = [-1 for _ in range(n)]
def dfs1(now,pre):
    res = 1
    for to in G[now]:
        if to == pre:
            continue
        res *= (dfs1(to,now) + 1)
        res %= m
    ans[now] = res
    return res

dfs1(0, -1)

def dfs2(now,pre):
    for to in G[now]:
        if to == pre:
            continue
        ans[to] *= (ans[now]//(ans[to]+1)+1)
        ans[to] %= m
        dfs2(to,now)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
from collections import deque


N, M = map(int, input().split())
MOD = 10**9 + 7
tree = [[] for i in range(N)]
for i in range(N-1):
  x, y = map(int, input().split())
  tree[x-1].append(y-1)
  tree[y-1].append(x-1)


dp1 = [0] * N
dp2 = [0] * N

def solve(node, parent):
  global dp1
  if dp1[node] > 0:
    return dp1[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        continue
      t *= (solve(child, node) + 1)
      # t %= M
    
    dp1[node] = t
    return t


_ = solve(0, -1)

dp2[0] = dp1[0]
d = deque([])
for child in tree[0]:
  d.append([child, 0])

while d:
  node, parent = d.popleft()
  dp2[node] = (dp2[parent]//(dp1[node]+1) + 1) * dp1[node] % MOD
  children = tree[node]
  for child in children:
    if child == parent:
      continue
    
    d.append([child, node])

print(*dp2, sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque

# そもそもこのまま頑張ってTLE取れるのか？
# WAになるのはわかった上で実験

import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
MOD = 10**9 + 7
tree = [[] for i in range(N)]
for i in range(N-1):
  x, y = map(int, input().split())
  tree[x-1].append(y-1)
  tree[y-1].append(x-1)


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


dp1 = [0] * N
dp2 = [0] * N

def solve(node, parent):
  global dp1
  if dp1[node] > 0:
    return dp1[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        continue
      t *= (solve(child, node) + 1)
      t %= MOD
    
    dp1[node] = t
    return t


_ = solve(0, -1)

dp2[0] = dp1[0]
d = deque([])
for child in tree[0]:
  d.append([child, 0])

while d:
  node, parent = d.popleft()
  dp2[node] = (dp2[parent] * power(dp1[node]+1, MOD-2) + 1) * dp1[node] % MOD
  children = tree[node]
  for child in children:
    if child == parent:
      continue
    
    d.append([child, node])

print(*dp2, sep='\n')

Submission status: Wrong Answer

Solution code:
# そもそもこのまま頑張ってTLE取れるのか？
# WAになるのはわかった上で実験

import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
MOD = 10**9 + 7
tree = [[] for i in range(N)]
for i in range(N-1):
  x, y = map(int, input().split())
  tree[x-1].append(y-1)
  tree[y-1].append(x-1)


def power(n, r, mod=10**9+7):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod


dp1 = [0] * N
dp2 = [0] * N
parents = [-1] * N
leaf_nodes = []

def solve1(node, parent):
  global dp1
  global parents
  global leaf_nodes
  parents[node] = parent
  if dp1[node] > 0:
    return dp1[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        continue
      t *= (solve1(child, node) + 1)
      t %= MOD
    
    if len(children) == 1:
      leaf_nodes.append(node)
    
    dp1[node] = t
    return t


def solve2(node):
  global dp2
  global parents
  parent = parents[node]
  if dp2[node] > 0:
    return dp2[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        t *= (solve2(parent)*power(dp1[node]+1, MOD-2) + 1)
        t %= MOD
      else:
        t *= (dp1[child] + 1)
        t %= MOD
    
    dp2[node] = t
    return t


_ = solve1(0, -1)
dp2[0] = dp1[0]
for leaf in leaf_nodes:
  _ = solve2(leaf)

print(*dp2, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
tree = [[] for i in range(N)]
for i in range(N-1):
  x, y = map(int, input().split())
  tree[x-1].append(y-1)
  tree[y-1].append(x-1)


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        return g, modinv(a//g, m)[1]
    else:
        return g, x % m


dp1 = [0] * N
dp2 = [0] * N
parents = [-1] * N
leaf_nodes = []

def solve1(node, parent):
  global dp1
  global parents
  global leaf_nodes
  parents[node] = parent
  if dp1[node] > 0:
    return dp1[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        continue
      t *= (solve1(child, node) + 1)
      t %= M
    
    if len(children) == 1:
      leaf_nodes.append(node)
    
    dp1[node] = t
    return t


def solve2(node):
  global dp2
  global parents
  parent = parents[node]
  if dp2[node] > 0:
    return dp2[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        g, inv = modinv(dp1[node]+1, M)
        t *= (solve2(parent)*inv//g + 1)
        t %= M
      else:
        t *= (dp1[child] + 1)
        t %= M
    
    dp2[node] = t
    return t


_ = solve1(0, -1)
dp2[0] = dp1[0]
for leaf in leaf_nodes:
  _ = solve2(leaf)

print(*dp2, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

n, m = map(int,input().split())

neighbor = {}
for i in range(1,n+1):
    neighbor[i] = []

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

dp = [{}] * (n+1)
for i in range(1,n+1):
    for j in neighbor[i]:
        dp[i][j] = -1

def calc_dp(x, y):
    if(dp[x][y] != -1):
        return(dp[x][y])

    if(len(neighbor[y]) == 1):
        dp[x][y] = 2 % m
        return(dp[x][y])

    temp = 1
    for i in neighbor[y]:
        if(i == x):
            continue

        temp = temp * (calc_dp(y,i)) % m

    temp = (temp + 1) % m
    dp[x][y] = temp
    return(temp)

for i in range(1,n+1):
    ans = 1
    for j in neighbor[i]:
        ans = ans * calc_dp(i,j) % m
    print(ans)

Submission status: Wrong Answer

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


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    g = Graph(N)
    for xx, yy in zip(x, y):
        g.add_edge(xx-1, yy-1)
        g.add_edge(yy-1, xx-1)

    dp = [0]*N

    def dfs(node, par=-1):
        dp[node] = 1
        for child, _ in g.E[node]:
            if child == par:
                continue
            dp[node] *= dfs(child, node) + 1
            dp[node] %= M
        return dp[node]

    ans = [0]*N

    def dfs_2(node, par=-1):
        ans[node] = 1
        for child, _ in g.E[node]:
            ans[node] *= dp[child]+1

        # 一要素を覗いた積を求めるため、昇順の積、降順の積を求めておく
        M = len(g.E[node])
        left, right = [1]*M, [1]*M
        for i in range(M):
            t, w = g.E[node][i]
            left[i] = left[i-1]*(dp[t]+1)
            left[i] %= M
        for i in range(M-1, -1, -1):
            t, w = g.E[node][i]
            if i != M-1:
                right[i] = right[i+1]*(dp[t]+1)
                right[i] %= M
            else:
                right[i] = dp[t]+1
                right[i] %= M

        for i in range(M):
            child, _ = g.E[node][i]
            if child == par:
                continue
            dp[node] = 1
            if i:
                dp[node] *= left[i-1]
                dp[node] %= M
            if i+1 < M:
                dp[node] *= right[i+1]
                dp[node] %= M
            dfs_2(child, node)
    dfs(0)
    dfs_2(0)

    for a in ans:
        print(a % M)

    return


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
    x = [int()] * (N - 1)  # type: "List[int]"
    y = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")
from collections import defaultdict
from collections import deque
sys.setrecursionlimit(10**8)


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))


def array(*args, initial=0):
    Spre, Spost = "", ""
    while len(args) > 0:
        Spre += "["
        Spost += " for _ in range("+str(args[-1])+")]"
        args = args[:-1]
    S = Spre + str(initial) + Spost
    return eval(S)


def solve(N: int, M: int, x: "List[int]", y: "List[int]"):
    g = Graph(N)
    for xx, yy in zip(x, y):
        g.add_edge(xx-1, yy-1)
        g.add_edge(yy-1, xx-1)

    dp = [0]*N

    def dfs(node, par=-1):
        dp[node] = 1
        for child, _ in g.E[node]:
            if child == par:
                continue
            dfs(child, node)
            dp[node] *= dp[child] + 1

    ans = [0]*N

    def dfs_2(node, par=-1):
        ans[node] = 1
        for child, _ in g.E[node]:
            ans[node] *= dp[child]+1

        # 一要素を覗いた積を求めるため、昇順の積、降順の積を求めておく
        M = len(g.E[node])
        left, right = [1]*M, [1]*M
        for i in range(M):
            t, w = g.E[node][i]
            left[i] = left[i-1]*(dp[t]+1)
            t, w = g.E[node][M-i-1]
            right[i] = right[M-i-1]*(dp[t]+1)

        for i in range(M):
            child, _ = g.E[node][i]
            if child == par:
                continue
            dp[node] = 1
            if i:
                dp[node] *= left[i-1]
            if i+1 < M:
                dp[node] *= right[i+1]
            dfs_2(child, node)
    dfs(0)
    dfs_2(0)

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

    return


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
    x = [int()] * (N - 1)  # type: "List[int]"
    y = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, M, x, y)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

    # 木DP(0-rooted tree)
    dp=[1]*n
    def dfs1(v,p)->NoneType:
        for nv in E[v]:
            if(nv==p): continue
            dfs1(nv,v)
            dp[v]*=(dp[nv]+1)
            dp[v]%=m
    dfs1(0,-1)

    # 全方位木DP
    ans=[1]*n
    def dfs2(v,p):
        # dpがv-rootedの状態なので、答えを確定させる
        for nv in E[v]:
            ans[v]*=dp[nv]+1
            ans[v]%=m
        # vの子nvに対して、nvの処理を行う前に、dp[v]をnv-rootedに変更する
        k=len(E[v])
        l=[0]*k
        r=[0]*k
        for i in range(k):
            l[i]=r[i]=dp[E[v][i]]+1
        for i in range(1,k):
            l[i]*=l[i-1]
            l[i]%=m
        for i in range(k-2,-1,-1):
            r[i]*=r[i+1]
            r[i]%=m
        for nv in E[v]:
            if(nv==p): continue
            dp[v]=1
            if(i>0): dp[v]*=l[i-1]
            if(i+1<k): dp[v]*=r[i+1]
            dp[v]%=m
            dfs2(nv,v)
    dfs2(0,-1)

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

Submission status: Wrong Answer

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

    # 木DP(0-rooted tree)
    dp=[1]*n
    def dfs1(v,p)->NoneType:
        for nv in E[v]:
            if(nv==p): continue
            dfs1(nv,v)
            dp[v]*=(dp[nv]+1)
            dp[v]%=m
    dfs1(0,-1)

    # 全方位木DP
    ans=[1]*n
    def dfs2(v,p):
        # dpがv-rootedの状態なので、答えを確定させる
        for nv in E[v]:
            ans[v]*=dp[nv]+1
            ans[v]%=m
        # vの子nvに対して、nvの処理を行う前に、dp[v]をnv-rootedに変更する　
        for nv in E[v]:
            if(nv==p): continue
            dp[v]=1
            for nv2 in E[v]:
                if(nv2==nv): continue
                dp[v]*=dp[nv2]+1
                dp[v]%=m
            dfs2(nv,v)
    dfs2(0,-1)

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

Submission status: Wrong Answer

Solution code:
#全方位木DPによって求める
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


def get_par_tree(tree: list, par: int) -> list:
    """親を求める"""
    n = len(tree)
    ans = [-1] * n
    visited = [False] * n
    visited[par] = True
    q = deque([par])
    while q:
        pos = q.popleft()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            ans[next_pos] = pos
    return ans


def topological_sort_tree(tree: list, par) -> list:
    n = len(tree)
    ans = [par]
    visited = [False] * n
    visited[par] = True
    q = deque([par])
    while q:
        pos = q.popleft()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            visited[next_pos] = True
            ans.append(next_pos)
            q.append(next_pos)
    return ans


def dfs1():
    """その頂点の部分木での黒色で塗るパターンを求める"""
    visited = [False] * n
    for pos in tp_list[::-1]:
        visited[pos] = True
        for next_pos in graph[pos]:
            if visited[next_pos]:
                continue
            b1[next_pos] *= (1 + b1[pos])
            b1[next_pos] %= MOD


def dfs2():
    """全方位木DP"""
    for pos in tp_list:
        cnt = 0
        b = 1
        par = par_list[pos]
        for next_pos in graph[pos]:
            if next_pos == par:
                d = child_pos[par][pos]
                tmp_b = ruiseki_child_l[par][d] * ruiseki_child_r[par][-d-2]
                tmp_b %= MOD
                b *= (1 + tmp_b)
                b %= MOD
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + tmp_b)
                cnt += 1
            else:
                b *= (1 + b1[next_pos])
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + b1[next_pos])
                cnt += 1
                b %= MOD
        b2[pos] = b
        ruiseki_child_l[pos] += child_val[pos] 
        ruiseki_child_r[pos] += child_val[pos][::-1]
        for i in range(len(child_val[pos])):
            ruiseki_child_r[pos][i+1] = ruiseki_child_r[pos][i] * ruiseki_child_r[pos][i+1]
            ruiseki_child_l[pos][i+1] = ruiseki_child_l[pos][i] * ruiseki_child_l[pos][i+1]
            ruiseki_child_r[pos][i+1] %= MOD
            ruiseki_child_l[pos][i+1] %= MOD


n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
dag = [[] for i in range(n)]

for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[b].append(a)
    graph[a].append(b)

par_list = get_par_tree(graph, 0)
tp_list = topological_sort_tree(graph, 0)
b1 = [1] * n
dfs1()

child_pos = defaultdict(lambda :defaultdict(dict))
child_val = [[] for i in range(n)]
ruiseki_child_l = [[1] for i in range(n)]
ruiseki_child_r = [[1] for i in range(n)]
b2 = [0] * n
dfs2()

for num in b2:
    print(num % MOD)

Submission status: Wrong Answer

Solution code:
#全方位木DPによって求める
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


def get_par_tree(tree: list, par: int) -> list:
    """親を求める"""
    n = len(tree)
    ans = [-1] * n
    visited = [False] * n
    visited[par] = True
    q = deque([par])
    while q:
        pos = q.popleft()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            ans[next_pos] = pos
    return ans


def topological_sort_tree(tree: list, par) -> list:
    n = len(tree)
    ans = [par]
    visited = [False] * n
    visited[par] = True
    q = deque([par])
    while q:
        pos = q.popleft()
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            ans.append(next_pos)
    return ans


def dfs1():
    """その頂点の部分木での黒色で塗るパターンを求める"""
    visited = [False] * n
    for pos in tp_list[::-1]:
        visited[pos] = True
        for next_pos in graph[pos]:
            if visited[next_pos]:
                continue
            b1[next_pos] *= (1 + b1[pos])
            b1[next_pos] %= MOD


def dfs2():
    """全方位木DP"""
    for pos in tp_list:
        cnt = 0
        b = 1
        par = par_list[pos]
        for next_pos in graph[pos]:
            if next_pos == par:
                d = child_pos[par][pos]
                tmp_b = ruiseki_child_l[par][d] * ruiseki_child_r[par][-d-2]
                tmp_b %= MOD
                b *= (1 + tmp_b)
                b %= MOD
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + tmp_b)
                cnt += 1
            else:
                b *= (1 + b1[next_pos])
                child_pos[pos][next_pos] = cnt
                child_val[pos].append(1 + b1[next_pos])
                cnt += 1
                b %= MOD
        b2[pos] = b
        ruiseki_child_l[pos] += child_val[pos] 
        ruiseki_child_r[pos] += child_val[pos][::-1]
        for i in range(len(child_val[pos])):
            ruiseki_child_r[pos][i+1] = ruiseki_child_r[pos][i] * ruiseki_child_r[pos][i+1]
            ruiseki_child_l[pos][i+1] = ruiseki_child_l[pos][i] * ruiseki_child_l[pos][i+1]
            ruiseki_child_r[pos][i+1] %= MOD
            ruiseki_child_l[pos][i+1] %= MOD


n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
dag = [[] for i in range(n)]

for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[b].append(a)
    graph[a].append(b)

par_list = get_par_tree(graph, 0)
tp_list = topological_sort_tree(graph, 0)
b1 = [1] * n
dfs1()

child_pos = defaultdict(lambda :defaultdict(dict))
child_val = [[] for i in range(n)]
ruiseki_child_l = [[1] for i in range(n)]
ruiseki_child_r = [[1] for i in range(n)]
b2 = [0] * n
dfs2()

for num in b2:
    print(num % MOD)

Submission status: Wrong Answer

Solution code:
#全方位木DPによって求める
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


def dfs1(pos, par):
    """その頂点の部分木での黒色で塗るパターンを求める"""
    b = 1
    for next_pos in graph[pos]:
        if next_pos == par:
            continue
        dfs1(next_pos, pos)
        b *= (1 + b1[next_pos])
        b %= MOD
    b1[pos] = b

n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)


b1 = [0] * n
dfs1(0, -1)

Submission status: Wrong Answer

Solution code:
#全方位木DPによって求める
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9 + 7)


def dfs1(pos, par):
    """その頂点の部分木での黒色で塗るパターンを求める"""
    b = 1
    for next_pos in graph[pos]:
        if next_pos == par:
            continue
        tmp_b = dfs1(next_pos, pos)
        b *= (1 + tmp_b)
        b %= MOD
    b1[pos] = b
    return b

n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

child_pos = defaultdict(lambda :defaultdict(dict))

b1 = [0] * n
dfs1(0, -1)

ruiseki_child_l = [[1] for i in range(n)]
ruiseki_child_r = [[1] for i in range(n)]

Submission status: Wrong Answer

Solution code:
#全方位木DPによって求める
import sys
sys.setrecursionlimit(10**9 + 7)


def dfs1(pos, par):
    """その頂点の部分木での黒色で塗るパターンを求める"""
    b = 1    
    for next_pos in graph[pos]:
        if next_pos == par:
            continue
        tmp_b = dfs1(next_pos, pos)
        b *= (1 + tmp_b)
        b %= MOD
    b1[pos] = b
    return b


def dfs2(pos, par):
    """全方位木DP"""
    b = 1
    for next_pos in graph[pos]:
        if next_pos == par:
            b *= 1 + (1 + b2[next_pos]) // (b1[pos] + 1)
            b %= MOD
        else:
            b *= (1 + b1[next_pos])
            b %= MOD
    b2[pos] = b

    for next_pos in graph[pos]:
        if next_pos == par:
            continue
        else:
            dfs2(next_pos, pos)
                
                
n, m = map(int, input().split())
MOD = m
info = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for i in range(n)]
for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

b1 = [0] * n
b2 = [0] * n
dfs1(0, -1)
dfs2(0, -1)
for i in range(n):
    print(b2[i])

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, MOD = [int(i) for i in input().split()]
adj = [[] for _ in [0] * (n+1)]
dp = [[0, 0] for i in range(n+1)]
dp2 = [0] * (n+1)


def dfs1(node, pn):
    dp[node] = [1, 1]
    for i in adj[node]:
        if i == pn:
            continue
        dfs1(i, node)
        dp[node][0] = (dp[node][0] * (dp[i][0] + dp[i][1])) % MOD
        dp[node][1] = (dp[node][1] * dp[i][1]) % MOD
    return



def dfs2(node, pn):
    dp2[node] = dp[node][0] % MOD

    for i in adj[node]:
        if i == pn:
            continue

        dp[node][0] = (dp[node][0] / (dp[i][0] + dp[i][1])) % MOD;
        dp[node][1] = (dp[node][1] / dp[i][1]) % MOD;
        dp[i][0] = (dp[i][0] * (dp[node][0] + dp[node][1])) % MOD;
        dp[i][1] = (dp[i][1] * dp[node][1]) % MOD;
        dfs2(i, node);
        dp[i][1] = (dp[i][1] / dp[node][1]) % MOD;
        dp[i][0] = (dp[i][0] / (dp[node][0] + dp[node][1])) % MOD;
        dp[node][0] = (dp[node][0] * (dp[i][0] + dp[i][1])) % MOD;
        dp[node][1] = (dp[node][1] * dp[i][1]) % MOD;
    return



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

dfs1(1, -1)
dfs2(1, -1)

for i in range(1, n+1):
    print(int(dp2[i]))

Submission status: Wrong Answer

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [[] for _ in range(N)]
for row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

Submission status: Wrong Answer

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [[] for _ in range(N)]
for row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

ldp = [[1]*(len(graph[v])) for v in range(N)]
rdp = [[1]*(len(graph[v])) for v in range(N)]

Submission status: Wrong Answer

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

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

ldp = [[1]*(len(graph[v])) for v in range(N)]
rdp = [[1]*(len(graph[v])) for v in range(N)]

Submission status: Wrong Answer

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

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

ldp = [[1]*(len(graph[v])) for v in range(N)]
rdp = [[1]*(len(graph[v])) for v in range(N)]

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    vals = [dfs_1(w,v) for w in graph[v] if w != parent]
    return

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

Submission status: Wrong Answer

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

ldp = [[1]*(len(graph[v])) for v in range(N)]
rdp = [[1]*(len(graph[v])) for v in range(N)]

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    graph[v].discard(parent)
    vals = [dfs_1(w,v) for w in graph[v]]
    return

dfs_1()

Submission status: Wrong Answer

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

dp_1 = [None] * (N+1)
products = [[] for _ in range(N+1)]

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    if graph[v]:
        arr = [dfs_1(w,v)+1 for w in graph[v]]
        dp_1[v] = 1
    else:
        dp_1[v] = 1
    return 1

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

Submission status: Wrong Answer

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

dp_1 = [None] * (N+1)
products = [[] for _ in range(N+1)]

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    if graph[v]:
        arr = [dfs_1(w,v)+1 for w in graph[v]]
        L = list(itertools.accumulate(arr[:-1], lambda x,y: x*y%MOD))
        R = list(itertools.accumulate(arr[1:][::-1], lambda x,y: x*y%MOD))[::-1]
        products[v] = [x*y%MOD for x,y in zip(L,R)]
        dp_1[v] = 1
    else:
        dp_1[v] = 1
    return 1

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

Submission status: Wrong Answer

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

dp_1 = [None] * (N+1)
products = [[] for _ in range(N+1)]

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    if graph[v]:
        arr = [dfs_1(w,v)+1 for w in graph[v]]
        L = [1] + list(itertools.accumulate(arr[:-1], lambda x,y: x*y%MOD))
        R = list(itertools.accumulate(arr[1:][::-1], lambda x,y: x*y%MOD))[::-1] + [1]
        products[v] = [x*y%MOD for x,y in zip(L,R)]
        dp_1[v] = products[v][0] * arr[0] % MOD
    else:
        dp_1[v] = 1
    return dp_1[v]

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

Submission status: Wrong Answer

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

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    for w in graph[v]:
        x *= (dfs_1(w,v) + 1)
    dp_1[v] = x
    return x

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

def dfs_2(v=1,parent=None,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    arr = [1 + dp_1[w] for w in graph[v]] + [x]
    L = (1,) + tuple(itertools.accumulate(arr, lambda x,y: x*y%MOD))
    R = tuple(itertools.accumulate(arr[1:][::-1], lambda x,y: x*y%MOD))[::-1] + (1,)
    dp[v] = L[-1]
    for w,x,y in zip(graph[v],L,R):
        dfs_2(w,v,x*y%MOD+1)

dp = [0] * (N+1)
dfs_2()

print('\n'.join(map(str,dp[1:])))