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 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)
dp_ = [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:])))

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)

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]
    for x in arr[:-1]:
        L.append(L[-1] * x % MOD)
    R = [1]
    for x in arr[1:][::-1]:
        R.append(R[-1] * x % MOD)
    products = [x*y%MOD for x,y in zip(L,reversed(R))]
    dp[v] = arr[0] * products[0] % MOD
    for w,p in zip(graph[v],products):
        if w==parent:
            continue
        dfs_2(w,v,p+1)

dp = [0] * (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)

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] + 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 = [x*y%MOD for x,y in zip(L,R)]
    dp[v] = arr[0] * products[0] % MOD
    for w,p in zip(graph[v],products):
        if w==parent:
            continue
        dfs_2(w,v,p+1)

dp = [0] * (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 = [[] for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    for w in graph[v]:
        if w == parent:
            continue
        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] if w != parent else x 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 = [x*y%MOD for x,y in zip(L,R)]
    dp[v] = arr[0] * products[0] % MOD
    for w,p in zip(graph[v],products):
        if w==parent:
            continue
        dfs_2(w,v,p+1)

dp = [0] * (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 = [[] for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)

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

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

def make_products(arr):
    # 左右からの積を作る方法
    f = lambda x,y: x*y%MOD
    L = [1] + list(itertools.accumulate(arr[:-1], f))
    R = list(itertools.accumulate(arr[::-1][:-1], f))[::-1] + [1]
    return [f(x,y) for x,y in zip(L,R)]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import reduce
from operator import mul 


def getpar(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[0] = -1
    par[p]  -1
    stack = [p]
    visited = set([p])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            stack.append(vf)
    return par

def topological_sort_tree(E, r):
    Q = [r]
    L = []
    visited = set([r])
    while Q:
        vn = Q.pop()
        L.append(vn)
        for vf in E[vn]:
            if vf not in visited:
                visited.add(vf)
                Q.append(vf)
    return L

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


        

N, M = map(int, input().split())
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)

P = getpar(Edge, 0)
L = topological_sort_tree(Edge, 0)
C = getcld(P)

dp1 = [1]*N
for l in L[N-1:0:-1]:
    p = P[l]
    dp1[p] = (dp1[p]*(dp1[l]+1)) % M

dp2 = [1]*N
dp2[0] = dp1[0]
info = [0]*(N+1)
vmul = [reduce(mul, [dp1[j]+1 for j in C[i]], 1) for i in range(N)]
for l in L[1:]:
    p = P[l]
    pp = P[p]
    res = vmul[p]//(dp1[l]+1) % M
    res = res*(1+info[pp]) % M
    dp2[l] = dp1[l]*(res+1) % M
    info[p] = res % M

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

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

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


dp = [[0]*len(to_i) for to_i in to]
parent_index = [-9999]*n 
ans = [0]*n

def dfs(v, p):
    res = 1
    for i, vc in enumerate(to[v]):
        if vc == p:
            parent_index[v] = i
            continue
        dp[v][i] = dfs(vc, v)
        res *= dp[v][i]+1
        res %= MOD
    return res

def dfs2(v, res_p, p):
    deg = len(to[v])
    if p >= 0:
        dp[v][parent_index[v]] = res_p

    accl = [1]*(deg+1)
    for i, dpvi in enumerate(dp[v]):
        accl[i+1] = accl[i]*(dpvi+1)%MOD

    accr = [1]*(deg+1)
    for i, dpvir in enumerate(reversed(dp[v])):
        accr[-i-2] = accr[-i-1]*(dpvir+1)%MOD

    ans[v] = accr[0]
    for i,vc in enumerate(to[v]):
        if vc == p: continue
        dfs2(vc, accl[i]*accr[i+1]%MOD, v)

dfs(0,-1)
#print(dp)
dfs2(0,0,-1)
#print(dp)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

n,MOD = [int(i) for i in input().split()]

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


dp = [[0]*len(to_i) for to_i in to]
parent_index = [-9999]*n 
ans = [0]*n

def dfs(v, p):
    res = 1
    for i, vc in enumerate(to[v]):
        if vc == p:
            parent_index[v] = i
            continue
        """子供から情報をもらって処理する"""
        dp[v][i] = dfs(vc, v)
        res *= dp[v][i]+1
        res %= MOD
        """処理ここまで"""
    return res

def dfs2(v, res_p, p):
    deg = len(to[v])
    if p >= 0:
        dp[v][parent_index[v]] = res_p

    accl = [1]*(deg+1)
    for i, dpvi in enumerate(dp[v]):
        accl[i+1] = accl[i]*(dpvi+1)%MOD

    accr = [1]*(deg+1)
    for i, dpvir in enumerate(reversed(dp[v])):
        accr[-i-2] = accr[-i-1]*(dpvir+1)%MOD

    ans[v] = accr[0]
    for i,vc in enumerate(to[v]):
        if vc == p: continue
        dfs2(vc, accl[i]*accr[i+1]%MOD, v)

dfs(0,-1)
#print(dp)
dfs2(0,0,-1)
#print(dp)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__

from types import GeneratorType


def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to

    return wrappedfunc


def main():
    n, m = map(int, input().split())

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

    memo = [{} for _ in range(n)]

    @bootstrap
    def dfs(node, parent):
        try:
            yield memo[node][parent]
        except:
            cnt = 1
            for child in tree[node]:
                if child is not parent:
                    call = yield dfs(child, node)
                    cnt = (cnt * (call + 1)) % m
            memo[node][parent] = cnt
            yield cnt

    for i in range(n):
        print(dfs(i, -1))


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy
from __future__ import division, print_function

import os
import sys
from __builtin__ import xrange as range
from cStringIO import StringIO
from future_builtins import ascii, filter, hex, map, oct, zip
from io import IOBase

import __pypy__

from types import GeneratorType


def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to

    return wrappedfunc


def main():
    n, m = map(int, input().split())

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

    memo = {}

    @bootstrap
    def dfs(node, parent):
        try:
            yield memo[node, parent]
        except:
            cnt = 1
            for child in tree[node]:
                if child is not parent:
                    call = yield dfs(child, node)
                    cnt = (cnt * (call + 1)) % m
            memo[node, parent] = cnt
            yield cnt

    for i in range(n):
        print(dfs(i, -1))


# region fastio

BUFSIZE = 8192


class FastI(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = StringIO()
        self.newlines = 0

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count("\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()


class FastO(IOBase):
    def __init__(self, file):
        self._fd = file.fileno()
        self._buffer = __pypy__.builders.StringBuilder()
        self.write = lambda s: self._buffer.append(s)

    def flush(self):
        os.write(self._fd, self._buffer.build())
        self._buffer = __pypy__.builders.StringBuilder()


def print(*args, **kwargs):
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastI(sys.stdin), FastO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(v, p = -1):
    deg[v] = len(U[v])
    dp[v] = [0] * deg[v]
    ans = 1
    for i in range(deg[v]):
        u = U[v][i]
        if u == p:
            par[v] = i
            continue
        dp[v][i] = dfs(u, v)
        ans *= dp[v][i] + 1
        ans %= M
    return(ans)

def bfs(v, ans_p = 0, p = -1):
    if p != -1:
        dp[v][par[v]] = ans_p
    lmul = [1] * (deg[v] + 1)
    rmul = [1] * (deg[v] + 1)
    for i in range(1, deg[v] + 1):
        lmul[i] = lmul[i - 1] * (dp[v][i - 1] + 1) % M
        rmul[-i - 1] = rmul[-i] * (dp[v][-i] + 1) % M
    ans[v] = rmul[0]
    for i in range(deg[v]):
        u = U[v][i]
        if u == p:
            continue
        bfs(u, lmul[i] * rmul[i + 1] % M, v)

N, M = map(int, input().split()) # 1 <= N <= 10^5, 2 <= M <= 10^9
U = [list() for _ in range(N)]
for x, y in [map(int, input().split()) for _ in range(N - 1)]:
    U[x - 1].append(y - 1)
    U[y - 1].append(x - 1)
deg = [0] * N
par = [0] * N
dp = [None] * N
ans = [0] * N
dfs(0)
bfs(0)
print("\n".join([str(x) for x in ans]))

Submission status: Time Limit Exceeded

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

def f2(n):
    dp = [[0] * n for _ in range(n)]
    s = [1] * n

    def dfs(i, j):  # from i to j
        dpi = dp[i]
        if dpi[j]:
            return(dpi[j])
        dpij = 1
        for u in U[i]:
            if u != j:
                dpij = dpij * (dfs(u, i) + 1) % M
        s[j] = s[j] * (dpij + 1) % M
        dpi[j] = dpij
        return(dpij)

    for i in range(n):
        for u in U[i]:
            dfs(u, i)
    print("\n".join([str(x) for x in s]))

N, M = map(int, input().split()) # 1 <= N <= 10^5, 2 <= M <= 10^9
U = [set() for _ in range(N)]
for x, y in [map(int, input().split()) for _ in range(N - 1)]:
    U[x - 1].add(y - 1)
    U[y - 1].add(x - 1)
f2(N)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def f2(n):
    dp = [[0] * n for _ in range(n)]

    def dfs(i, j):  # from i to j
        if dp[i][j]:
            return(dp[i][j])
        dpij = 1
        for u in U[i]:
            if u != j:
                dpij = dpij * (dfs(u, i) + 1) % M
        dp[i][j] = dpij
        return(dpij)

    for i in range(n):
        ans = 1
        for u in U[i]:
            ans = ans * (dfs(u, i) + 1) % M
            if not ans:
              break
        print(ans)

N, M = map(int, input().split()) # 1 <= N <= 10^5, 2 <= M <= 10^9
U = [set() for _ in range(N)]
for x, y in [map(int, input().split()) for _ in range(N - 1)]:
    U[x - 1].add(y - 1)
    U[y - 1].add(x - 1)
f2(N)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def f2(n):
    dp = [[0] * n for _ in range(n)]

    def dfs(i, j):  # from i to j
        # print(i, "->", j)
        if dp[i][j]:
            return(dp[i][j])
        dpij = 1
        for u in U[i]:
            if u != j:
                dpij *= dfs(u, i) + 1
        dp[i][j] = dpij
        return(dpij)

    for i in range(n):
        ans = 1
        for u in U[i]:
            ans *= dfs(u, i) + 1
        print(ans % M)

N, M = map(int, input().split()) # 1 <= N <= 10^5, 2 <= M <= 10^9
U = [set() for _ in range(N)]
for x, y in [map(int, input().split()) for _ in range(N - 1)]:
    U[x - 1].add(y - 1)
    U[y - 1].add(x - 1)
f2(N)

Submission status: Time Limit Exceeded

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

def f(i):
    if dp[i]:
        return(False)
    dp[i] = 1
    for u in U[i]:
        if f(u):
            dp[i] = dp[i] * (dp[u] + 1)
    return(True)

N, M = map(int, input().split()) # 1 <= N <= 10^5, 2 <= M <= 10^9
U = [set() for _ in range(N)]
for x, y in [map(int, input().split()) for _ in range(N - 1)]:
    U[x - 1].add(y - 1)
    U[y - 1].add(x - 1)
# print(U)
for i in range(N):
    dp = [0] * N
    f(i)
    print(dp[i] % M)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def cnt(i, oya_i):
    if len(ko[i]) == 1 and oya_i:
        return 1
    if memo[i][oya_i] != 0:
        return memo[i][oya_i]
    re = 1
    for ko_i in ko[i]:
        if ko_i == oya_i: continue
        re *= (cnt(ko_i, i) + 1)
    memo[i][oya_i] = re = re % m
    return re


def f(n, m):
    for _ in range(n - 1):
        x, y = map(int, input().split())
        ko[x] += [y]
        ko[y] += [x]
    for start_i in range(1, n + 1):
        print(cnt(start_i, 0) % m)


n, m = map(int, input().split())
memo = [[0] * (n + 1) for _ in range(n + 1)]
ko = [[] for _ in range(n + 1)]
f(n, m)

Submission status: Time Limit Exceeded

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


def cnt(i, oya_i):
    if len(ko[i]) == 1 and oya_i:
        return 1
    if memo[i][oya_i] != 0:
        return memo[i][oya_i]
    re = 1
    for ko_i in ko[i]:
        if ko_i == oya_i: continue
        re *= (cnt(ko_i, i) + 1)
    memo[i][oya_i] = re
    return re


def f(n, m):
    for _ in range(n - 1):
        x, y = map(int, input().split())
        ko[x] += [y]
        ko[y] += [x]
    for start_i in range(1, n + 1):
        print(cnt(start_i, 0) % m)


n, m = map(int, input().split())
memo = [[0] * (n + 1) for _ in range(n + 1)]
ko = [[] for _ in range(n + 1)]
f(n, m)

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline


def cnt(i, oya_i):
    if len(ko[i]) == 1 and oya_i:
        return 1
    if memo[i][oya_i] != 0:
        return memo[i][oya_i]
    re = 1
    for ko_i in ko[i]:
        if ko_i == oya_i: continue
        re *= (cnt(ko_i, i) + 1)
    memo[i][oya_i] = re
    return re


def f(n, m):
    for _ in range(n - 1):
        x, y = map(int, input().split())
        ko[x] += [y]
        ko[y] += [x]
    for start_i in range(1, n + 1):
        print(cnt(start_i, 0) % m)


n, m = map(int, input().split())
memo = [[0] * (n + 1) for _ in range(n + 1)]
ko = [[] for _ in range(n + 1)]
f(n, m)

Submission status: Time Limit Exceeded

Solution code:
def cnt(i, oya_i):
    if len(ko[i]) == 1 and oya_i:
        return 1
    if memo[i][oya_i]!=0:
        return memo[i][oya_i]
    re = 1
    for ko_i in ko[i]:
        if ko_i == oya_i: continue
        re *= (cnt(ko_i, i) + 1)
    memo[i][oya_i]=re
    return re


kuro = 1
siro = 0
n, m = map(int, input().split())
ko = [[] for _ in range(n + 1)]
memo = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    ko[x] += [y]
    ko[y] += [x]
for start_i in range(1, n + 1):
    print(cnt(start_i, 0) % m)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [tuple(map(int, l.split())) for l in sys.stdin]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    if n == 1:
        return 1
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b = LI_()
        e[a].append(b)
        e[b].append(a)

    w = [None] * n

    d = [None] * n
    def f(i,p):
        r = 1
        s = [1]
        t = []
        for c in e[i]:
            if c == p:
                s.append(r)
                t.append(1)
                continue
            u = f(c,i) + 1
            r *= u
            r %= m
            s.append(r)
            t.append(u)
        for j in range(len(t)-2, -1, -1):
            t[j] *= t[j+1]
            t[j] %= m
        t.append(1)
        d[i] = [s, t]
        w[i] = r
        return r

    def g(i,p,k):
        w[i] *= k
        w[i] %= m
        s,t = d[i]
        for j,c in enumerate(e[i]):
            if c == p:
                continue
            g(c,i,(s[j] * t[j+1] * k) % m + 1)

    f(0, -1)
    g(0, -1, 1)
    return '\n'.join(map(str, w))


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [tuple(map(int, l.split())) for l in sys.stdin]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    if n == 1:
        return 1
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b = LI_()
        e[a].append(b)
        e[b].append(a)

    rr = [None] * n

    fm = [None] * n
    def f(i,p):
        if not fm[i] is None:
            return fm[i]
        r = 1
        for c in e[i]:
            if c != p:
                r *= f(c,i) + 1
                r %= m
        fm[i] = r
        return r

    def g(i,p,pp):
        v = e[i]
        l = len(v)
        ta = [(pp if u==p else f(u,i)) + 1 for u in v]

        if l == 1:
            rr[i] = ta[0] % m
            return

        aa = [None] * l
        aa[0] = ta[0]
        for j in range(1,l):
            aa[j] = aa[j-1] * ta[j] % m

        ba = [None] * l
        ba[-1] = ta[-1]
        for j in range(l-2,-1,-1):
            ba[j] = ba[j+1] * ta[j] % m

        rr[i] = ba[0] % m
        if v[0] != p:
            g(v[0],i,ba[1])
        for j,u in enumerate(v[1:-1]):
            if u != p:
                g(u,i,aa[j]*ba[j+2]%m)
        if v[-1] != p:
            g(v[-1],i,aa[-2])

    def h(i):
        l = len(e[i])
        v = e[i]
        ta = [f(u,i) + 1 for u in v]

        if l == 1:
            rr[i] = ta[0] % m
            g(v[0],i,1)
            return

        aa = [None] * l
        aa[0] = ta[0]
        for j in range(1,l):
            aa[j] = aa[j-1] * ta[j] % m

        ba = [None] * l
        ba[-1] = ta[-1]
        for j in range(l-2,-1,-1):
            ba[j] = ba[j+1] * ta[j] % m

        rr[i] = ba[0] % m
        g(v[0],i,ba[1])
        for j,u in enumerate(v[1:-1]):
            g(u,i,aa[j]*ba[j+2]%m)
        g(v[-1],i,aa[-2])

    h(1)

    return '\n'.join(map(str, rr))


print(main())

Submission status: Time Limit Exceeded

Solution code:


import sys
sys.setrecursionlimit(1000000)

def dfs1(u, pu):
    dp[u] = 1
    for v in tree[u]:
        if v != pu:
            dfs1(v, u)
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

def dfs2(u, pu, pval):
    resp[u] = (dp[u] * pval) % MOD

    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval
    for i in range(len(chlds)):
        v = chlds[i]
        vval = (1 + pref * cumulr[i]) % MOD

        dfs2(v, u, vval)

        pref *= (dp[v] + 1)
        pref %= MOD


n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)

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

Submission status: Time Limit Exceeded

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

N,mod=map(int,input().split())
EDGE=[list(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(1)
    sys.exit()

EDGELIST=[[] for i in range(N+1)]
for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

SCORELIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
PRODLIST_rev=[[-1]*len(EDGELIST[i]) for i in range(N+1)]
EDICT=dict()

for i in range(1,N+1):
    for j in range(len(EDGELIST[i])):
        EDICT[(i,EDGELIST[i][j])]=j

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

    ANS=1
    for to in EDGELIST[x]:
        if to==y:
            continue
        ANS=ANS*dp(to,x)%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1   
    return ANS+1

def dp2(x,y):
    if PRODLIST[x][0]==-1:
        PRODLIST[x][0]=(SCORELIST[x][0])%mod
        for i in range(1,len(EDGELIST[x])):
            PRODLIST[x][i]=PRODLIST[x][i-1]*SCORELIST[x][i]%mod

        PRODLIST_rev[x][-1]=SCORELIST[x][-1]
        for i in range(len(EDGELIST[x])-2,-1,-1):
            PRODLIST_rev[x][i]=PRODLIST_rev[x][i+1]*SCORELIST[x][i]%mod

    if len(EDGELIST[x])==1:
        ANS=1
    elif EDICT[(x,y)]==0:
        ANS=PRODLIST_rev[x][1]
    elif EDICT[(x,y)]==len(EDGELIST[x])-1:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]
    else:
        ANS=PRODLIST[x][EDICT[(x,y)]-1]*PRODLIST_rev[x][EDICT[(x,y)]+1]%mod

    SCORELIST[y][EDICT[(y,x)]]=ANS+1

for to in EDGELIST[1]:
    dp(to,1)

QUE=deque([1])
check=[0]*(N+1)

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue
    for to in EDGELIST[x]:
        if check[x]==0 or check[to]==0:
            dp2(x,to)
            QUE.append(to)
    check[x]=1

for i in range(1,N+1):
    print(PRODLIST[i][-1])