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 .

Solution (Python):
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())

Solution (Python):


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)


cola = [(0, -1)]
qind = 0
while qind < len(cola):
    u, pu = cola[qind]
    qind += 1
    for v in tree[u]:
        if v != pu:
            cola.append((v, u))

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

resp = [0] * n
pval = [1] * n
for j in range(n):
    u, pu = cola[j]
    resp[u] = (dp[u] * pval[u]) % 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[u]
    for i in range(len(chlds)):
        v = chlds[i]
        pval[v] = (1 + pref * cumulr[i]) % MOD
        pref *= (dp[v] + 1)
        pref %= MOD

for i in range(n):
    print(resp[i])

Solution (Python):
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])

Solution (Python):
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 _ in range(n)]
dp = [0 for _ in range(n)]
pre_muls = [None for _ 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)))

Solution (Python):
import sys
from collections import deque

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
V = [(0, -1)]
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)
        V.append(e)
        used[w] = 1
        que.append(w)
    G0[v] = g

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

lv = [0]*(2*N); rv = [0]*(2*N)
for v, e in V:
    s = 1 + memo[e ^ 1]
    for w, d in G0[v]:
        lv[d] = s
        s = s * (1 + memo[d]) % M
    s = 1
    for w, d in reversed(G0[v]):
        rv[d] = s
        s = s * (1 + memo[d]) % M
    for w, d in G0[v]:
        memo[d ^ 1] = lv[d] * rv[d] % M

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)