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:
#!/usr/bin/env python3
import collections
import sys

sys.setrecursionlimit(10 ** 8)


def solve(N: int, M: int, adj):
    sub = collections.defaultdict(lambda: 0)

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

    ans = [0] * N
    for i in range(N):
        ans[i] = dfs(i, -1)
    return ans


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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)


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

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

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

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

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

    dfs2(0, -1)
    return [a % M for a in ans]


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

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


class Tree:
    def __init__(self, crdinal, adjgrph, root):
        self.n = crdinal
        self.g = adjgrph
        self.root = root
        self.parent = [-1]*self.n
        self.depth = [-1]*self.n
        self.subsize = [1]*self.n
        self.result = [1]*self.n  # 0 : additive, 1 : multiplicative

        s = [self.root]
        while s:
            v = s.pop()
            if self.depth[v] == -1:
                if v == self.root:
                    self.depth[v] = 0
                else:
                    self.depth[v] = self.depth[self.parent[v]] + 1
                    s.append(v)
                for w in self.g[v]:
                    if self.depth[w] == -1:
                        self.parent[w] = v
                        s.append(w)
            else:
                self.subsize[self.parent[v]] += self.subsize[v]
                self.calc(v)

    def calc(self, v):
        # The following formula is calculated by bottom-up:
        self.result[self.parent[v]] *= self.result[v]+1
        self.result[self.parent[v]] %= m
        return None

    def wanted(self):
        # Edit the result you want using self.depth, self.subsize, etc..
        # Default : self.parent
        return self.parent

    def rerooting(self) -> list:
        cum1 = [[1] for i in range(n)]  # 0 : additive, 1 : multiplicative
        cum2 = [[1] for i in range(n)]  # 0 : additive, 1 : multiplicative
        SisterAll = [{} for _ in range(n)]
        ans = [0]*n
        ans[0] = self.result[0]

        s = [self.root]
        while s:
            v = s.pop()
            if v != self.root:
                ans[v] = SisterAll[v][self.parent[v]]*self.result[v]
                ans[v] %= m

            for w in self.g[v]:
                if w != self.parent[v]:
                    cum1[v].append(cum1[v][-1]*(self.result[w]+1))
                    s.append(w)
                else:
                    cum1[v].append(cum1[v][-1]*SisterAll[v][w])
            for w in self.g[v][::-1]:
                if w != self.parent[v]:
                    cum2[v].append(cum2[v][-1]*(self.result[w]+1))
                else:
                    cum2[v].append(cum2[v][-1]*SisterAll[v][w])
            cum2[v] = cum2[v][::-1]

            for i, w in enumerate(self.g[v]):
                SisterAll[w][v] = cum1[v][i]*cum2[v][i+1]+1
        return ans


n, m = map(int, input().split())
g = [[] for _ in range(n)]

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


T1 = Tree(n, g, 0)

ans = T1.rerooting()


for x in T1.rerooting():
    print(x)

Submission status: Time Limit Exceeded

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

    topological_sort = []
    parent = [None] * n
    stack = [(~0, -1), (0, -1)] # (v, p)
    while stack:
        v, p = stack.pop()
        if v >= 0:
            parent[v] = p
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            if deg[~v] == 0:
                topological_sort.append(~v)
            deg[p] -= 1

    # tree DP
    dp = [None] * n
    for v in topological_sort:
        res = 1
        for nv in E[v]:
            if nv == parent[v]:
                continue
            res = res * (dp[nv] + 1) % MOD
        dp[v] = res

    # rerooting
    def rerooting(v, p):
        if v == -1 or p == -1:
            return

        # 初めは計算量を無視
        p_res = 1
        for nv in E[p]:
            if nv == v:
                continue
            p_res = p_res * (dp[nv] + 1) % MOD
        dp[p] = p_res

        v_res = 1
        for nv in E[v]:
            v_res = v_res * (dp[nv] + 1) % MOD
        dp[v] = v_res


    ans = [None] * n
    ans[0] = dp[0]
    stack = [(~0, -1), (0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            ans[v] = dp[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    def rerooting(v, p):
        if v == -1 or p == -1:
            return

        # 初めは計算量を無視
        p_res = 1
        for nv in E[p]:
            if nv == v:
                continue
            p_res = p_res * (dp[nv] + 1) % MOD
        dp[p] = p_res

        v_res = 1
        for nv in E[v]:
            v_res = v_res * (dp[nv] + 1) % MOD
        dp[v] = v_res

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n,m=map(int,input().split())
es=[[] for i in range(n)]
for i in range(n-1):
   a,b=map(int,input().split())
   es[a-1].append(b-1)
   es[b-1].append(a-1)
dp={} #dp[(a,b)]=(aからbに保存されている場合の数)
def dfs(v,p):
    if (v,p) in dp:
        return dp[(v,p)]
    res=1
    for i in es[v]:
        if i-p:
            res*=dfs(i,v)
            res%=m
    res=(res+1)%m
    dp[(v,p)]=res
    return res
for p in range(n):
    ans=1
    for v in es[p]:
        ans=(ans*dfs(v,p))%m
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline
sys.setrecursionlimit(1000000)

N,M=map(int,input().split())
edge={i:[] for i in range(1,N+1)}
for _ in range(N-1):
    x,y=map(int,input().split())
    edge[x].append(y)
    edge[y].append(x)

parent={i:-1 for i in range(1,N+1)}
parent[1]=0

q=set([1])
sub=set([])
while q:
    while q:
        x=q.pop()
        for i in edge[x]:
            if parent[i]==-1:
                parent[i]=x
                sub.add(i)

        if not q:
            q=sub
            sub=set([])
            break


memo={i:-1 for i in range(1,N+1)}
def dfs(num):
    if memo[num]!=-1:
        return memo[num]

    if edge[num]==[parent[num]]:
        return 1

    ans=1
    for i in edge[num]:
        if i!=parent[num]:
            ans=(ans*(dfs(i)+1))

    memo[num]=ans

    return memo[num]

answer={i:-1 for i in range(1,N+1)}
answer[1]=dfs(1)

def all(num):
    if answer[num]!=-1:
        return answer[num]

    x=all(parent[num])
    y=dfs(num)

    answer[num]=(x//(y+1)+1)*y

    return answer[num]

for i in range(1,N+1):
    print(all(i)%M)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10 ** 7)

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

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

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

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

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

dfs(1, 0)
# print (DP1)

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

while stack:
    x = stack.pop()
    for next_ in G[x]:
        if DP2[next_] != -1:
            continue
        tmp = 1
        for y in G[x]:
            if y != next_ and y != parent[x]:
                tmp *= (DP1[y] + 1)
                tmp %= MOD
        tmp *= DP2[parent[next_]]
        tmp += 1 #白色の分
        DP2[next_] = tmp % MOD
        stack.append(next_)

# print (DP2)

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

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10 ** 7)

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

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

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

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

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

dfs(1, 0)
# print (DP1)

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

while stack:
    x = stack.pop()
    for next_ in G[x]:
        if DP2[next_] != -1:
            continue
        tmp = DP1[x]
        tmp //= (DP1[next_] + 1)
        tmp *= DP2[parent[next_]]
        tmp += 1 #白色の分
        DP2[next_] = tmp
        stack.append(next_)

# print (DP2)

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

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(10 ** 7)

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

#計算量 log(m)くらい
def modinv(a, m): #mod. m でのaの逆元 a^{-1}を計算する
    b = m
    u = 1
    v = 0
    while b:
        t = a//b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    
    u %= m
    if u < 0:
        u += m
    return u

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

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

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

dfs(1, 0)
# print (DP1)

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

while stack:
    x = stack.pop()
    for next_ in G[x]:
        if DP2[next_] != -1:
            continue
        tmp = DP1[x]
        tmp //= (DP1[next_] + 1)
        tmp *= DP2[parent[next_]]
        tmp += 1 #白色の分
        DP2[next_] = tmp
        stack.append(next_)

# print (DP2)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.buffer.readline()[:-1]

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

dp = [1 for _ in range(n)]
def dfs1(x, p):
	for c in adj[x]:
		if c == p:
			continue
		dfs1(c, x)
		dp[x] *= dp[c]+1
		dp[x] %= m
	return

dfs1(0, -1)
ans = [0 for _ in range(n)]
ans[0] = dp[0]
def dfs2(x, p):
	l = len(adj[x])
	cuml = [1 for _ in range(l+2)]
	cumr = [1 for _ in range(l+2)]
	for i in range(l):
		cuml[i+1] = (cuml[i] * (dp[adj[x][i]] + 1)) % m
	for i in range(l-1, -1, -1):
		cumr[i+1] = (cumr[i+2] * (dp[adj[x][i]] + 1)) % m
	pres_x = dp[x]
	for i, c in enumerate(adj[x]):
		if c == p:
			continue
		pres_c = dp[c]
		dp[x] = (cuml[i] * cumr[i+2]) % m
		dp[c] *= dp[x] + 1
		dp[c] %= m
		ans[c] = dp[c]
		dfs2(c, x)
		dp[x] = pres_x
		dp[c] = pres_c
	return

dfs2(0, -1)
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

def os(): return input()
def oi(): return int(input())
def oli(): return map(int, input().split())
def olai(): return list(map(int, input().split()))
def olas(): return list(input().split())
def mlai(L): return [int(input()) for _ in range(L)]
def mlas(L): return [input() for _ in range(L)]
def ar(a, b, c=-1, d=-1, INIT=0):
    if(c==-1): return [[INIT]*b for _ in range(a)]
    if(d==-1): return [[[INIT]*c for _ in range(b)] for __ in range(a)]
    return [[[[INIT]*d for _ in range(c)] for __ in range(b)] for ___ in range(a)]

n, m = oli()

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス


#零元
zero = 1

#一個上に遷移した時の変化
def step(x):
    return x+1
#マージ
def merge(x, y):
    return (x*y)%m

G = [[] for _ in range(100001)]
down_data = [zero for _ in range(100001)]
dat = [zero for _ in range(100001)]

def dfs(now, parent):
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        cnt += 1
        dfs(to, now)
        down_data[now] = merge(down_data[now], step(down_data[to]))

def dfs_rev(now, parent, rev):
    #累積
    left = []
    right = []
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        if(len(left)==0): left.append(step(down_data[to]))
        else: left.append(merge(left[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    for to in reversed(G[now]):
        if(to==parent): continue
        if(len(right)==0): right.append(step(down_data[to]))
        else: right.append(merge(right[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    dat[now] = merge(rev, down_data[now])

    for to in G[now]:
        if(to==parent): continue
        x = zero if cnt==0 else left[cnt-1]
        y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
        dfs_rev(to, now, step(merge(rev, merge(x, y))))
        cnt += 1

def calc(N):
    root = -1
    for i in range(1, N+1):
        if(len(G[i]) == 1 or len(G[i]) == 0):
            root = i
            break
    dfs(root, -1)
    dfs_rev(root, -1, zero)
#-------------------------------------------------------------------

for i in range(n-1):
    a, b = oli()
    G[a].append(b)
    G[b].append(a)
calc(n)
for i in range(1, n+1):
    print(dat[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

def os(): return input()
def oi(): return int(input())
def oli(): return map(int, input().split())
def olai(): return list(map(int, input().split()))
def olas(): return list(input().split())
def mlai(L): return [int(input()) for _ in range(L)]
def mlas(L): return [input() for _ in range(L)]
def ar(a, b, c=-1, d=-1, INIT=0):
    if(c==-1): return [[INIT]*b for _ in range(a)]
    if(d==-1): return [[[INIT]*c for _ in range(b)] for __ in range(a)]
    return [[[[INIT]*d for _ in range(c)] for __ in range(b)] for ___ in range(a)]

n, m = oli()

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1

    def __init__(self, a):
        self.num = a

#零元
zero = T(1)

#一個上に遷移した時の変化
def step(x):
    return T(x.num+1)
#マージ
def merge(x, y):
    return T((x.num*y.num)%m)

G = [[] for _ in range(100001)]
down_data = [zero for _ in range(100001)]
dat = [zero for _ in range(100001)]

def dfs(now, parent):
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        cnt += 1
        dfs(to, now)
        down_data[now] = merge(down_data[now], step(down_data[to]))

def dfs_rev(now, parent, rev):
    #累積
    left = []
    right = []
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        if(len(left)==0): left.append(step(down_data[to]))
        else: left.append(merge(left[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    for to in reversed(G[now]):
        if(to==parent): continue
        if(len(right)==0): right.append(step(down_data[to]))
        else: right.append(merge(right[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    dat[now] = merge(rev, down_data[now])

    for to in G[now]:
        if(to==parent): continue
        x = zero if cnt==0 else left[cnt-1]
        y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
        dfs_rev(to, now, step(merge(rev, merge(x, y))))
        cnt += 1

def calc(N):
    root = -1
    for i in range(1, N+1):
        if(len(G[i]) == 1 or len(G[i]) == 0):
            root = i
            break
    dfs(root, -1)
    dfs_rev(root, -1, zero)
#-------------------------------------------------------------------

for i in range(n-1):
    a, b = oli()
    G[a].append(b)
    G[b].append(a)
calc(n)
for i in range(1, n+1):
    print(dat[i].num)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(4100000)

def os(): return input()
def oi(): return int(input())
def oli(): return map(int, input().split())
def olai(): return list(map(int, input().split()))
def olas(): return list(input().split())
def mlai(L): return [int(input()) for _ in range(L)]
def mlas(L): return [input() for _ in range(L)]
def ar(a, b, c=-1, d=-1, INIT=0):
    if(c==-1): return [[INIT]*b for _ in range(a)]
    if(d==-1): return [[[INIT]*c for _ in range(b)] for __ in range(a)]
    return [[[[INIT]*d for _ in range(c)] for __ in range(b)] for ___ in range(a)]

n, m = oli()

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1

    def __init__(self, a):
        self.num = a

#零元
zero = T(1)

#一個上に遷移した時の変化
def step(x):
    return T(x.num+1)
#マージ
def merge(x, y):
    return T((x.num*y.num)%m)

G = [[] for _ in range(100001)]
down_data = [zero for _ in range(100001)]
dat = [zero for _ in range(100001)]

def dfs(now, parent):
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        cnt += 1
        dfs(to, now)
        down_data[now] = merge(down_data[now], step(down_data[to]))

def dfs_rev(now, parent, rev):
    #累積
    left = []
    right = []
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        if(len(left)==0): left.append(step(down_data[to]))
        else: left.append(merge(left[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    for to in reversed(G[now]):
        if(to==parent): continue
        if(len(right)==0): right.append(step(down_data[to]))
        else: right.append(merge(right[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    dat[now] = merge(rev, down_data[now])

    for to in G[now]:
        if(to==parent): continue
        x = zero if cnt==0 else left[cnt-1]
        y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
        dfs_rev(to, now, step(merge(rev, merge(x, y))))
        cnt += 1

#-------------------------------------------------------------------
def main():
    for i in range(n-1):
        a, b = oli()
        G[a].append(b)
        G[b].append(a)
    root = -1
    for i in range(1, n+1):
        if(len(G[i]) == 1 or len(G[i]) == 0):
            root = i
            break
    dfs(root, -1)
    dfs_rev(root, -1, zero)
    for i in range(1, n+1):
        print(dat[i].num)

if __name__ == "__main__": main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
sys.setrecursionlimit(4100000)

def os(): return input()
def oi(): return int(input())
def oli(): return map(int, input().split())
def olai(): return list(map(int, input().split()))
def olas(): return list(input().split())
def mlai(L): return [int(input()) for _ in range(L)]
def mlas(L): return [input() for _ in range(L)]
def ar(a, b, c=-1, d=-1, INIT=0):
    if(c==-1): return [[INIT]*b for _ in range(a)]
    if(d==-1): return [[[INIT]*c for _ in range(b)] for __ in range(a)]
    return [[[[INIT]*d for _ in range(c)] for __ in range(b)] for ___ in range(a)]

def lcm(a, b): return (a*b)//gcd(a, b)
#MOD
n, m = oli()
P = m
N = 100001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b or b < 0: return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1

    def __init__(self, a):
        self.num = a

#零元
zero = T(1)

#一個上に遷移した時の変化
def step(x):
    return T(x.num+1)
#マージ
def merge(x, y):
    return T((x.num*y.num)%P)

G = [[] for _ in range(200001)]
down_data = [zero for _ in range(200001)]
dat = [zero for _ in range(200001)]

def dfs(now, parent):
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        cnt += 1
        dfs(to, now)
        down_data[now] = merge(down_data[now], step(down_data[to]))

def dfs_rev(now, parent, rev):
    #累積
    left = []
    right = []
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        if(len(left)==0): left.append(step(down_data[to]))
        else: left.append(merge(left[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    for to in reversed(G[now]):
        if(to==parent): continue
        if(len(right)==0): right.append(step(down_data[to]))
        else: right.append(merge(right[cnt-1], step(down_data[to])))
        cnt += 1
    cnt = 0
    dat[now] = merge(rev, down_data[now])

    for to in G[now]:
        if(to==parent): continue
        x = zero if cnt==0 else left[cnt-1]
        y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
        dfs_rev(to, now, step(merge(rev, merge(x, y))))
        cnt += 1

#-------------------------------------------------------------------
def main():
    for i in range(n-1):
        a, b = oli()
        G[a].append(b)
        G[b].append(a)
    root = -1
    for i in range(1, n+1):
        if(len(G[i]) == 1 or len(G[i]) == 0):
            root = i
            break
    dfs(root, -1)
    dfs_rev(root, -1, zero)
    for i in range(1, n+1):
        print(dat[i].num)

if __name__ == "__main__": main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().strip()
def dfs(r=0,p=-1):
    ans1 = 1
    for c in adj[r]:
        if c==p:
            continue 
        dfs(c,r)
        ans1*=(dp[c]+1)
    dp[r] = ans1 
def dfs1(r=0,p=-1):
    ans[r] = dp[r]
    for c in adj[r]:
        if c==p:
            continue 
        tmp = dp[r]
        tmp1 = dp[c]
        dp[r] = (dp[r]//(dp[c]+1))
        dp[c] = (dp[c]*(dp[r]+1))
        dfs1(c,r)
        dp[r] = tmp 
        dp[c] = tmp1
n,m = map(int,input().split())
ans = [0 for _ in range(n)]
dp = [0 for _ in range(n)]
adj = [[] for _ in range(n)]
for i in range(n-1):
    u,v = map(int,input().split())
    u-=1;v-=1
    adj[u].append(v)
    adj[v].append(u)
dfs()
dfs1()
print('\n'.join(map(lambda x:str(x%m),ans)))