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: Runtime Error

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 = [-1]*n 
ans = [0]*n

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

def bfs(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
        bfs(vc, accl[i]*accr[i+1]%MOD, v)

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

Submission status: Runtime Error

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 i 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 = [-1]*n 
ans = [0]*n

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

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

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

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

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

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

Submission status: Runtime Error

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 i 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 = [-1]*n 
ans = [0]*n

def dfs(v, p):
    """葉の場合（必要なら）"""
#    if p >= 0 and len(to[v]) == 1: 
#        return 1

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

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

    dpl = [1]*(deg+1)
    for i in range(deg):
        dpl[i+1] = dpl[i]*(dp[v][i]+1)%MOD

    dpr = [1]*(deg+1)
    for i in range(deg-1,-1,-1):
        dpr[i] = dpr[i+1]*(dp[v][i]+1)%MOD

    ans[v] = dpr[0]
    
    for child in to[v]:
        if child == p: continue
        bfs(child, dpl[i]*dpr[i+1]%MOD, v)

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

Submission status: Runtime Error

Solution code:
import sys

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


def cnt1(i, oya_i=0):
    if len(pair[i]) == 1 and oya_i:
        memo[i][oya_i] = 1
        return 1

    if memo[i][oya_i] != -1:
        return memo[i][oya_i]

    re = 1
    for ko_i in pair[i]:
        if ko_i == oya_i: continue
        re *= (cnt1(ko_i, i) + 1)
    memo[i][oya_i] = re = re % m
    return re


def cnt2(i, ko_i=0, cnt_ko=-1):
    if cnt_ko != -1:
        memo[ko_i][i] = cnt_ko

    oyas = pair[i]
    oya_n = len(oyas)
    ruisekiL = [1] * (oya_n)
    ruisekiR = [1] * (oya_n)
    for k in range(1, oya_n):
        ruisekiL[k] = ruisekiL[k - 1] * (memo[oyas[k - 1]][i] + 1) % m
        ruisekiR[-k - 1] = ruisekiR[-k] * (memo[oyas[-k]][i] + 1) % m

    ans[i] = ruisekiL[-1] * (memo[oyas[-1]][i] + 1) % m

    for k, oya_i in enumerate(oyas):
        if oya_i == ko_i: continue
        cnt2(oya_i, i, ruisekiL[k] * ruisekiR[k] % m)


n, m = map(int, input().split())
memo = [[-1] * (n + 1) for _ in range(n + 1)]
pair = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    pair[x] += [y]
    pair[y] += [x]
ans = [0] * (n + 1)

cnt1(1)
cnt2(1)

print(*ans[1:], sep="\n")

Submission status: Runtime Error

Solution code:
import sys

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


def cnt1(i, oya_i=0):
    if len(pair[i]) == 1 and oya_i:
        memo[i][oya_i] = 1
        return 1

    if memo[i][oya_i] != 0:
        return memo[i][oya_i]

    re = 1
    for ko_i in pair[i]:
        if ko_i == oya_i: continue
        re *= (cnt1(ko_i, i) + 1)
    memo[i][oya_i] = re = re % m
    return re


def cnt2(i, ko_i=0, cnt_ko=-1):
    if cnt_ko != -1:
        memo[ko_i][i] = cnt_ko

    oya_n = len(pair[i])
    ruisekiL = [1] * (oya_n)
    ruisekiR = [1] * (oya_n)
    for k in range(1, oya_n):
        ruisekiL[k] = ruisekiL[k - 1] * (memo[pair[i][k - 1]][i] + 1) % m
        ruisekiR[-k - 1] = ruisekiR[-k] * (memo[pair[i][-k]][i] + 1) % m

    ans[i] = ruisekiL[-1] * (memo[pair[i][-1]][i] + 1) % m

    for k, oya_i in enumerate(pair[i]):
        if oya_i == ko_i: continue
        cnt2(oya_i, i, ruisekiL[k] * ruisekiR[k] % m)


n, m = map(int, input().split())
memo = [[0] * (n + 1) for _ in range(n + 1)]
pair = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    pair[x] += [y]
    pair[y] += [x]
ans = [0] * (n + 1)

cnt1(1)
cnt2(1)

print(*ans[1:],sep="\n")

Submission status: Runtime Error

Solution code:


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: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline

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

#N=10**5
#mod=10**8
#import random
#EDGE=[[i,random.randint(1,i-1)] for i in range(2,N+1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

QUE=deque()
DPDICT=dict()

for i in range(1,N+1):
    if len(EDGELIST[i])==1:
        #DPDICT[(i,EDGELIST[i][0])]=2
        QUE.append(i)


def SCORE(point):
    ANS=1
    for to in EDGELIST[point]:
        ANS=ANS*DPDICT[(to,point)]%mod
    return ANS

def dp(x,y):
    if DPDICT.get((x,y))!=None:
        return DPDICT[(x,y)]

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

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

while QUE:
    x=QUE.pop()
    for to in EDGELIST[x]:
        if DPDICT.get((x,to))==None:
            dp(x,to)
            QUE.append(to)


for i in range(1,N+1):
    print(SCORE(i))

Submission status: Runtime Error

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

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

#N=10**5
#mod=10**8
#import random
#EDGE=[[i,random.randint(1,i-1)] for i in range(2,N+1)]

EDGELIST=[[] for i in range(N+1)]
DPDICT=dict()

for x,y in EDGE:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

for i in range(1,N+1):
    if len(EDGELIST)==1:
        DPDICT[(i,EDGELIST[i][0])]=2    


def SCORE(point):
    ANS=1
    for to in EDGELIST[point]:
        ANS=ANS*dp(to,point)%mod
    return ANS

def dp(x,y):
    if DPDICT.get((x,y))!=None:
        return DPDICT[(x,y)]

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

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

for i in range(1,N+1):
    print(SCORE(i))

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,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 [int(x) for x in sys.stdin.readline().split()]
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
    tt = [None] * n

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

        ta = []
        for c in e[i]:
            ta.append(f(c,i,-1) + 1)
        l = len(e[i])
        if l == 1:
            tt[i] = [1]
            rr[i] = ta[0] % m
            if pp is None:
                f(e[i][0],None,i)
            return 0

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

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

        ei = e[i]
        ca = {}
        ca[ei[0]] = ba[1]
        for ej,j in zip(ei[1:-1],range(l-2)):
            ca[ej] = aa[j] * ba[j+2] % m
        ca[ei[-1]] = aa[-2]
        tt[i] = ca
        rr[i] = ba[0] % m
        for c in e[i]:
            if c != pp:
                f(c,None,i)
        return 0

    f(0,None,None)

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



print(main())

Submission status: Runtime Error

Solution code:
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
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
G = G0

memo = [0]*(2*N+1)
def dfs0(v, p, e):
    r = 1
    for w, d in G[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 G[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 G[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)