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: Wrong Answer

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)
print(1)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
N=int(input())
plist=list(map(int,input().split()))

def powmod(a,p):
  if p==0:
    return 1
  elif p==1:
    return a
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD    
def invmod(a):
  return powmod(a,MOD-2)

graph=[]
graph_rev=[]
for i in range(N+1):
  graph.append([])
  graph_rev.append([])
  
for i in range(N):
  graph[i+1].append(plist[i])
  graph_rev[plist[i]].append(i+1)
#print(graph)
#print(graph_rev)

num_box=0
pow_2n=powmod(2,N)
ball_list=[pow_2n]*(N+1)
#print(ball_list)

while(sum(ball_list)>0):
  #print(num_box,ball_list)
  for i in range(N+1):
    if i==0:
      num_box+=ball_list[0]
      num_box%=MOD
    
    ball_list[i]=0
    ball_sum=0
    for v in graph_rev[i]:
      ball_sum+=ball_list[v]
    
    num_v=len(graph_rev[i])
    if num_v==1:
      ball_list[i]=ball_sum
    else:
      ball_list[i]=ball_sum*num_v*invmod(powmod(2,num_v))
    
    ball_list[i]%=MOD
        
print(num_box)

Submission status: Wrong Answer

Solution code:
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 2:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Submission status: Wrong Answer

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

sys.setrecursionlimit(202020)


def powmod(a, x, m):
    y = 1
    while 0 < x:
        if x % 2 == 1:
            y *= a
            y %= m
        x //= 2
        a = a ** 2
        a %= m

    return y


M = 10 ** 9 + 7
I2 = powmod(2, M - 2, M)

def dfs(g, v):

    r = [I2]

    if len(g[v]) == 0:
        return r

    cr = []
    for w in g[v]:
        cr.append(dfs(g, w))

    cr.sort(key = lambda v: -len(v))
    d_max = len(cr[0])

    for j in range(d_max):
        pr = 1
        sm = 0
        nc = 0
        for cri in cr:
            if len(cri) <= j:
                break
            c = cri[j]
            pr *= c
            pr %= M
            sm += powmod(c, M - 2, M)
            sm %= M
            nc += 1
        pr *= sm + M - nc
        pr %= M
        pp = 1 + M - pr
        pp %= M
        r.append(pp)


    return r


def solve(n, p):

    g = [[] for _ in range(n + 1)]
    for i in range(n):
        g[p[i]].append(i + 1)

    r = dfs(g, 0)
    ans = 0
    P2 = powmod(2, n, M)
    for c in r:
        ans += P2 * (1 + M - c)
        ans %= M

    return ans


def main():
    n = input()
    n = int(n)
    p = list(map(int, input().split()))

    print(solve(n, p))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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)

ept = []
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]
    if k > 1:
        # a0 <- a2
        for s, r in zip(Q[g[1]] or ept, R):
            r[0] += r[2]; r[2] = 0

        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
    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: Wrong Answer

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 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 status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul

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()

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

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].append(b)
            node_counts[n] = descendants + 1
            ball = [pow(2, descendants, mod)]
            # print(n, balls_from_children, children[n])
            for ball_list in balls_from_children:
                if ball_list:
                    ball.append(reduce(mul, ball_list) * len(ball_list) * 2 % mod)
                else:
                    break
            balls[n] = ball
        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: Wrong Answer

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import math
import collections

N, = list(map(int, sys.stdin.readline().rstrip().split()))
Ps = list(map(int, sys.stdin.readline().rstrip().split()))

tree = collections.defaultdict(list)
for i, P in enumerate(Ps):
    tree[P].append(i + 1)

collisions = [0 for _ in range(N + 1)]

visited = 0
current_levels = [0]
# sames = [1]
while visited < N + 1:
    next_levels = []
    for n in current_levels:
        if n in tree:
            for t in tree[n]:
                collisions[t] = collisions[n] + len(tree[n]) - 1
            next_levels += tree[n]
    visited += len(current_levels)
    # sames.append(len(current_levels))
    current_levels = next_levels

result = 0

c = 1
collision_cache = [0 for _ in range(N + 1)]
collision_cache[N] = c
for i in range(N):
    c = c * 2 % 1000000007
    collision_cache[N - 1 - i] = c

for collision in collisions:
    # print(collision)
    result += collision_cache[collision]
    result = result % 1000000007
    # print(math.pow(2, N - collision))
    # print(collision_cache[collision])
    # result += math.pow(2, N - collision)
# result = result % 1000000007
# for same in sames:
#     print(same, math.pow(2, N + 1 - same))
#     result += same * math.pow(2, N + 1 - same) % 1000000007
print(result)
# print(Ps)
# print(collisions)
exit(0)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc086/tasks/arc086_c

対消滅する可能性があるのは同じ深さの点に置かれたビー玉だけ
→1つも残らない or 1つだけ残るである

すなわち、ある深さに関して、そのうち1つ残るのがいくつあるかを数えればよい

1つだけ置く場合→絶対のこる
2つ置く場合→絶対消える
3つ置く場合→3つのLCAが等しくなければ残る

木dpみたいにする？
dp[0] = 一つも含んでいない場合の通り数
dp[1] = 1つ含んでいる場合の通り数

dp[0] = すべての場合 - dp[1]
dp[1] = 1つだけ1を持っている場合

で、子から親に伝播させていく…？
マージテクで計算量削減か？
3sだからそうっぽいな…
3つ以上のマージ書くのだるすぎん？

またはマージの順番をどっかにメモっておく

maxd-d = indexでやる
最長のやつにマージする

dp[maxd-d][1] = 1つだけ元深さdが残っている場合の数
c = 子の数

計算量は？
サイズは高々1しか増えないので可能っぽい
2倍処理がまずい

"""
import sys
mod = 10**9 + 7
sys.setrecursionlimit(200000)

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis

def inverse(a): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)


def dfs(v):

    if len(lis[v]) == 0:
        ret = [ 0 for i in range(maxd-dlis[v]+1) ]
        ret[maxd-dlis[v]] = 1
        
        return 1,ret,0

    else:
        #ここがむずすぎる
        #まずcとretを受け取るか
        csum = 0 #cの合計

        len_c_ret = []
        for nex in lis[v]:
            nc,nret,mmm = dfs(nex)
            #print (nex,nc,nret,mmm)
            len_c_ret.append( [len(nret) , nc , nret , mmm ] )
            csum += nc
        len_c_ret.sort()

        #1つしかない場合マージしない
        if len(len_c_ret) == 1:
            
            len_c_ret[0][2].append(pow(2,len_c_ret[0][1],mod) * inverse(pow(2,len_c_ret[0][3] + 1,mod)))
            return len_c_ret[0][1]+1 , len_c_ret[0][2] , len_c_ret[0][3] + 1

        #2つ以上の場合最大のやつにマージする
        for i in range(len(len_c_ret)):
            xxxx = pow(2,len_c_ret[i][3],mod)
            if xxxx > 1:
                for j in range(len(len_c_ret[i][2])):
                    len_c_ret[i][2][j] *= xxxx
                    len_c_ret[i][2][j] %= mod
        
        for revd in range(len(len_c_ret[-1][2])):

            zmul = 1
            otmp = csum
            for i in range(len(len_c_ret)-1,-1,-1):
                if revd < len(len_c_ret[i][2]):
                    zmul *= ( pow(2,len_c_ret[i][1],mod) - len_c_ret[i][2][revd] )
                    otmp -= len_c_ret[i][1]
                else:
                    break

            zmul *= pow(2,otmp,mod)
            zmul %= mod

            nsum = 0
            for i in range(len(len_c_ret)-1,-1,-1):
                if revd < len(len_c_ret[i][2]):
                    nsum += zmul * inverse(pow(2,len_c_ret[i][1],mod)-len_c_ret[i][2][revd])*len_c_ret[i][2][revd]
                    nsum %= mod
                else:
                    break
            len_c_ret[-1][2][revd] = nsum * 2 % mod


        len_c_ret[-1][2].append(pow(2,csum,mod))
        return csum+1 , len_c_ret[-1][2] , 0

N = int(input())
p = list(map(int,input().split()))

lis = [ [] for i in range(N+1) ]

for i in range(N):

    #lis[i+1].append(p[i])
    lis[p[i]].append(i+1)

dlis,plis = NC_Dij(lis,0)
maxd = max(dlis)

cc,ans,tmps = dfs(0)
#print (ans)
print (sum(ans) * pow(2,tmps,mod) % mod)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc086/tasks/arc086_c

対消滅する可能性があるのは同じ深さの点に置かれたビー玉だけ
→1つも残らない or 1つだけ残るである

すなわち、ある深さに関して、そのうち1つ残るのがいくつあるかを数えればよい

1つだけ置く場合→絶対のこる
2つ置く場合→絶対消える
3つ置く場合→3つのLCAが等しくなければ残る

木dpみたいにする？
dp[0] = 一つも含んでいない場合の通り数
dp[1] = 1つ含んでいる場合の通り数

dp[0] = すべての場合 - dp[1]
dp[1] = 1つだけ1を持っている場合

で、子から親に伝播させていく…？
マージテクで計算量削減か？
3sだからそうっぽいな…
3つ以上のマージ書くのだるすぎん？

またはマージの順番をどっかにメモっておく

maxd-d = indexでやる
最長のやつにマージする

dp[maxd-d][1] = 1つだけ元深さdが残っている場合の数
c = 子の数

計算量は？
サイズは高々1しか増えないので可能っぽい
2倍処理がまずい

"""
import sys
mod = 10**9 + 7
sys.setrecursionlimit(200000)

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis

def inverse(a): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)


def dfs(v):

    if len(lis[v]) == 0:
        ret = [ 0 for i in range(maxd-dlis[v]+1) ]
        ret[maxd-dlis[v]] = 1
        
        return 1,ret,0

    else:
        #ここがむずすぎる
        #まずcとretを受け取るか
        csum = 0 #cの合計

        len_c_ret = []
        for nex in lis[v]:
            nc,nret,mmm = dfs(nex)
            #print (nex,nc,nret,mmm)
            len_c_ret.append( [len(nret) , nc , nret , mmm ] )
            csum += nc
        len_c_ret.sort()

        #1つしかない場合マージしない
        if len(len_c_ret) == 1:
            
            len_c_ret[0][2].append(pow(2,len_c_ret[0][1],mod) * inverse(pow(2,len_c_ret[0][3] + 1,mod)))
            return len_c_ret[0][1]+1 , len_c_ret[0][2] , len_c_ret[0][3] + 1

        #2つ以上の場合最大のやつにマージする
        for i in range(len(len_c_ret)):
            xxxx = pow(2,len_c_ret[i][3],mod)
            if xxxx > 1:
                for j in range(len(len_c_ret[i][2])):
                    len_c_ret[i][2][j] *= xxxx
                    len_c_ret[i][2][j] %= mod
        
        for revd in range(len(len_c_ret[-1][2])):

            zmul = 1
            for i in range(len(len_c_ret)):
                if revd < len(len_c_ret[i][2]):
                    zmul *= ( pow(2,len_c_ret[i][1],mod) - len_c_ret[i][2][revd] )
                else:
                    zmul *= pow(2,len_c_ret[i][1],mod)
                zmul %= mod

            nsum = 0
            for i in range(len(len_c_ret)):
                if revd < len(len_c_ret[i][2]):
                    nsum += zmul * inverse(pow(2,len_c_ret[i][1],mod)-len_c_ret[i][2][revd])*len_c_ret[i][2][revd]
                    nsum %= mod
            len_c_ret[-1][2][revd] = nsum * 2 % mod


        len_c_ret[-1][2].append(pow(2,csum,mod))
        return csum+1 , len_c_ret[-1][2] , 0

N = int(input())
p = list(map(int,input().split()))

lis = [ [] for i in range(N+1) ]

for i in range(N):

    #lis[i+1].append(p[i])
    lis[p[i]].append(i+1)

dlis,plis = NC_Dij(lis,0)
maxd = max(dlis)

cc,ans,tmps = dfs(0)
#print (ans)
print (sum(ans) * pow(2,tmps,mod) % mod)

Submission status: Time Limit Exceeded

Solution code:

"""

https://atcoder.jp/contests/arc086/tasks/arc086_c

対消滅する可能性があるのは同じ深さの点に置かれたビー玉だけ
→1つも残らない or 1つだけ残るである

すなわち、ある深さに関して、そのうち1つ残るのがいくつあるかを数えればよい

1つだけ置く場合→絶対のこる
2つ置く場合→絶対消える
3つ置く場合→3つのLCAが等しくなければ残る

木dpみたいにする？
dp[0] = 一つも含んでいない場合の通り数
dp[1] = 1つ含んでいる場合の通り数

dp[0] = すべての場合 - dp[1]
dp[1] = 1つだけ1を持っている場合

で、子から親に伝播させていく…？
マージテクで計算量削減か？
3sだからそうっぽいな…
3つ以上のマージ書くのだるすぎん？

またはマージの順番をどっかにメモっておく

maxd-d = indexでやる
最長のやつにマージする

dp[maxd-d][1] = 1つだけ元深さdが残っている場合の数
c = 子の数

計算量は？
サイズは高々1しか増えないので可能っぽい
"""
import sys
mod = 10**9 + 7
sys.setrecursionlimit(200000)

from collections import deque
def NC_Dij(lis,start):

    ret = [float("inf")] * len(lis)
    ret[start] = 0
    
    q = deque([start])
    plis = [i for i in range(len(lis))]

    while len(q) > 0:
        now = q.popleft()

        for nex in lis[now]:

            if ret[nex] > ret[now] + 1:
                ret[nex] = ret[now] + 1
                plis[nex] = now
                q.append(nex)

    return ret,plis

def inverse(a): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)


def dfs(v):

    if len(lis[v]) == 0:
        ret = [ 0 for i in range(maxd-dlis[v]+1) ]
        ret[maxd-dlis[v]] = 1
        
        return 1,ret

    else:
        #ここがむずすぎる
        #まずcとretを受け取るか
        csum = 0 #cの合計

        len_c_ret = []
        for nex in lis[v]:
            nc,nret = dfs(nex)
            len_c_ret.append( [len(nret) , nc , nret ] )
            csum += nc
        len_c_ret.sort()

        #1つしかない場合マージしない
        if len(len_c_ret) == 1:
            for i in range(len(len_c_ret[0][2])):
                len_c_ret[0][2][i] *= 2
                len_c_ret[0][2][i] %= mod
            len_c_ret[0][2].append(pow(2,len_c_ret[0][1],mod))
            return len_c_ret[0][1]+1 , len_c_ret[0][2]

        #2つ以上の場合最大のやつにマージする
        for revd in range(len(len_c_ret[-1][2])):

            zmul = 1
            for i in range(len(len_c_ret)):
                if revd < len(len_c_ret[i][2]):
                    zmul *= ( pow(2,len_c_ret[i][1],mod) - len_c_ret[i][2][revd] )
                else:
                    zmul *= pow(2,len_c_ret[i][1],mod)
                zmul %= mod

            nsum = 0
            for i in range(len(len_c_ret)):
                if revd < len(len_c_ret[i][2]):
                    nsum += zmul * inverse(pow(2,len_c_ret[i][1],mod)-len_c_ret[i][2][revd])*len_c_ret[i][2][revd]
                    nsum %= mod
            len_c_ret[-1][2][revd] = nsum * 2 % mod


        len_c_ret[-1][2].append(pow(2,csum,mod))
        return csum+1 , len_c_ret[-1][2]

N = int(input())
p = list(map(int,input().split()))

lis = [ [] for i in range(N+1) ]

for i in range(N):

    #lis[i+1].append(p[i])
    lis[p[i]].append(i+1)

dlis,plis = NC_Dij(lis,0)
maxd = max(dlis)

cc,ans = dfs(0)
#print (ans)
print (sum(ans)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        dpu = deque()
        start=(inv2, inv2, 0)
        # 葉の場合
        if len(to[u]) == 0:
            dpu.append(start)
            return dpu
        # すべての子をマージ
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        start=(inv2, inv2, 0)
        # 葉の場合
        if len(to[u]) == 0:
            return [deque(start)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            dpv = dfs(v)
            #深さが2段以上あったらu2をu0に
            if len(dpv) > 1:
                for d, (u0, u1, u2) in enumerate(dpv):
                    dpv[d] = (u0 + u2, u1, 0)
            if not dpu:
                dpu = dpv
            else:
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        def merge(dpu, dpv):
            vn = len(dpv)
            for d in range(-1, -1 - vn, -1):
                u0, u1, u2 = dpu[d]
                v0, v1, v2 = dpv[d]
                n0 = (u0 * v0) % md
                n1 = (u0 * v1 + u1 * v0) % md
                n2 = (u2 * (v0 + v1 + v2) + v2 * (u0 + u1) + u1 * v1) % md
                dpu[d] = (n0, n1, n2)

        # 葉の場合
        if len(to[u]) == 0:
            return [(inv2, inv2, 0)]
        # すべての子をマージ
        dpu = []
        for v in to[u]:
            if not dpu:
                dpu = dfs(v)
            else:
                dpv = dfs(v)
                if len(dpu) < len(dpv): dpu, dpv = dpv, dpu
                merge(dpu, dpv)
        for d in range(len(dpu)):
            u0, u1, u2 = dpu[d]
            dpu[d] = (u0 + u2, u1, 0)
        dpu.append((inv2, inv2, 0))
        return dpu

    md = 10 ** 9 + 7
    # 1/2のmod
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp, 1):
        to[p].append(i)
    # print(to)
    dp0 = dfs()
    # print(dp0)
    ans = sum(u1 for _, u1, _ in dp0)
    print((ans * pow(2, n + 1, md)) % md)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        if not to[u]:
            dp[u].append([inv2, inv2, 0])
            return
        dpu = []
        for v in to[u]:
            dfs(v)
            v = utou[v]
            if not dpu:
                dpu = dp[v]
                utou[u] = v
                continue
            dpv = dp[v]
            if len(dpu) < len(dpv):
                dpu, dpv = dpv, dpu
                utou[u] = v
            for d in range(len(dpv)):
                dpu[d][2] = (dpu[d][2] * sum(dpv[d]) + dpv[d][2] * sum(dpu[d])
                             - dpu[d][2] * dpv[d][2] + dpu[d][1] * dpv[d][1]) % md
                dpu[d][1] = (dpu[d][0] * dpv[d][1] + dpu[d][1] * dpv[d][0]) % md
                dpu[d][0] = (dpu[d][0] * dpv[d][0]) % md
        for d in range(len(dpu)):
            dpu[d][0] = (dpu[d][0] + dpu[d][2]) % md
            dpu[d][2] = 0
        dpu.appendleft([inv2, inv2, 0])

    md = 10 ** 9 + 7
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp):
        i += 1
        to[p].append(i)
    #print(to)
    utou = list(range(n + 1))
    dp = [deque() for _ in range(n + 1)]
    dfs()
    #p2D(dp)
    # print(utou)
    root = utou[0]
    ans = 0
    for dpr in dp[root]:
        ans += dpr[1]
    ans %= md
    print((ans * pow(2, n + 1, md)) % md)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import *

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    def dfs(u=0):
        if not to[u]:
            dp[u] = [[inv2, inv2, 0]]
            return
        dpu = []
        for v in to[u]:
            dfs(v)
            v = utou[v]
            if not dpu:
                dpu = dp[v]
                utou[u] = v
                continue
            dpv = dp[v]
            if len(dpu) < len(dpv):
                dpu, dpv = dpv, dpu
                utou[u] = v
            for d in range(len(dpv)):
                dpu[d][2] = (dpu[d][2] * sum(dpv[d]) + dpv[d][2] * sum(dpu[d])
                             - dpu[d][2] * dpv[d][2] + dpu[d][1] * dpv[d][1]) % md
                dpu[d][1] = (dpu[d][0] * dpv[d][1] + dpu[d][1] * dpv[d][0]) % md
                dpu[d][0] = (dpu[d][0] * dpv[d][0]) % md
        for d in range(len(dpu)):
            dpu[d][0] = (dpu[d][0] + dpu[d][2]) % md
            dpu[d][2] = 0
        dpu.insert(0, [inv2, inv2, 0])

    md = 10 ** 9 + 7
    inv2 = pow(2, md - 2, md)
    to = defaultdict(list)
    n = int(input())
    pp = list(map(int, input().split()))
    for i, p in enumerate(pp):
        i += 1
        to[p].append(i)
    #print(to)
    utou = list(range(n + 1))
    dp = [[] for _ in range(n + 1)]
    dfs()
    #p2D(dp)
    # print(utou)
    root = utou[0]
    ans = 0
    for dpr in dp[root]:
        ans += dpr[1]
    ans %= md
    print((ans * pow(2, n + 1, md)) % md)

main()

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(202020)


def powmod(a, x, m):
    y = 1
    while 0 < x:
        if x % 2 == 1:
            y *= a
            y %= m
        x //= 2
        a = a ** 2
        a %= m

    return y


M = 10 ** 9 + 7
I2 = powmod(2, M - 2, M)

def dfs(g, v):

    r = [I2]

    if len(g[v]) == 0:
        return r

    cr = []
    for w in g[v]:
        cr.append(dfs(g, w))

    cr.sort(key = lambda v: -len(v))
    d_max = len(cr[0])

    for j in range(d_max):
        pr = 1
        sm = 0
        nc = 0
        for cri in cr:
            if len(cri) <= j:
                break
            c = cri[j]
            pr *= c
            pr %= M
            sm += powmod(c, M - 2, M)
            sm %= M
            nc += 1
        pr *= sm + M - nc
        pr %= M
        pp = 1 + M - pr
        pp %= M
        r.append(pp)


    return r


def solve(n, p):

    g = [[] for _ in range(n + 1)]
    for i in range(n):
        g[p[i]].append(i + 1)

    r = dfs(g, 0)
    ans = 0
    P2 = powmod(2, n + 1, M)
    for c in r:
        ans += P2 * (1 + M - c)
        ans %= M

    return ans


def main():
    n = input()
    n = int(n)
    p = list(map(int, input().split()))

    print(solve(n, p))


if __name__ == '__main__':
    main()