Contest Duration: - (local time) (300 minutes)

Submission #8271798

Source Code Expand

Copy
```import sys

import itertools

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

#### Submission Info

Submission Time 2019-11-03 22:23:01+0900 V - Subtree maspy Python (3.4.3) 100 1300 Byte AC 993 ms 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