Submission #2711528

---

Source Code Expand

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
A = [None]*(N+1)
PP = [1]*(N+1)
for i in range(N):
    PP[i+1] = PP[i]*2 % MOD

for i in range(N, -1, -1):

    # 子ノードのdequeを集める
    R = None
    for j in G[i]:
        S = Q[j]
        if not S:
            continue
        if not R:
            R = S
            S[:] = ([a+c,b,0,d] for a, b, c, d in S)
            continue

        T = S if len(R) < len(S) else R
        # dequeの小さい方から大きい方へマージする処理
        def gen():
            for s, r in zip(S, R):
                a0, a1, a2, c0 = s
                b0, b1, b2, c1 = r
                a0 += a2
                yield a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, (a0*b2 + a1*b1 + a1*b2) % MOD, c0+c1
        T[:min(len(R), len(S))] = gen()
        R = T

    k = len(G[i])
    if k:
        r = [(PP[k] - k, k, 0, k)]
    else:
        r = None
    if R:
        # a0 <- a2
        r.extend(R)
    Q[i] = r
ans = PP[N]
for a0, a1, a2, c in Q[0]:
    ans += PP[N+1-c] * a1 % MOD
print(ans % MOD)

Submission Info

Judge Result