Submission #2711501

---

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 R:
            R = S
            continue

        # |R| > |S|
        if len(R) < len(S):
            R, S = S, R

        # dequeの小さい方から大きい方へマージする処理
        for s, r in zip(S, R):
            a0, a1, a2, c0 = s
            b0, b1, b2, c1 = r
            r[0] = a0*b0 % MOD
            r[1] = (a0*b1 + a1*b0) % MOD
            r[2] = (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD
            r[3] = c0+c1

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

Submission Info

Judge Result