Problem:


Score : 1000 points

Problem Statement

Snuke has a rooted tree with N+1 vertices.
The vertices are numbered 0 through N, and Vertex 0 is the root of the tree.
The parent of Vertex i (1 \leq i \leq N) is Vertex p_i.

Besides this tree, Snuke also has an box which is initially empty and many marbles, and playing with them.
The play begins with placing one marble on some of the vertices, then proceeds as follows:

If there is a marble on Vertex 0, move the marble into the box.

Move each marble from the vertex to its parent (all at once).

For each vertex occupied by two or more marbles, remove all the marbles from the vertex.

If there exists a vertex with some marbles, go to Step 1. Otherwise, end the play.

There are 2^{N+1} ways to place marbles on some of the vertices.
For each of them, find the number of marbles that will be in the box at the end of the play, and compute the sum of all those numbers modulo 1,000,000,007.

Constraints

1 \leq N < 2 \times 10^{5}

0 \leq p_i < i

Partial Scores

In the test set worth 400 points, N < 2{,}000.

Input

Input is given from Standard Input in the following format:

N
p_1 p_2 ... p_{N}

Output

Print the answer.

Sample Input 1

2
0 0

Sample Output 1

8

When we place a marble on both Vertex 1 and 2, there will be multiple marbles on Vertex 0 by step 2. In such a case, these marbles will be removed instead of being moved to the box.

Sample Input 2

5
0 1 1 0 4

Sample Output 2

96

Sample Input 3

31
0 1 0 2 4 0 4 1 6 4 3 9 7 3 7 2 15 6 12 10 12 16 5 3 20 1 25 20 23 24 23

Sample Output 3

730395550

Be sure to compute the sum modulo 1,000,000,007.



Sample input:
2
0 0


Sample output:
8

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

M = 10 ** 9 + 7
F = []
num_children = []
series = []

def solve(N, p):
    global c

    series = [None] * (N + 1)
    num_children = [0] * (N + 1)
    for i in range(1, N + 1):
        num_children[p[i]] += 1

    ans = 0
    for i in range(N, -1, -1):
        if num_children[i] == 0:
            continue
        ns = [(num_children[i], num_children[i])]
        if series[i] is not None:
            t_max = max([len(s) for s in series[i]])
            for t in range(t_max):
                u = []
                for s in series[i]:
                    if t < len(s):
                        u.append(s[t])
                count = 0
                perms = 0
                for j in range(len(u)):
                    count += u[j][0]
                    q = u[j][1]
                    for k in range(len(u)):
                        if j != k:
                            q *= (F[u[k][0]] - u[k][1])
                            q %= M
                    perms += q
                ns.append((count, perms))
        if i != 0:
            if series[p[i]] is None:
                series[p[i]] = []
            series[p[i]].append(ns)
        else:
            ans = F[N]
            for v in ns:
                r = F[N + 1 - v[0]] * v[1]
                ans += r
                ans %= M

    return ans


def main():
    global F

    N = int(input())
    p = list(map(int, input().split()))
    p = [-1] + p

    x = 1
    for i in range(N + 2):
        F.append(x)
        x *= 2
        x %= M


    print(solve(N, p))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

M = 10 ** 9 + 7
F = []
num_children = []
series = []

def solve(N, p):
    global c

    series = [None] * (N + 1)
    num_children = [0] * (N + 1)
    for i in range(1, N + 1):
        num_children[p[i]] += 1

    ans = 0
    for i in range(N, -1, -1):
        ns = [(1, 1)]
        if num_children[i] != 0:
            t_max = max([len(s) for s in series[i]])
            for t in range(t_max):
                u = []
                for s in series[i]:
                    if t < len(s):
                        u.append(s[t])
                count = 0
                perms = 0
                for j in range(len(u)):
                    count += u[j][0]
                    q = u[j][1]
                    for k in range(len(u)):
                        if j != k:
                            q *= (F[u[k][0]] - u[k][1])
                            q %= M
                    perms += q
                ns.append((count, perms))
        if i != 0:
            if series[p[i]] is None:
                series[p[i]] = []
            series[p[i]].append(ns)
        else:
            for v in ns:
                r = F[N + 1 - v[0]] * v[1]
                ans += r
                ans %= M

    return ans


def main():
    global F

    N = int(input())
    p = list(map(int, input().split()))
    p = [-1] + p

    x = 1
    for i in range(N + 2):
        F.append(x)
        x *= 2
        x %= M


    print(solve(N, p))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 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)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    for j in g[1:]:
        S = Q[j]
        if not S:
            break

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

    # a0 <- a2
    for r in R:
        r[0] += r[2]
        r[2] = 0
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 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)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=L.__getitem__, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    R = Q[g0]
    for j in g[1:]:
        S = Q[j]
        if not S:
            break

        # dequeの小さい方から大きい方へマージする処理
        for (a0, a1, a2), r in zip(S, R):
            b0, b1, b2 = 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

    # a0 <- a2
    for r in R:
        r[0] += r[2]
        r[2] = 0
    R.appendleft(e)
    Q[i] = R
ans = pp(N)
for (a0, a1, a2), c in zip(Q[0], C[1:]):
    ans += pp(N+1-c) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 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)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
L = [1]*(N+1)

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

    g = G[i]
    if not g:
        Q[i] = deque()
        continue

    # 子ノードのdequeを集める
    g.sort(key=L.__getitem__, reverse=1)
    k = len(g)
    if k not in PP:
        PP[k] = pow(2, k, MOD)
    e = [PP[k] - k, k, 0]

    g0 = g[0]
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    L[i] = L[g0] + 1
    R = Q[g0]
    for j in g[1:]:
        S = Q[j]

        # dequeの小さい方から大きい方へマージする処理
        for (a0, a1, a2), r in zip(S, R):
            b0, b1, b2 = 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

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

Submission status: Time Limit Exceeded

Solution code:
# 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)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = [1]*(N+1)
for i in range(N):
    PP[i+1] = PP[i]*2 % MOD
L = [1]*(N+1)

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

    g = G[i]
    if not g:
        Q[i] = deque()
        continue

    # 子ノードのdequeを集める
    g.sort(key=L.__getitem__, reverse=1)
    k = len(g)
    e = [PP[k] - k, k, 0]

    g0 = g[0]
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    L[i] = L[g0] + 1
    R = Q[g0]
    for j in g[1:]:
        S = Q[j]

        # dequeの小さい方から大きい方へマージする処理
        for (a0, a1, a2), r in zip(S, R):
            b0, b1, b2 = 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

    # a0 <- a2
    for r in R:
        r[0] += r[2]
        r[2] = 0
    R.appendleft(e)
    Q[i] = R
ans = PP[N]
for (a0, a1, a2), c in zip(Q[0], C[1:]):
    ans += PP[N+1-c] * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 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 status: Time Limit Exceeded

Solution code:
# 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)
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 = [[pow(2, k, MOD) - k, k, 0, k]]
    else:
        r = []
    if R:
        # a0 <- a2
        for e in R:
            e[0] += e[2]
            e[2] = 0
        r.extend(R)
        Q[i] = r
    else:
        Q[i] = r
ans = pow(2, N, MOD)
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
import sys
sys.setrecursionlimit(10**6)
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7
from itertools import tee

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
E = [1, 1, 0, 1]
def gen(i):
    *I, = map(Q.__getitem__, G[i])
    k = len(G[i])
    r = 1, k, pow(2, k, MOD) - k - 1, k
    while r:
        a,b,c,d=r
        yield (a+c,b,0,d)
        r = None
        for it in I:
            s = next(it, None)
            if s:
                if r:
                    a0, a1, a2, c0 = s
                    b0, b1, b2, c1 = r
                    r = a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, ((a0 + a1)*b2 + a1*b1) % MOD, c0+c1
                else:
                    r = s
*Q, = map(gen, range(N+1))
ans = pow(2, N, MOD)
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
import sys
sys.setrecursionlimit(10**6)
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7
from itertools import tee

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
E = [1, 1, 0, 1]
for i in range(N, -1, -1):
    def gen(i):
        *I, = map(Q.__getitem__, G[i])
        r = E
        while r:
            a,b,c,d=r
            yield (a+c,b,0,d)
            r = None
            for it in I:
                s = next(it, None)
                if s:
                    if r:
                        a0, a1, a2, c0 = s
                        b0, b1, b2, c1 = r
                        r = a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, ((a0 + a1)*b2 + a1*b1) % MOD, c0+c1
                    else:
                        r = s
    Q[i] = gen(i)
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# seishin.py
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)
for i in range(N, -1, -1):

    # 子ノードのqueを集める
    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

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

        Q[i] = [[1, 1, 0, 1]] + R
    else:
        Q[i] = [[1, 1, 0, 1]]
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 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)
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
    if R:
        # a0 <- a2
        for e in R:
            e[0] += e[2]
            e[2] = 0
        R.appendleft([1, 1, 0, 1])
        Q[i] = R
    else:
        Q[i] = deque([[1, 1, 0, 1]])
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 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)
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
    if R:
        # a0 <- a2
        for e in R:
            e[0] += e[2]
            e[2] = 0
        R.appendleft([1, 1, 0, 1])
        Q[i] = R
    else:
        Q[i] = deque([[1, 1, 0, 1]])
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 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)
for i in range(N, -1, -1):
    # i+1 <- P[i]
    Q[i] = q = deque([[1, 1, 0, 1]])

    # 子ノードのdequeを集める
    R = []
    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 k in range(len(S)):
            a0, a1, a2, c0 = S.popleft()
            b0, b1, b2, c1 = R[k]
            R[k] = [a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD, c0+c1]
    # a0 <- a2
    for e in R:
        e[0] += e[2]
        e[2] = 0
    q.extend(R)
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 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)
for i in range(N, -1, -1):
    # i+1 <- P[i]
    Q[i] = q = deque([[1, 1, 0, 1]])

    # 子ノードのdequeを集める
    R = []
    for j in G[i]:
        R.append(Q[j])

    if R:
        R.sort(key=len, reverse=1)

        # dequeの小さい方から大きい方へマージする処理
        last = R.pop()
        while R:
            nxt = R.pop()
            for k in range(len(last)):
                a0, a1, a2, c0 = last.popleft()
                b0, b1, b2, c1 = nxt[k]
                nxt[k] = [a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD, c0+c1]
            last = nxt
        # a0 <- a2
        for e in last:
            e[0] += e[2]
            e[2] = 0
        q.extend(last)
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# 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)
for i in range(N, -1, -1):
    # i+1 <- P[i]
    Q[i] = q = deque([[1, 1, 0, 1]])

    # 子ノードのdequeを集める
    R = []
    for j in G[i]:
        R.append(Q[j])

    if R:
        R.sort(key=len, reverse=1)

        # dequeの小さい方から大きい方へマージする処理
        last = R.pop()
        while R:
            nxt = R.pop()
            for k in range(len(last)):
                a0, a1, a2, c0 = last.popleft()
                b0, b1, b2, c1 = nxt[k]
                nxt[k] = [a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD, c0+c1]
            last = nxt
        # a0 <- a2
        for e in last:
            e[0] += e[2]
            e[2] = 0
        q.extend(last)
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
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)
for i in range(N, -1, -1):
    # i+1 <- P[i]
    Q[i] = q = deque([[1, 1, 0, 1]])
    R = []
    for j in G[i]:
        R.append(Q[j])

    if R:
        R.sort(key=len, reverse=1)

        last = R.pop()
        while R:
            nxt = R.pop()
            for k in range(len(nxt)):
                if last:
                    a0, a1, a2, c0 = last.popleft()
                    b0, b1, b2, c1 = nxt.popleft()
                    C = [a0*b0 % MOD, (a0*b1 + a1*b0) % MOD, (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD, c0+c1]
                    nxt.append(C)
                else:
                    nxt.append(nxt.popleft())
            last = nxt
        # a0 <- a2
        for e in last:
            e[0] += e[2]
            e[2] = 0
        q.extend(last)
ans = 0
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
def get_pow():
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = pow(2, x, mod)
        return cache[x]

    return func


mod = 1000000007
n = int(input())
parents = list(map(int, input().split()))
children = [set() for _ in range(n + 1)]
for c, p in enumerate(parents):
    children[p].add(c + 1)

levels = [{0}]
while True:
    level = set()
    for p in levels[-1]:
        level.update(children[p])
    if not level:
        break
    levels.append(level)
levels.reverse()

level_node_count = []
balls = [None] * (n + 1)

for i, level in enumerate(levels):
    level_node_count.append(len(level))
    for node in level:
        balls[node] = [[1, 1, 0]]
        if children[node]:
            balls_from_children = [balls[c] for c in children[node]]
            balls_from_children.sort(key=len)
            bs1 = balls_from_children[0]
            for bs2 in balls_from_children[1:]:
                for (b10, b11, b12), b2 in zip(bs1, bs2):
                    b2[2] = ((b11 + b12) * b2[1] + b12 * b2[0]) % mod
                    b2[1] = (b10 * b2[1] + b11 * b2[0]) % mod
                    b2[0] = b2[0] * b10 % mod
                bs1 = bs2
            for b in balls_from_children[-1]:
                b[0] = (b[0] + b[2]) % mod
                b[2] = 0
            balls[node].extend(balls_from_children[-1])

level_node_count.reverse()

pow2 = get_pow()
print(sum(b[1] * pow2(n - l + 1) % mod for l, b in zip(level_node_count, balls[0])) % mod)

Submission status: Time Limit Exceeded

Solution code:
def get_pow():
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = pow(2, x, mod)
        return cache[x]

    return func


mod = 1000000007
n = int(input())
parents = list(map(int, input().split()))
children = [set() for _ in range(n + 1)]
for c, p in enumerate(parents):
    children[p].add(c + 1)

levels = [{0}]
while True:
    level = set()
    for p in levels[-1]:
        level.update(children[p])
    if not level:
        break
    levels.append(level)
levels.reverse()

level_node_count = []
balls = [None] * (n + 1)

for i, level in enumerate(levels):
    level_node_count.append(len(level))
    for node in level:
        balls[node] = [[1, 1, 0]]
        if children[node]:
            balls_from_children = [balls[c] for c in children[node]]
            balls_from_children.sort(key=len)
            for bs1, bs2 in zip(balls_from_children, balls_from_children[1:]):
                for (b10, b11, b12), b2 in zip(bs1, bs2):
                    b2[2] = ((b11 + b12) * b2[1] + b12 * b2[0]) % mod
                    b2[1] = (b10 * b2[1] + b11 * b2[0]) % mod
                    b2[0] *= b10
            for b in balls_from_children[-1]:
                b[0] += b[2]
                b[2] = 0
            balls[node].extend(balls_from_children[-1])

level_node_count.reverse()

pow2 = get_pow()
print(sum(b[1] * pow2(n - l + 1) % mod for l, b in zip(level_node_count, balls[0])) % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007


def get_pow():
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = pow(2, x, mod)
        return cache[x]

    return func


n = int(input())
parents = list(map(int, input().split()))
children = [set() for _ in range(n + 1)]
for c, p in enumerate(parents):
    children[p].add(c + 1)

levels = [{0}]
while True:
    level = set()
    for p in levels[-1]:
        level.update(children[p])
    if not level:
        break
    levels.append(level)
levels.reverse()

level_node_count = []
balls = [None] * (n + 1)

for i, level in enumerate(levels):
    level_node_count.append(len(level))
    for node in level:
        if children[node]:
            balls_from_children = [balls[c] for c in children[node]]
            balls_from_children.sort(key=len)
            for bs1, bs2 in zip(balls_from_children, balls_from_children[1:]):
                for b1, b2 in zip(bs1, bs2):
                    b2[2] = (b1[1] + b1[2]) * b2[1] + b1[2] * b2[0]
                    b2[1] = b1[0] * b2[1] + b1[1] * b2[0]
                    b2[0] *= b1[0]
            for b in balls_from_children[-1]:
                b[0] += b[2]
                b[2] = 0
            balls[node] = [[1, 1, 0]] + balls_from_children[-1]
        else:
            balls[node] = [[1, 1, 0]]

level_node_count.reverse()

pow2 = get_pow()
print(sum(b[1] * pow2(n - l + 1) for l, b in zip(level_node_count, balls[0])) % mod)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

mod = 1000000007


def get_pow():
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = pow(2, x, mod)
        return cache[x]

    return func


pow2 = get_pow()
n = int(input())
parents = list(map(int, input().split()))
children = [set() for _ in range(n + 1)]
for c, p in enumerate(parents):
    children[p].add(c + 1)

levels = [{0}]
while True:
    level = set()
    for p in levels[-1]:
        level.update(children[p])
    if not level:
        break
    levels.append(level)
levels.reverse()

level_node_count = []
balls = [None] * (n + 1)

for i, level in enumerate(levels):
    level_node_count.append(len(level))
    for node in level:
        if children[node]:
            balls_from_children = [balls[c] for c in children[node]]
            balls_from_children.sort(key=len)
            for bs1, bs2 in zip(balls_from_children, balls_from_children[1:]):
                for b1, b2 in zip(bs1, bs2):
                    b2[2] = (b1[1] + b1[2]) * b2[1] + b1[2] * b2[0]
                    b2[1] = b1[0] * b2[1] + b1[1] * b2[0]
                    b2[0] *= b1[0]
            for b in balls_from_children[-1]:
                b[0] += b[2]
                b[2] = 0
            balls[node] = [[1, 1, 0]] + balls_from_children[-1]
        else:
            balls[node] = [[1, 1, 0]]

level_node_count.reverse()

print(sum(b[1] * pow2(n - l + 1) for l, b in zip(level_node_count, balls[0])) % mod)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

mod = 1000000007


def get_pow():
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = pow(2, x, mod)
        return cache[x]

    return func


def update(n, descendants, balls_from_children):
    ball = [pow2(descendants)]
    for ball_list in balls_from_children:
        put_list = [[], []]
        flag = False
        for c in children[n]:
            if c in ball_list:
                put = ball_list[c]
                flag = True
            else:
                put = 0
            put_list[0].append(balls[c][0] * 2 - put)
            put_list[1].append(put)
        if not flag:
            break
        bl = 0
        for i, p in enumerate(put_list[1]):
            if p:
                bl += reduce(mul, (np for j, np in enumerate(put_list[0]) if j != i), 1) * p * 2
        ball.append(bl)
    return ball


n = int(input())
parents = list(map(int, input().split()))
children = [set() for _ in range(n + 1)]
for c, p in enumerate(parents):
    children[p].add(c + 1)

levels = [{0}]
while True:
    level = set()
    for p in levels[-1]:
        level.update(children[p])
    if not level:
        break
    levels.append(level)
levels.reverse()

node_counts = [0] * (n + 1)
balls = [None] * (n + 1)
pow2 = get_pow()

for i, level in enumerate(levels):
    for n in level:
        if children[n]:
            descendants = 0
            balls_from_children = [{} for _ in range(i)]
            for c in children[n]:
                descendants += node_counts[c]
                for j, b in enumerate(balls[c]):
                    balls_from_children[j][c] = b
            node_counts[n] = descendants + 1
            balls[n] = update(n, descendants, balls_from_children)
        else:
            node_counts[n] = 1
            balls[n] = [1]
        # print(n, balls[n], node_counts[n])

# print(node_counts)
# print(balls)
print(sum(balls[0]) % mod)

Submission status: Accepted

Solution code:
n, = map(int, input().split())
p = [-1] + [*map(int, input().split())]

MOD = 10**9+7
dp = [[] for _ in range(n+1)]
dep = [0]*(n+1)
nxt = [0]*(n+1)

for v in range(n,0,-1):
    _,nxt[p[v]],dep[p[v]] = sorted([nxt[p[v]],dep[p[v]],dep[v]+1])

tot = [0]*(dep[0]+1)
for i in range(n+1): tot[dep[i]] += 1

def merge(p,v):
    if len(dp[p]) < len(dp[v]):
        dp[p],dp[v]=dp[v],dp[p]
    for i in range(-len(dp[v]),0):
        a,b,c = dp[p][i]
        d,e,f = dp[v][i]
        dp[p][i][:] = [a*d%MOD,(b*d+a*e)%MOD,c*f%MOD]

for v in range(n,-1,-1):
    dp[v].append([1,1,2])
    for i in range(-nxt[v]-1,0):
        dp[v][i][0] = dp[v][i][2] - dp[v][i][1]
    if v: merge(p[v],v)

ans = 0
for d in dp[0]:
    ans += pow(d[2],MOD-2,MOD)*d[1]%MOD
print(ans*pow(2,n+1,MOD)%MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int, readline().split())
p = [-1] + [*map(int, readline().split())]

MOD = 10**9+7
child = [[] for i in range(n+1)]
tot = [None for i in range(n+1)]
one = [None for i in range(n+1)]
dep = [0]*(n+1)
p2 = [1]*(n+1)
for i in range(n):
    p2[i+1] = p2[i]*2%MOD

for v in range(n,-1,-1):
    if dep[v]==0:
        tot[v] = []
        one[v] = []
    else:
        child[v].sort(key=lambda i: dep[i])
        one[v] = one[child[v][-1]]
        tot[v] = tot[child[v][-1]]
        #one_sum = [0]*(dep[v])
        #zero_sum = [0]*(dep[v])
        child[v].pop()
        if child[v]:
            zero = [p2[tot[v][j]]-one[v][j] for j in range(-len(one[child[v][-1]]),0)]
        for c in child[v]:
            for j in range(-len(one[c]),0):
                z = p2[tot[c][j]]-one[c][j]
                one[v][j] = (one[v][j]*z+zero[j]*one[c][j])%MOD
                zero[j] = zero[j]*z%MOD
                tot[v][j] += tot[c][j]

    tot[v].append(1)
    one[v].append(1)

    child[p[v]].append(v)
    dep[p[v]] = max(dep[p[v]],dep[v]+1)        

    #print(v,tot[v],one[v])
        
#print("tot",tot[0])
#print("one",one[0])

ans = 0
for i,j in zip(tot[0],one[0]):
    ans += pow(2,n+1-i,MOD)*j%MOD

print(ans%MOD)
#print(sum(tot[0]))