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

#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: 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)]

#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: Time Limit Exceeded

Solution code:
import sys
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)]

#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: Time Limit Exceeded

Solution code:
import sys
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)]

#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: Time Limit Exceeded

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

    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):
        l = len(e[i])
        v = e[i]
        ta = [(pp if u==p else (fm[u] if not fm[u] is None 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 = [(fm[u] if not fm[u] is None else 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 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

    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):
        if not rr[i] is None:
            return
        l = len(e[i])
        v = e[i]
        ta = [(pp if u==p else (fm[u] if not fm[u] is None else f(u,i))) + 1 for u in v]

        if l == 1:
            rr[i] = ta[0] % m
            if pp is None:
                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])

    g(0,None,None)


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



print(main())

Submission status: Time Limit Exceeded

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

    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):
        l = len(e[i])
        v = e[i]
        ta = [(pp if u==p else (fm[u] if not fm[u] is None else f(u,i))) + 1 for u in v]

        if l == 1:
            rr[i] = ta[0] % m
            if pp is None:
                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

        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])
        rr[i] = ba[0] % m

    g(0,None,None)


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



print(main())

Submission status: Time Limit Exceeded

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

    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

    for c in e[0]:
        f(c,0)

    def g(i,p,pp):
        ta = []
        for c in e[i]:
            if c == p:
                ta.append(pp+1)
            else:
                ta.append(f(c,i) + 1)

        l = len(e[i])
        if l == 1:
            e0 = e[i][0]
            rr[i] = ta[0] % m
            if pp is None:
                g(e0,i,1)
            return

        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 = {}
        if ei[0] != p:
            g(ei[0],i,ba[1])
        for ej,j in zip(ei[1:-1],range(l-2)):
            if ej != p:
                g(ej,i,aa[j]*ba[j+2]%m)
        if ei[-1] != p:
            g(ei[-1],i,aa[-2])
        rr[i] = ba[0] % m
        return

    g(0,None,None)


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



print(main())

Submission status: Time Limit Exceeded

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):
        if i in fm:
            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

    for c in e[0]:
        f(c,0)

    def g(i,p,pp):
        ta = []
        for c in e[i]:
            if c == p:
                ta.append(pp+1)
            else:
                ta.append(f(c,i) + 1)

        l = len(e[i])
        if l == 1:
            e0 = e[i][0]
            rr[i] = ta[0] % m
            if pp is None:
                g(e0,i,1)
            return

        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 = {}
        if ei[0] != p:
            g(ei[0],i,ba[1])
        for ej,j in zip(ei[1:-1],range(l-2)):
            if ej != p:
                g(ej,i,aa[j]*ba[j+2]%m)
        if ei[-1] != p:
            g(ei[-1],i,aa[-2])
        rr[i] = ba[0] % m
        return

    g(0,None,None)


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



print(main())

Submission status: Time Limit Exceeded

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] = {}
            e0 = e[i][0]
            tt[i][e0] = 1
            rr[i] = ta[0] % m
            if pp is None:
                f(e0,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: Time Limit Exceeded

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):
        k = (i,p)
        if k in fm:
            return fm[k]
        if not p is None:
            if not tt[i] is None:
                ind = e[i].index(p)
                return tt[i][ind]
            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) % m)
        l = len(e[i])
        if l == 1:
            tt[i] = [1]
            rr[i] = ta[0]
            for c in e[i]:
                if c == pp:
                    continue
                f(c,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

        ca = [ba[1]]
        for j in range(1,l-1):
            ca.append(aa[j-1]*ba[j+1]%m)
        ca.append(aa[-2])
        tt[i] = ca
        rr[i] = ba[0]
        fm[k] = ba[0]
        for c in e[i]:
            if c == pp:
                continue
            f(c,None,i)
        return 0

    f(0,None,-1)

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



print(main())

Submission status: Time Limit Exceeded

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):
        k = (i,p)
        # print(k)
        if k in fm:
            return fm[k]
        if not p is None:
            if not tt[i] is None:
                el = len(e[i])
                if el == 1:
                    return 1
                ind = e[i].index(p)
                tti = tt[i]
                if ind == 0:
                    return tti[1][1]
                if ind == el - 1:
                    return tti[0][-2]
                return tti[0][ind-1] * tti[1][ind+1] % m
            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])
        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

        tt[i] = [aa, ba]
        rr[i] = ba[0] % m
        for c in e[i]:
            if c == pp:
                continue
            f(c,None,i)
        return rr[i]

    f(0,None,-1)

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



print(main())

Submission status: Time Limit Exceeded

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):
        k = (i,p)
        # print(k)
        if k in fm:
            return fm[k]
        if p != -1:
            if not tt[i] is None:
                if len(e[i]) == 1:
                    return 1
                ind = e[i].index(p)
                tti = tt[i]
                if ind == 0:
                    return tti[1][1]
                if ind == len(e[i]) - 1:
                    return tti[0][-2]
                return tti[0][ind-1] * tti[1][ind+1] % m
            r = 1
            for c in e[i]:
                if c == p:
                    continue
                t = f(c,i)
                r *= t + 1
                r %= m
            fm[k] = r
            return r
        ta = []
        for c in e[i]:
            t = f(c,i)
            # print('t',t,c,i)
            # print(fm)
            ta.append(t + 1)
        l = len(e[i])
        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

        tt[i] = [aa, ba]
        rr[i] = aa[-1] % m
        fm[k] = aa[-1] % m
        for c in e[i]:
            f(c,-1)
        return aa[-1] % m

    f(0,-1)

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



print(main())

Submission status: Time Limit Exceeded

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(G0[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: Time Limit Exceeded

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

Solution code:
'''
N頂点の木があり、i番目の辺は頂点x_iとy_iを結んでいる。
各頂点を白または黒で塗り、どの黒い頂点からどの黒い頂点へも黒い頂点のみをたどって到達できる時、
頂点vが黒であるような頂点の色の組み合わせは何通りか？Mで割ったあまりを求めよ。
graph_i
input:
3 100
1 2
2 3
output:
    3
    4
    3

'''
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


# endregion

# setting
unit = 1  # 単位元


def merge(a, b):
    # モノイド演算
    return a * b % M


def adj_bu(a, i):
    # bottom up DP
    return a + 1


def adj_td(a, i, p):
    # top down DP
    return a + 1


def adj_fin(a, i):
    # 最終結果
    return a
#####


n, M = inpl()
graph = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = inpl()
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)
parent = [-1] * n
root = 0  # 0を根とする
queue = collections.deque([root])
sorted_graph = []  # トポロジカルソート

# トポロジカルソート
while queue:
    i = queue.popleft()
    sorted_graph.append(i)
    for a in graph[i]:
        if a != parent[i]:
            parent[a] = i
            graph[a].remove(i)  # graph：隣接リストから子リストにする
            queue.append(a)

# Bottom up DP

BU = [unit] * n  # acc[i]と対応
res = [0] * n
for i in sorted_graph[1:][::-1]:
    res[i] = adj_bu(BU[i], i)
    p = parent[i]
    BU[p] = merge(BU[p], res[i])
res[sorted_graph[0]] = adj_fin(BU[sorted_graph[0]], sorted_graph[0])  # 根だけ別で


# Top down DP

TD = [unit] * n
for i in sorted_graph:
    # 左からDP
    tmp = TD[i]
    for j in graph[i]:
        TD[j] = tmp
        tmp = merge(tmp, res[j])
    # 右からDP
    tmp = unit
    for j in graph[i][::-1]:
        TD[j] = adj_td(merge(TD[j], tmp), j, i)
        tmp = merge(tmp, res[j])
        res[j] = adj_fin(merge(BU[j], TD[j]), j)
print(*res, sep="\n")
'''
各頂点に対して結果を出力するので全方位木を考える。
全方位木では子→親の木DPと親→子の木DPを使う。
acc[i][p]:ノードiにおける親pを除いた全方向からの累積
res[i][p]:acc[i][p]に調整を加えたもの
acc[i]:ノードiにおけるすべての方向からの集約
'''

Submission status: Accepted

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
        ans[v] %=M
    if marker==0:
      stack.pop()
  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)%M
      else:
        cum1[i+1] = cum1[i]*(ans[u]+1)%M
    for i,u in enumerate(edge[v][::-1]):
      if u==parent[v]:
        cum2[-i-2] = cum2[-i-1]*(p_value[v]+1)%M
      else:
        cum2[-i-2] = cum2[-i-1]*(ans[u]+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')