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

vidx = [0]*N
vmull = [None]*N
vmulr = [None]*N
for i in range(N):
    Ci = C[i]
    res = [1]
    for j, c in enumerate(Ci, 1):
        vidx[c] = j
        res.append(res[-1] * (1+dp1[c]) % M)
    vmulr[i] = res + [1]
    res = [1]
    for c in Ci:
        res.append(res[-1] * (1+dp1[c]) % M)
    vmull[i] = [1] + res[::-1]
for l in L[1:]:
    p = P[l]
    pp = P[p]
    vi = vidx[l]
    res = vmulr[p][vi-1] * vmull[p][vi+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: Wrong Answer

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

    fm = [None] * n
    def f(i,p):
        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)
        x = [(pp if u==p else fm[u]) + 1 for u in v]

        if l == 1:
            w[i] = x[0] % m
            return

        z = [None] * l
        t = z[0] = x[0]
        for j in range(1,l):
            t = z[j] = z[j-1] * x[j] % m

        y = [None] * l
        t = y[-1] = x[-1]
        for j in range(l-2,-1,-1):
            t = y[j] = t * x[j] % m

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

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

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

        z = [None] * l
        t = z[0] = x[0]
        for j in range(1,l):
            t = z[j] = t * x[j] % m

        y = [None] * l
        t = y[-1] = x[-1]
        for j in range(l-2,-1,-1):
            t = y[j] = t * x[j] % m

        w[i] = y[0] % m
        g(v[0],i,y[1])
        for j,u in enumerate(v[1:-1]):
            g(u,i,z[j]*y[j+2]%m)
        g(v[-1],i,z[-2])

    h(1)

    return sum(w)
    # return '\n'.join(map(str, w))


print(main())

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

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

N, M = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, readline().split())
    G[x-1].append((y-1, 2*i))
    G[y-1].append((x-1, 2*i+1))
G0 = [None]*N
used = [0]*N
used[0] = 1
que = deque([0])
while que:
    v = que.popleft()
    g = []
    for e in G[v]:
        w, d = e
        if used[w]:
            continue
        g.append(e)
        used[w] = 1
        que.append(w)
    G0[v] = g


memo = [0]*(2*N+1)
def dfs0(v, p, e):
    r = 1
    for w, d in G0[v]:
        r = r * (1 + dfs0(w, v, d)) % M
    memo[e] = r
    return r


lv = [0]*(2*N); rv = [0]*(2*N)
ans = [None]*N
def dfs1(v, p, par):
    s = 1 + par
    for w, d in G0[v]:
        lv[d] = s
        s = s * (1 + memo[d]) % M
    s = 1
    for w, d in reversed(G[v]):
        rv[d] = s
        s = s * (1 + memo[d]) % M
    for w, d in G0[v]:
        memo[d ^ 1] = x = lv[d] * rv[d] % M
        dfs1(w, v, x)


dfs0(0, -1, 2*N)
dfs1(0, -1, 0)
ans = []
for v in range(N):
    r = 1
    for w, d in G[v]:
        r = r * (1 + memo[d]) % M
    ans.append("%d\n" % r)
sys.stdout.writelines(ans)

Submission status: Wrong Answer

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

readline = sys.stdin.readline

N, M = map(int, readline().split())
G = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, readline().split())
    G[x-1].append((y-1, 2*i))
    G[y-1].append((x-1, 2*i+1))

memo = [0]*(2*N+1)
def dfs0(v, p, e):
    r = 1
    for w, d in G[v]:
        if w == p:
            continue
        r = r * (1 + dfs0(w, v, d)) % M
    memo[e] = r
    return r


lv = [0]*(2*N); rv = [0]*(2*N)
ans = [None]*N
def dfs1(v, p, par):
    s = 1 + par
    for w, d in G[v]:
        if w == p:
            continue
        lv[d] = s
        s = s * (1 + memo[d]) % M
    ans[v] = "%d\n" % s
    s = 1
    for w, d in reversed(G[v]):
        if w == p:
            continue
        rv[d] = s
        s = s * (1 + memo[d]) % M
    for w, d in G[v]:
        if w == p:
            continue
        memo[d ^ 1] = x = lv[d] * rv[d] % M
        dfs1(w, v, x)


dfs0(0, -1, 2*N)
dfs1(0, -1, 0)
sys.stdout.writelines(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        ans[v] *= ans[u]+1
    if marker==0:
      stack.pop()
    ans[v]%=M
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  while stack:
    v = stack.pop()
    cum1 = [1]*(len(edge[v])+1)
    cum2 = [1]*(len(edge[v])+1)
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        cum1[i+1] = cum1[i]*(p_value[v]+1)
      else:
        cum1[i+1] = cum1[i]*(ans[u]+1)
      cum1[i+1] %= M
    for i,u in enumerate(edge[v][::-1]):
      if u==parent[v]:
        cum2[-i-2] = cum2[-i-1]*(p_value[v]+1)
      else:
        cum2[-i-2] = cum2[-i-1]*(ans[u]+1)
      cum2[i+1]%=M
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = cum1[i]*cum2[i+1]%M
      ans[u] *= (p_value[u]+1)
      ans[u] %= M
      stack.append(u)
    ans[v] %= M
  return

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

Submission status: Time Limit Exceeded

Solution code:
import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        ans[v] *= ans[u]+1
    if marker==0:
      stack.pop()
    ans[v]%=M
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  while stack:
    v = stack.pop()
    cum1 = [1]*(len(edge[v])+1)
    cum2 = [1]*(len(edge[v])+1)
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        cum1[i+1] = cum1[i]*(p_value[v]+1)
      else:
        cum1[i+1] = cum1[i]*(ans[u]+1)
      cum1[i+1] %= M
    for i,u in enumerate(edge[v][::-1]):
      if u==parent[v]:
        cum2[-i-2] = cum2[-i-1]*(p_value[v]+1)
      else:
        cum2[-i-2] = cum2[-i-1]*(ans[u]+1)
      cum2[i+1]%=M
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = cum1[i]*cum2[i+1]%M
      ans[u] *= (p_value[u]+1)
      ans[u] %= M
      stack.append(u)
    ans[v] %= M
  return

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

Submission status: Time Limit Exceeded

Solution code:
import sys,os,io
# input = sys.stdin.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        ans[v] *= ans[u]+1
    if marker==0:
      stack.pop()
    ans[v]%=M
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  while stack:
    v = stack.pop()
    cum1 = [1]*(len(edge[v])+1)
    cum2 = [1]*(len(edge[v])+1)
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        cum1[i+1] = cum1[i]*(p_value[v]+1)
      else:
        cum1[i+1] = cum1[i]*(ans[u]+1)
      cum1[i+1] %= M
    for i,u in enumerate(edge[v][::-1]):
      if u==parent[v]:
        cum2[-i-2] = cum2[-i-1]*(p_value[v]+1)
      else:
        cum2[-i-2] = cum2[-i-1]*(ans[u]+1)
      cum2[i+1]%=M
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = cum1[i]*cum2[i+1]%M
      ans[u] *= (p_value[u]+1)
      ans[u] %= M
      stack.append(u)
    ans[v] %= M
  return

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

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        ans[v] *= ans[u]+1
    if marker==0:
      stack.pop()
    ans[v]%=M
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  while stack:
    v = stack.pop()
    cum1 = [1]*(len(edge[v])+1)
    cum2 = [1]*(len(edge[v])+1)
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        cum1[i+1] = cum1[i]*(p_value[v]+1)
      else:
        cum1[i+1] = cum1[i]*(ans[u]+1)
      cum1[i+1] %= M
    for i,u in enumerate(edge[v][::-1]):
      if u==parent[v]:
        cum2[-i-2] = cum2[-i-1]*(p_value[v]+1)
      else:
        cum2[-i-2] = cum2[-i-1]*(ans[u]+1)
      cum2[i+1]%=M
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = cum1[i]*cum2[i+1]%M
      ans[u] *= (p_value[u]+1)
      ans[u] %= M
      stack.append(u)
    ans[v] %= M
  return

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

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        ans[v] *= ans[u]+1
    if marker==0:
      stack.pop()
  return ans

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

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

Submission status: Time Limit Exceeded

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

N, M = map(int, input().split())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        ans[v] *= ans[u]+1
    if marker==0:
      stack.pop()
  return ans

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
def dfs(v,p):
    if res_v[v]!=-1:
        return res_v[v]
    size[v]=len(G[v])
    dp[v]=[0]*size[v]
    res=1
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            p_i[v]=i
            continue
        R=dfs(nv,v)
        dp[v][i]=R
        res=res*(R+1)%MOD
    return res
    
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][p_i[v]]=res_p
    for i in range(size[v]):
        ans[v]=ans[v]*(dp[v][i]+1)%MOD
    dp_L=[1]*(size[v]+1)
    dp_R=[1]*(size[v]+1)
    for i in range(size[v]):
        dp_L[i+1]=dp_L[i]*(dp[v][i]+1)%MOD
    for i in reversed(range(size[v])):
        dp_R[i]=dp_R[i+1]*(dp[v][i]+1)%MOD
        
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            continue
        reroot(nv,dp_L[i]*dp_R[i+1]%MOD,v)

N,MOD=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
res_v=[-1]*N
dp=[[] for i in range(N)]
size=[-1]*N
p_i=[-1]*N
dp_L=[[] for i in range(N)]
dp_R=[[] for i in range(N)]
ans=[1]*N

z_root=dfs(0,-1)
res_v[0]=z_root
reroot(0,0,-1)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

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

def dfs(v,p):
    if res_v[v]!=-1:
        return res_v[v]
    size[v]=len(G[v])
    dp[v]=[0]*size[v]
    res=1
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            p_i[v]=i
            continue
        R=dfs(nv,v)
        dp[v][i]=R
        res=res*(R+1)%MOD
    return res
    
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][p_i[v]]=res_p
    for i in range(size[v]):
        ans[v]=ans[v]*(dp[v][i]+1)%MOD
    dp_L=[1]*(size[v]+1)
    dp_R=[1]*(size[v]+1)
    for i in range(size[v]):
        dp_L[i+1]=dp_L[i]*(dp[v][i]+1)%MOD
    for i in reversed(range(size[v])):
        dp_R[i]=dp_R[i+1]*(dp[v][i]+1)%MOD
        
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            continue
        reroot(nv,dp_L[i]*dp_R[i+1]%MOD,v)

N,MOD=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
res_v=[-1]*N
dp=[[] for i in range(N)]
size=[-1]*N
p_i=[-1]*N
dp_L=[[] for i in range(N)]
dp_R=[[] for i in range(N)]
ans=[1]*N

z_root=dfs(0,-1)
res_v[0]=z_root
reroot(0,0,-1)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


n, mod = LI()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

dp = [-1] * n
par = [-1] * n
def f(u):
    ret = 1
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        ret = ret * f(v)
    dp[u] = ret
    if u: return ret + 1

f(0)
ans = [0] * n
ans[0] = dp[0]
par_acc = [1] * n
dp2 = [1] * n
q = deque([0])
while q:
    u = q.pop()
    ans[u] = dp[u] * dp2[u] % mod
    L1 = [1]
    L2 = []
    D = {}
    cnt = 0
    for v in G[u]:
        if par[u] == v:
            continue
        L1 += [dp[v] + 1]
        L2 += [dp[v] + 1]
        D[cnt] = v
        q += [v]
        cnt += 1
    L2 += [1]
    if len(L1) > 2:
        for i in range(len(L1) - 2):
            L1[i + 2] = L1[i + 2] * L1[i + 1] % mod
            L2[-i - 3] = L2[-i - 3] * L2[-i - 2] % mod
    for j in D:
        dp2[D[j]] = (L1[j] * L2[j + 1] * dp2[u] + 1) % mod

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from operator import add, mul
import sys
sys.setrecursionlimit(1000000)


d = defaultdict(list)
N, M = map(int, input().split())
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

q = [1]
parents = [-1]*(N+1)
dp = defaultdict(lambda: defaultdict(int))
ans = [0]*(N+1)
merge = lambda x,y:mul(x, y)
add_root = lambda x:x#+1
e = 1


def dfs1(s):
    v = e
    for t in d[s]:
        if t == parents[s]:
            continue
        parents[t] = s
        v = merge(v, dfs1(t)+1)
    dp[parents[s]][s] = add_root(v)
    return add_root(v)


def dfs2(s):
    q = [(s, e)]
    while q:
        s, dp_p = q.pop()
        par = parents[s]
        for t in d[s]:
            if t == par:
                dp[s][t] = dp_p

        size = len(d[s])
        ac_l = [e] * (size+1)
        ac_r = [e] * (size+1)
        for i, t in enumerate(d[s]):
            ac_l[i+1] = merge(ac_l[i], dp[s][t]+1)%M
        for i, t in enumerate(d[s][::-1]):
            ac_r[size-i-1] = merge(ac_r[size-i], dp[s][t]+1)%M
        ans[s] = add_root(ac_l[size])
        for i, t in enumerate(d[s]):
            if t == par:
                continue
            q.append((t, add_root(merge(ac_l[i], ac_r[i+1])%M)))


dfs1(1)
dfs2(1)
for i in range(1, N+1):
    print(ans[i])

Submission status: Time Limit Exceeded

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

from collections import defaultdict
#from heapq import heappush, heappop
#import numpy as np
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7

debug_indent = 0


def debug(*x):
    global debug_indent
    x = list(x)
    indent = 0
    if x[0].startswith("enter") or x[0][0] == ">":
        indent = 1
    if x[0].startswith("leave") or x[0][0] == "<":
        debug_indent -= 1
    x[0] = "  " * debug_indent + x[0]
    print(*x, file=sys.stderr)
    debug_indent += indent


def solve(N, M, edges):

    cache = {}

    for v in edges:
        if len(edges[v]) == 1:
            cache[(v, edges[v][0])] = (1, 0)

    def visit(parent, self):
        "return (blackroot, whiteroot)"
        cacheindex = (self, parent)
        if cacheindex in cache:
            return cache[cacheindex]

        total = 1
        fw_b = 1  # full white or black
        one_black = 0  # only one black-root

        if parent != 0 and self in precompute:
            totals, fw_bs, one_blacks = precompute[self]
            total = totals[parent]
            fw_b = fw_bs[parent]
            one_black = one_blacks[parent]
        else:
            for child in edges[self]:
                if child == parent:
                    continue
                b, w = visit(self, child)
                total *= (1 + w + b)
                total %= M
                fw_b *= (1 + b)
                fw_b %= M
                one_black += b

        ret_b = ret_w = 0
        # when all child are fill-white, one black-root and one full-white
        ret_b += 1
        # when only one child is black-root and others are full-white
        # both white-root and black-root are OK
        ret_b += one_black
        ret_w += one_black
        # when multiple black-root and no white-root, it should be black
        ret_b += (fw_b - one_black - 1)
        # otherwise there are one or more white-root, it should be white
        ret_w += total - fw_b

        ret_b %= M
        ret_w %= M

        if parent != 0:
            ret = (ret_b, ret_w)
            cache[cacheindex] = ret
            return ret
        else:
            return ret_b

    # precomputed product
    precompute = {}

    def calc_one_out_product(xs):
        n = len(xs)
        head = [0] * (n + 1)
        cur = 1
        for i in range(n):
            cur *= xs[i]
            head[i] = cur
        head[-1] = 1

        tail = [0] * (n + 1)
        cur = 1
        for i in range(n - 1, -1, -1):
            cur *= xs[i]
            tail[i] = cur
        tail[-1] = 1

        one_out_product = [head[i - 1] * tail[i + 1] for i in range(n)]
        return one_out_product

    for v in edges:
        n = len(edges[v])
        if n > 600:
            tmp_ret = [visit(v2, v) for v2 in edges[v]]
            _totals = calc_one_out_product([1 + b + w for b, w in tmp_ret])
            _fw_bs = calc_one_out_product([1 + b for b, w in tmp_ret])
            s = sum([b for b, w in tmp_ret])

            # change domain from i to v
            totals = [0] * (N + 1)
            fw_bs = [0] * (N + 1)
            one_blacks = [s] * (N + 1)
            for i, v2 in enumerate(edges[v]):
                totals[v2] = _totals[i]
                fw_bs[v2] = _fw_bs[i]
                one_blacks[v2] -= tmp_ret[i][0]
            precompute[v] = (totals, fw_bs, one_blacks)

    ret = [visit(0, i + 1) % M for i in range(N)]
    return ret


def main():
    # parse input
    N, M = map(int, input().split())
    edges = defaultdict(list)
    for i in range(N - 1):
        x, y = map(int, input().split())
        edges[x].append(y)
        edges[y].append(x)

    #print(*solve(N, M, edges), sep="\n")
    for x in solve(N, M, edges):
        print(x)


# tests
T1 = """
3 100
1 2
2 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    3
    4
    3
    """


T2 = """
4 100
1 2
1 3
1 4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    8
    5
    5
    5
    """


T3 = """
1 100
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1
    """


T4 = """
10 2
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    0
    0
    1
    1
    1
    0
    1
    0
    1
    1
    """


# def test_T5():
#     """
#     >>> edges = defaultdict(list)
#     >>> for i in range(100000 - 1):
#     ...     edges[i + 1].append(i + 2)
#     ...     edges[i + 2].append(i + 1)
#     >>> solve(100000, 5, edges)
#     """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()