Contest Duration: - (local time) (100 minutes) Back to Home

Submission #9215355

Source Code Expand

Copy
```import sys

AB = zip(m,m)

MOD = 10 ** 9 + 7

graph = [[] for _ in range(N+1)]
for a,b in AB:
graph[a].append(b)
graph[b].append(a)

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)

# (1/2)^n
x = (MOD + 1) // 2
power = [1] * (N+100)
power_inv = [1] * (N+100)
for i in range(1,N+100):
power[i] = power[i-1] * 2 % MOD
power_inv[i] = power_inv[i-1] * x % MOD

# 部分木の大きさ
size = [1] * (N+1)
for v in order[::-1]:
p = parent[v]
size[p] += size[v]
A = [size[w] for w in graph[v] if w != p] # 部分木のサイズ集合
if v != root:
A.append(N - 1 - sum(A))
if len(A) == 1:
continue
prod = 1
coef = 1
for x in A:
prod *= power_inv[x]
prod %= MOD
coef += (power[x] - 1)
E = 1 - prod * coef % MOD

#### Submission Info

Submission Time 2019-12-29 20:21:11+0900 F - Surrounded Nodes maspy Python (3.4.3) 600 1263 Byte AC 1309 ms 67344 KB

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
 AC × 4
 AC × 30
Set Name Test Cases
Sample sample_01, sample_02, sample_03, sample_04
All min_01, path1_01, path1_02, path1_03, path2_01, path2_02, path2_03, random_01, random_02, random_03, random_04, random_05, random_06, random_07, random_08, random_09, random_10, random_11, random_12, random_13, sample_01, sample_02, sample_03, sample_04, star1_01, star1_02, star1_03, star2_01, star2_02, star2_03
Case Name Status Exec Time Memory
min_01 AC 17 ms 3188 KB
path1_01 AC 1196 ms 61752 KB
path1_02 AC 1270 ms 65264 KB
path1_03 AC 1041 ms 56436 KB
path2_01 AC 1309 ms 67336 KB
path2_02 AC 1294 ms 67344 KB
path2_03 AC 1298 ms 67336 KB
random_01 AC 81 ms 7240 KB
random_02 AC 73 ms 6860 KB
random_03 AC 26 ms 3572 KB
random_04 AC 54 ms 5616 KB
random_05 AC 30 ms 3956 KB
random_06 AC 872 ms 48200 KB
random_07 AC 833 ms 46912 KB
random_08 AC 963 ms 52536 KB
random_09 AC 1172 ms 59552 KB
random_10 AC 675 ms 37956 KB
random_11 AC 1182 ms 61968 KB
random_12 AC 1173 ms 61968 KB
random_13 AC 1167 ms 61968 KB
sample_01 AC 17 ms 3188 KB
sample_02 AC 17 ms 3188 KB
sample_03 AC 17 ms 3188 KB
sample_04 AC 17 ms 3064 KB
star1_01 AC 803 ms 58416 KB
star1_02 AC 485 ms 35892 KB
star1_03 AC 512 ms 36240 KB
star2_01 AC 600 ms 41444 KB
star2_02 AC 897 ms 57968 KB
star2_03 AC 848 ms 56112 KB