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: Time Limit Exceeded

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 = [{} for _ in range(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: Time Limit Exceeded

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 = [[-1] * (n+1) for _ in range(n+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: Time Limit Exceeded

Solution code:
from collections import deque
N, M = map(int, input().split())
d = [set() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].add(b)
    d[b].add(a)

queue=deque([1])
vs = set([1])
vs_bfs = list()
parents = [0] * (N+1)
while queue:
    v = queue.popleft()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        queue.append(u)

dp = [0]*(N+1)
for v in vs_bfs[::-1]:
    r = 1
    for u in d[v]:
        r *= dp[u]+1
    dp[v] = r

dp2 = [0]*(N+1)
for v in vs_bfs:
    if v == 1:
        dp2[v] = dp[v]
        continue
    p = parents[v]
    dp2[v] = dp[v] * ((dp2[p]//(dp[v]+1)) + 1)
for i in range(1, N+1):
    dp2[i] = str(dp2[i] % M)
print("\n".join(dp2[1:]))

Submission status: Time Limit Exceeded

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)
        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)
            else:
                right[i] = 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)

    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: Time Limit Exceeded

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
        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)
        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)
            else:
                right[i] = 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)

    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: Time Limit Exceeded

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 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] = dp[t]+1
            right[i] = dp[t]+1
        for i in range(1, M):
            left[i] *= left[i-1]
        for i in range(M-2, 0, -1):
            right[i] *= right[i+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)

    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: Time Limit Exceeded

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


def dfs1(pos, par, e=1):
    """dfsを用いて前計算する"""
    for child in tree[pos]:
        if child == par:
            continue
        tmp = dfs1(child, pos)
        e *= (1 + tmp)
        e %= MOD
    st_val[pos] = e
    return st_val[pos]


def dfs2(pos, par):
    """全方位木DP"""
    q = deque([(pos, par)])
    while q:
        pos, par = q.pop()
        e = 1
        for child in tree[pos]:
            if child == par:
                ind = compress[par][pos]
                tmp = ruiseki_l[par][ind] * ruiseki_r[par][len(tree[par]) - ind - 1]
            else:
                tmp = st_val[child]
            e *= (1 + tmp)
            e %= MOD
            ind = compress[pos][child]
            re_subtree_val[pos][ind] = 1 + tmp

        for i in range(len(tree[pos])):
            ruiseki_l[pos][i + 1] = ruiseki_l[pos][i] * re_subtree_val[pos][i]
            ruiseki_l[pos][i + 1] %= MOD
        for i in range(len(tree[pos])):
            ruiseki_r[pos][i + 1] = ruiseki_r[pos][i] * re_subtree_val[pos][-i-1]
            ruiseki_r[pos][i + 1] %= MOD

        ans[pos] = e
        for child in tree[pos]:
            if child == par:
                continue
            else:
                q.append((child, pos))


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

# subtreeから値を集める
st_val = [0] * n
dfs1(0, -1)

# rerootによって、subtreeから値を集める。
re_subtree_val = [[1] * len(tree[i]) for i in range(n)]

# 左右それぞれの累積
ruiseki_l = [[1] * (len(tree[i]) + 1) for i in range(n)]
ruiseki_r = [[1] * (len(tree[i]) + 1) for i in range(n)]

compress = [{v: j for j, v in enumerate(tree[i])} for i in range(n)]
ans = [0]*n
dfs2(0, -1)

for i in range(n):
    print(ans[i] % MOD)

Submission status: Time Limit Exceeded

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


def dfs1(pos, par, e=1):
    """dfsを用いて前計算する"""
    for child in tree[pos]:
        if child == par:
            continue
        tmp = dfs1(child, pos)
        e *= (1 + tmp)
        e %= MOD
    st_val[pos] = e
    return st_val[pos]


def dfs2(pos, par):
    """全方位木DP"""
    e = 1
    for child in tree[pos]:
        if child == par:
            ind = compress[par][pos]
            tmp = ruiseki_l[par][ind] * ruiseki_r[par][len(tree[par]) - ind - 1]
        else:
            tmp = st_val[child]
        e *= (1 + tmp)
        e %= MOD
        ind = compress[pos][child]
        re_subtree_val[pos][ind] = 1 + tmp

    for i in range(len(tree[pos])):
        ruiseki_l[pos][i + 1] = ruiseki_l[pos][i] * re_subtree_val[pos][i]
        ruiseki_l[pos][i + 1] %= MOD
    for i in range(len(tree[pos])):
        ruiseki_r[pos][i + 1] = ruiseki_r[pos][i] * re_subtree_val[pos][-i-1]
        ruiseki_r[pos][i + 1] %= MOD

    ans[pos] = e
    for next_pos in tree[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)]
tree = [[] for i in range(n)]
for i in range(n-1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

# subtreeから値を集める
st_val = [0] * n
dfs1(0, -1)

# rerootによって、subtreeから値を集める。
re_subtree_val = [[1] * len(tree[i]) for i in range(n)]

# 左右それぞれの累積
ruiseki_l = [[1] * (len(tree[i]) + 1) for i in range(n)]
ruiseki_r = [[1] * (len(tree[i]) + 1) for i in range(n)]

compress = [{v: j for j, v in enumerate(tree[i])} for i in range(n)]
ans = [0]*n
dfs2(0, -1)

for i in range(n):
    print(ans[i] % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
# dp[u][v] uを根としたときのサブツリーvの値
dp = [[-1] * n for _ in range(n)]

def dfs(u=0, pu=-1):
    res = 1
    for v in to[u]:
        if v == pu: continue
        res *= dfs(v, u) + 1
        res %= m
    if pu != -1: dp[pu][u] = res
    return res

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    dfs()
    # bfsでdfsとは逆向きのdpを完成させる
    que = deque()
    que.append([0, -1])
    while que:
        u, pu = que.popleft()
        tn = len(to[u])
        # 累積積のための配列
        ll = [0] * tn
        rr = [0] * tn
        # uのサブツリーの値+1を入れる
        dpu = dp[u]
        for i, v in enumerate(to[u]):
            ll[i] = rr[i] = dpu[v] + 1
        # 左右から累積積を作る
        for i in range(1, tn):
            ll[i] = (ll[i - 1] * ll[i]) % m
            rr[tn - 1 - i] = (rr[tn - i] * rr[tn - 1 - i]) % m
        # 配列の最初or最後のために最後に1を追加
        ll += [1]
        rr += [1]
        # uの子vを根とみたときのサブツリーuの値を求める
        for i, v in enumerate(to[u]):
            if v == pu: continue
            dp[v][u] = (ll[i - 1] * rr[i + 1]) % m
            que.append([v, u])
    # p2D(dp)
    # 各頂点について答えを出す
    for u in range(n):
        ans = 1
        dpu = dp[u]
        for v in to[u]:
            ans = (ans * (dpu[v] + 1)) % m
        print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
dp = [[[-1] * 2 for _ in range(n)] for _ in range(n + 1)]

def dfs(u, pu=-1):
    if dp[pu][u][0] != -1:
        return dp[pu][u]
    w = b = 1
    for v in to[u]:
        if v == pu: continue
        vb, vw = dfs(v, u)
        b += b * vb
        w += vb + vw - 1
        b, w = b % m, w % m
    dp[pu][u] = [b, w]
    return [b, w]

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    for u in range(n):
        print(dfs(u)[0])

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
dp = [[[-1] * 2 for _ in range(n)] for _ in range(n + 1)]

def dfs(u, pu=-1):
    # if pu != -1 and dp[pu][u][0] != -1:
    #    return dp[pu][u]
    w = b = 1
    for v in to[u]:
        if v == pu: continue
        if dp[u][v][0] == -1: dfs(v, u)
        vb, vw = dp[u][v]
        b += b * vb
        w += vb + vw - 1
        b, w = b % m, w % m
    dp[pu][u] = [b, w]
    return

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    for u in range(n):
        dfs(u)
        print(dp[-1][u][0])

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)

def dfs(u, pu=-1):
    b = w = 1
    for v in to[u]:
        if v == pu: continue
        vb, vw = dfs(v, u)
        b += b * vb
        w += vb + vw - 1
        b, w = b % m, w % m
    return b, w

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    for u in range(n):
        print(dfs(u)[0])

main()

Submission status: Time Limit Exceeded

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 i in range(k):
            if(E[v][i]==p): continue
            dp[v]=1
            if(i>0): dp[v]*=l[i-1]
            if(i<k-1): dp[v]*=r[i+1]
            dp[v]%=m
            dfs2(E[v][i],v)
    dfs2(0,-1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

def dfs1(v,p):
    val=1
    pre_mul=[1]
    rev_mul=[]
    for c in links[v]:
        if c==p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res=1+dfs1(c,v)
        val*=res
        val%=m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v]=val
    for i in range(len(rev_mul)-2,-1,-1):
        rev_mul[i]*=rev_mul[i+1]
        rev_mul[i]%=m
    rev_mul.append(1)
    pre_muls[v]=[pre_mul,rev_mul]
    return val

def dfs2(v,p,a):
    dp[v]=dp[v]*a%m
    pmv=pre_muls[v]
    for i,c in enumerate(links[v]):
        if c==p:
            continue
        pmc=pmv[0][i]*pmv[1][i+1]%m
        pmc=pmc*a%m
        dfs2(c,v,pmc+1)


n,m=map(int,input().split())
links=[[] for i in range(n)]
dp=[0 for i in range(n)]
pre_muls=[None for i in range(n)]
for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].append(y)
    links[y].append(x)

dfs1(0,None)
dfs2(0,None,1)
print('\n'.join(map(str,dp)))

Submission status: Time Limit Exceeded

Solution code:
#全方位木DPによって求める
from collections import defaultdict
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
    cnt = 0
    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
    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)

child_pos = defaultdict(lambda :defaultdict(dict))

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

for i in range(n):
    print(b2[i]%MOD)

Submission status: Time Limit Exceeded

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]))
        dp[node][1] = (dp[node][1] * dp[i][1])
    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]));
        dp[node][1] = (dp[node][1] / dp[i][1]);
        dp[i][0] = (dp[i][0] * (dp[node][0] + dp[node][1]));
        dp[i][1] = (dp[i][1] * dp[node][1]);
        dfs2(i, node);
        dp[i][1] = (dp[i][1] / dp[node][1]);
        dp[i][0] = (dp[i][0] / (dp[node][0] + dp[node][1]));
        dp[node][0] = (dp[node][0] * (dp[i][0] + dp[i][1]));
        dp[node][1] = (dp[node][1] * dp[i][1]);
    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(dp2[i])

Submission status: Time Limit Exceeded

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 row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

ldp = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v].discard(parent)
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

def dfs_2(v=0,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    dp[v] = x * ldp[v][-1] % MOD
    for w,p,q in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        dfs_2(w,x*p*q%MOD+1)

dp = [None] * N
dfs_2()

print('\n'.join(map(str,dp)))

Submission status: Time Limit Exceeded

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 = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v] = [w for w in graph[v] if w != parent]
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

def dfs_2(v=0,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    dp[v] = x * ldp[v][-1] % MOD
    for w,p,q in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        dfs_2(w,x*p*q%MOD+1)

dp = [None] * N
dfs_2()

print('\n'.join(map(str,dp)))

Submission status: Time Limit Exceeded

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 = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v] = [w for w in graph[v] if w != parent]
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(vals[::-1],1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

def dfs_2(v=0,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    dp[v] = x * ldp[v][-1] % MOD
    for w,p,q in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        dfs_2(w,x*p*q%MOD+1)

dp = [None] * N
dfs_2()

print('\n'.join(map(str,dp)))

Submission status: Time Limit Exceeded

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


def dfs_2(v=1,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    dp[v] = x * dp_1[v] % MOD
    for w,p in zip(graph[v],products[v]):
        dfs_2(w,x*p%MOD+1)

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

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

Submission status: Time Limit Exceeded

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

dp_1

products

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

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

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

Submission status: Time Limit Exceeded

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

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

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

dp_1

products

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

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

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