Submission #8271798


Source Code Expand

Copy
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N,MOD = map(int,readline().split())
m = map(int,read().split())
XY = zip(m,m)

mult = lambda x,y: x*y%MOD

graph = [[] for _ in range(N+1)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

# 自身を黒く塗ったときの根側
dp1 = [0]*(N+1)

for v in order[::-1]:
    x = 1
    for w in graph[v]:
        x *= dp1[w]+1
        x %= MOD
    dp1[v] = x

# 親側
dp2 = [1]*(N+1)

for v in order:
    p = parent[v]
    arr = [dp1[c]+1 if c != p else dp2[v] for c in graph[v]]
    # 1元を除く積を取得
    from_left = [1] + list(itertools.accumulate(arr,mult))[:-1]
    from_right = list(itertools.accumulate(reversed(arr),mult))[-2::-1] + [1]
    prod = [x*y%MOD for x,y in zip(from_left,from_right)]
    for c,x in zip(graph[v],prod):
        if c != p:
            dp2[c] = 1+x

answer = '\n'.join(str(x*y%MOD) for x,y in zip(dp1[1:],dp2[1:]))
print(answer)

Submission Info

Submission Time
Task V - Subtree
User maspy
Language Python (3.4.3)
Score 100
Code Size 1300 Byte
Status AC
Exec Time 993 ms
Memory 41420 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 36
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11, 1_12, 1_13, 1_14, 1_15, 1_16, 1_17, 1_18, 1_19, 1_20, 1_21, 1_22, 1_23, 1_24, 1_25, 1_26, 1_27, 1_28, 1_29, 1_30, 1_31
Case Name Status Exec Time Memory
0_00 AC 18 ms 3188 KB
0_01 AC 18 ms 3188 KB
0_02 AC 18 ms 3188 KB
0_03 AC 18 ms 3188 KB
1_00 AC 18 ms 3188 KB
1_01 AC 18 ms 3188 KB
1_02 AC 911 ms 32220 KB
1_03 AC 950 ms 39444 KB
1_04 AC 827 ms 34372 KB
1_05 AC 841 ms 41420 KB
1_06 AC 832 ms 34140 KB
1_07 AC 851 ms 40040 KB
1_08 AC 805 ms 33512 KB
1_09 AC 899 ms 37712 KB
1_10 AC 848 ms 32904 KB
1_11 AC 849 ms 37188 KB
1_12 AC 869 ms 32888 KB
1_13 AC 889 ms 36984 KB
1_14 AC 873 ms 32872 KB
1_15 AC 905 ms 36956 KB
1_16 AC 910 ms 31928 KB
1_17 AC 940 ms 36828 KB
1_18 AC 878 ms 32488 KB
1_19 AC 924 ms 36712 KB
1_20 AC 924 ms 32028 KB
1_21 AC 993 ms 36700 KB
1_22 AC 956 ms 32248 KB
1_23 AC 936 ms 36680 KB
1_24 AC 858 ms 31788 KB
1_25 AC 934 ms 36704 KB
1_26 AC 883 ms 32360 KB
1_27 AC 912 ms 36460 KB
1_28 AC 918 ms 32264 KB
1_29 AC 984 ms 37316 KB
1_30 AC 905 ms 31556 KB
1_31 AC 977 ms 38480 KB