Submission #9215355


Source Code Expand

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

N = int(readline())
m = map(int,read().split())
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

# 部分木の大きさ
answer = 0
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
    answer += E

answer *= power_inv[1]
answer %= MOD
print(answer)

Submission Info

Submission Time
Task F - Surrounded Nodes
User maspy
Language Python (3.4.3)
Score 600
Code Size 1263 Byte
Status AC
Exec Time 1309 ms
Memory 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