Road Improvement (Codeforces 543D)
Tags: DP, trees

The country has n cities and n - 1 bidirectional roads, it is possible to get from every city to any other one if you move only along the roads. The cities are numbered with integers from 1 to n inclusive.All the roads are initially bad, but the government wants to improve the state of some roads. We will assume that the citizens are happy about road improvement if the path from the capital located in city x to any other city contains at most one bad road.Your task is — for every possible x determine the number of ways of improving the quality of some roads in order to meet the citizens' condition. As those values can be rather large, you need to print each value modulo 1 000 000 007 (109 + 7).

Input: The first line of the input contains a single integer n (2 ≤ n ≤ 2·105) — the number of cities in the country. Next line contains n - 1 positive integers p2, p3, p4, ..., pn (1 ≤ pi ≤ i - 1) — the description of the roads in the country. Number pi means that the country has a road connecting city pi and city i. 

Output: Print n integers a1, a2, ..., an, where ai is the sought number of ways to improve the quality of the roads modulo 1 000 000 007 (109 + 7), if the capital of the country is at city number i.


Sample Inputs:
3
1 1

5
1 2 3 4

Sample Outputs:
4 3 3

5 8 9 8 5

Solution (Python):
import sys
readline = sys.stdin.readline

class Graph:

    def __init__(self, V, edges=False, graph=False, directed=False, weighted=False, inf=float('inf')):
        self.V = V
        self.directed = directed
        self.weighted = weighted
        self.inf = inf
        if graph:
            self.graph = graph
            self.edges = []
            for i in range(self.V):
                if self.weighted:
                    for (j, d) in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j, d))
                else:
                    for j in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j))
        else:
            self.edges = edges
            self.graph = [[] for i in range(self.V)]
            if weighted:
                for (i, j, d) in self.edges:
                    self.graph[i].append((j, d))
                    if not self.directed:
                        self.graph[j].append((i, d))
            else:
                for (i, j) in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)

    def SIV_DFS(self, s, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, lowlink=False, parents=False, postorder=False, preorder=False, subtree_size=False, topological_sort=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if lowlink:
            order = [None] * self.V
            ll = [None] * self.V
            idx = 0
        if parents or cycle_detection or lowlink or subtree_size:
            ps = [None] * self.V
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        if subtree_size:
            ss = [1] * self.V
        if unweighted_dist or bipartite_graph:
            uwd = [self.inf] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [self.inf] * self.V
            wd[s] = 0
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if lowlink:
                    order[x] = idx
                    ll[x] = idx
                    idx += 1
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
                        if parents or cycle_detection or lowlink or subtree_size:
                            ps[y] = x
                        if unweighted_dist or bipartite_graph:
                            uwd[y] = uwd[x] + 1
                        if weighted_dist:
                            wd[y] = wd[x] + d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag = False
                            if cycle_detection:
                                cd = (y, x)
            elif not finished[x]:
                finished[x] = True
                if euler_tour:
                    et.append(~x)
                if lowlink:
                    bl = True
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if ps[x] == y and bl:
                            bl = False
                            continue
                        ll[x] = min(ll[x], order[y])
                    if x != s:
                        ll[ps[x]] = min(ll[ps[x]], ll[x])
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if y == ps[x]:
                            continue
                        ss[x] += ss[y]
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (x, y) = tpl[:2] if self.weighted else tpl
                if uwd[x] == self.inf or uwd[y] == self.inf:
                    continue
                if not uwd[x] % 2 ^ uwd[y] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if uwd[x] == self.inf:
                        continue
                    bg[uwd[x] % 2].append(x)
        retu = ()
        if bipartite_graph:
            retu += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            retu += (cd,)
        if directed_acyclic:
            retu += (dag,)
        if euler_tour:
            retu += (et,)
        if linked_components:
            retu += (lc,)
        if lowlink:
            retu = (ll,)
        if parents:
            retu += (ps,)
        if postorder:
            retu += (post,)
        if preorder:
            retu += (pre,)
        if subtree_size:
            retu += (ss,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            retu += (tp_sort,)
        if unweighted_dist:
            retu += (uwd,)
        if weighted_dist:
            retu += (wd,)
        if len(retu) == 1:
            retu = retu[0]
        return retu

    def Build_Rerooting(self, s, f_transition, f_merge):
        self.rerooting_s = s
        self.rerooting_f_transition = f_transition
        self.rerooting_f_merge = f_merge
        (parents, postorder, preorder) = self.SIV_DFS(s, parents=True, postorder=True, preorder=True)
        self.rerooting_lower_dp = [None] * self.V
        for x in postorder:
            self.rerooting_lower_dp[x] = self.rerooting_f_merge([self.rerooting_f_transition(self.rerooting_lower_dp[y]) for y in G.graph[x] if y != parents[x]])
        self.rerooting_upper_dp = [None] * self.V
        for x in preorder:
            children = [y for y in self.graph[x] if y != parents[x]]
            left_accumule_f = [None] * (len(children) + 1)
            right_accumule_f = [None] * (len(children) + 1)
            left_accumule_f[0] = self.rerooting_f_merge([])
            for i in range(1, len(children) + 1):
                left_accumule_f[i] = self.rerooting_f_merge([left_accumule_f[i - 1], self.rerooting_f_transition(self.rerooting_lower_dp[children[i - 1]])])
            right_accumule_f[len(children)] = self.rerooting_f_merge([])
            for i in range(len(children) - 1, -1, -1):
                right_accumule_f[i] = self.rerooting_f_merge([right_accumule_f[i + 1], self.rerooting_f_transition(self.rerooting_lower_dp[children[i]])])
            for i in range(len(children)):
                if parents[x] != None:
                    self.rerooting_upper_dp[children[i]] = self.rerooting_f_merge([left_accumule_f[i], right_accumule_f[i + 1], self.rerooting_f_transition(self.rerooting_upper_dp[x])])
                else:
                    self.rerooting_upper_dp[children[i]] = self.rerooting_f_merge([left_accumule_f[i], right_accumule_f[i + 1]])

    def Rerooting(self, x):
        if x == self.rerooting_s:
            retu = self.rerooting_lower_dp[x]
        else:
            retu = self.rerooting_f_merge([self.rerooting_lower_dp[x], self.rerooting_f_transition(self.rerooting_upper_dp[x])])
        return retu
N = int(readline())
edges = []
for (i, p) in enumerate(map(int, readline().split()), 1):
    p -= 1
    edges.append((p, i))
G = Graph(N, edges=edges)
mod = 10 ** 9 + 7

def transition(c):
    return (c + 1) % mod

def merge(lst):
    retu = 1
    for c in lst:
        retu *= c
        retu %= mod
    return retu
G.Build_Rerooting(0, transition, merge)
ans_lst = [G.Rerooting(x) for x in range(N)]
print(*ans_lst)

Solution (Python):
class Graph:

    def __init__(self, n_vertices, edges, directed=True, weighted=False):
        self.n_vertices = n_vertices
        self.edges = edges
        self.directed = directed
        self.weighted = weighted

    @property
    def adj(self):
        try:
            return self._adj
        except AttributeError:
            adj = [[] for _ in range(self.n_vertices)]

            def d_w(e):
                adj[e[0]].append((e[1], e[2]))

            def ud_w(e):
                adj[e[0]].append((e[1], e[2]))
                adj[e[1]].append((e[0], e[2]))

            def d_uw(e):
                adj[e[0]].append(e[1])

            def ud_uw(e):
                adj[e[0]].append(e[1])
                adj[e[1]].append(e[0])
            helper = (ud_uw, d_uw, ud_w, d_w)[self.directed + self.weighted * 2]
            for e in self.edges:
                helper(e)
            self._adj = adj
            return adj

class RootedTree(Graph):

    def __init__(self, n_vertices, edges, root_vertex):
        self.root = root_vertex
        super().__init__(n_vertices, edges, False, False)

    @property
    def parent(self):
        try:
            return self._parent
        except AttributeError:
            adj = self.adj
            parent = [None] * self.n_vertices
            parent[self.root] = -1
            stack = [self.root]
            for i in range(self.n_vertices):
                v = stack.pop()
                for u in adj[v]:
                    if parent[u] is None:
                        parent[u] = v
                        stack.append(u)
            self._parent = parent
            return parent

    @property
    def children(self):
        try:
            return self._children
        except AttributeError:
            children = [None] * self.n_vertices
            for (v, (l, p)) in enumerate(zip(self.adj, self.parent)):
                children[v] = [u for u in l if u != p]
            self._children = children
            return children

    @property
    def dfs_order(self):
        try:
            return self._dfs_order
        except AttributeError:
            order = [None] * self.n_vertices
            children = self.children
            stack = [self.root]
            for i in range(self.n_vertices):
                v = stack.pop()
                order[i] = v
                for u in children[v]:
                    stack.append(u)
            self._dfs_order = order
            return order
from functools import reduce
from itertools import accumulate, chain

def rerooting(rooted_tree, merge, identity, finalize):
    N = rooted_tree.n_vertices
    parent = rooted_tree.parent
    children = rooted_tree.children
    order = rooted_tree.dfs_order
    dp_down = [None] * N
    for v in reversed(order[1:]):
        dp_down[v] = finalize(reduce(merge, (dp_down[c] for c in children[v]), identity))
    dp_up = [None] * N
    dp_up[0] = identity
    for v in order:
        if len(children[v]) == 0:
            continue
        temp = (dp_up[v],) + tuple((dp_down[u] for u in children[v])) + (identity,)
        left = accumulate(temp[:-2], merge)
        right = tuple(accumulate(reversed(temp[2:]), merge))
        for (u, l, r) in zip(children[v], left, reversed(right)):
            dp_up[u] = finalize(merge(l, r))
    res = [None] * N
    for (v, l) in enumerate(children):
        res[v] = reduce(merge, (dp_down[u] for u in children[v]), identity)
        res[v] = finalize(merge(res[v], dp_up[v]))
    return res

def solve(T):
    MOD = 10 ** 9 + 7

    def merge(x, y):
        return x * y % MOD

    def finalize(x):
        return x + 1
    return [v - 1 for v in rerooting(T, merge, 1, finalize)]
if __name__ == '__main__':
    N = int(input())
    edges = [(i + 1, p - 1) for (i, p) in enumerate(map(int, input().split()))]
    T = RootedTree(N, edges, 0)
    print(*solve(T))

Solution (Python):
import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
from collections import Counter, deque, defaultdict
from functools import lru_cache, reduce
from heapq import heappush, heappop, heapify, heappushpop, _heappop_max, _heapify_max

def _heappush_max(heap, item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap) - 1)

def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        (item, heap[0]) = (heap[0], item)
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD, modf
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

class Graph:

    def __init__(self, V, edges=False, graph=False, directed=False, weighted=False):
        self.V = V
        self.directed = directed
        self.weighted = weighted
        if not graph:
            self.edges = edges
            self.graph = [[] for i in range(self.V)]
            if weighted:
                for (i, j, d) in self.edges:
                    self.graph[i].append((j, d))
                    if not self.directed:
                        self.graph[j].append((i, d))
            else:
                for (i, j) in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)
        else:
            self.graph = graph
            self.edges = []
            for i in range(self.V):
                if self.weighted:
                    for (j, d) in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j, d))
                else:
                    for j in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j))

    def SS_BFS(self, s, bipartite_graph=False, linked_components=False, parents=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        seen[s] = True
        if linked_components:
            lc = [s]
        if parents:
            ps = [None] * self.V
            ps[s] = s
        if unweighted_dist or bipartite_graph:
            uwd = [float('inf')] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [float('inf')] * self.V
            wd[s] = 0
        queue = deque([s])
        while queue:
            x = queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if not seen[y]:
                    seen[y] = True
                    queue.append(y)
                    if linked_components:
                        lc.append(y)
                    if parents:
                        ps[y] = x
                    if unweighted_dist or bipartite_graph:
                        uwd[y] = uwd[x] + 1
                    if weighted_dist:
                        wd[y] = wd[x] + d
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if type(uwd[i]) == float or type(uwd[j]) == float:
                    continue
                if not uwd[i] % 2 ^ uwd[j] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if type(uwd[x]) == float:
                        continue
                    bg[uwd[x] % 2].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if unweighted_dist:
            tpl += (uwd,)
        if weighted_dist:
            tpl += (wd,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def AP_BFS(self, bipartite_graph=False, linked_components=False, parents=False):
        seen = [False] * self.V
        if bipartite_graph:
            bg = [None] * self.V
            cnt = -1
        if linked_components:
            lc = []
        if parents:
            ps = [None] * self.V
        for s in range(self.V):
            if seen[s]:
                continue
            seen[s] = True
            if bipartite_graph:
                cnt += 1
                bg[s] = (cnt, s & 2)
            if linked_components:
                lc.append([s])
            if parents:
                ps[s] = s
            queue = deque([s])
            while queue:
                x = queue.popleft()
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
                        if bipartite_graph:
                            bg[y] = (cnt, bg[x][1] ^ 1)
                        if linked_components:
                            lc[-1].append(y)
                        if parents:
                            ps[y] = x
        if bipartite_graph:
            bg_ = bg
            bg = [[[], []] for i in range(cnt + 1)]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if not bg_[i][1] ^ bg_[j][1]:
                    bg[bg_[i][0]] = False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def SS_DFS(self, s, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, parents=False, postorder=False, preorder=False, subtree_size=False, topological_sort=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if parents or cycle_detection or subtree_size:
            ps = [None] * self.V
            ps[s] = s
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        if subtree_size:
            ss = [1] * self.V
        if unweighted_dist or bipartite_graph:
            uwd = [float('inf')] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [float('inf')] * self.V
            wd[s] = 0
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
                        if parents or cycle_detection or subtree_size:
                            ps[y] = x
                        if unweighted_dist or bipartite_graph:
                            uwd[y] = uwd[x] + 1
                        if weighted_dist:
                            wd[y] = wd[x] + d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag = False
                            if cycle_detection:
                                cd = (y, x)
            elif not finished[x]:
                finished[x] = True
                if euler_tour:
                    et.append(~x)
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if y == ps[x]:
                            continue
                        ss[x] += ss[y]
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if type(uwd[i]) == float or type(uwd[j]) == float:
                    continue
                if not uwd[i] % 2 ^ uwd[j] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if type(uwd[x]) == float:
                        continue
                    bg[uwd[x] % 2].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            tpl += (cd,)
        if directed_acyclic:
            tpl += (dag,)
        if euler_tour:
            tpl += (et,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if postorder:
            tpl += (post,)
        if preorder:
            tpl += (pre,)
        if subtree_size:
            tpl += (ss,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            tpl += (tp_sort,)
        if unweighted_dist:
            tpl += (uwd,)
        if weighted_dist:
            tpl += (wd,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def AP_DFS(self, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, parents=False, postorder=False, preorder=False, topological_sort=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if bipartite_graph:
            bg = [None] * self.V
            cnt = -1
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if parents or cycle_detection:
            ps = [None] * self.V
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        for s in range(self.V):
            if seen[s]:
                continue
            if bipartite_graph:
                cnt += 1
                bg[s] = (cnt, s & 2)
            if linked_components:
                lc.append([])
            if parents:
                ps[s] = s
            stack = [(s, 0)] if self.weighted else [s]
            while stack:
                if self.weighted:
                    (x, d) = stack.pop()
                else:
                    x = stack.pop()
                if not seen[x]:
                    seen[x] = True
                    stack.append((x, d) if self.weighted else x)
                    if euler_tour:
                        et.append(x)
                    if linked_components:
                        lc[-1].append(x)
                    if preorder:
                        pre.append(x)
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if not seen[y]:
                            stack.append((y, d) if self.weighted else y)
                            if bipartite_graph:
                                bg[y] = (cnt, bg[x][1] ^ 1)
                            if parents or cycle_detection:
                                ps[y] = x
                        elif not finished[y]:
                            if directed_acyclic and dag:
                                dag = False
                                if cycle_detection:
                                    cd = (y, x)
                elif not finished[x]:
                    finished[x] = True
                    if euler_tour:
                        et.append(~x)
                    if postorder or topological_sort:
                        post.append(x)
        if bipartite_graph:
            bg_ = bg
            bg = [[[], []] for i in range(cnt + 1)]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if not bg_[i][1] ^ bg_[j][1]:
                    bg[bg_[i][0]] = False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        tpl = ()
        if bipartite_graph:
            tpl += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            tpl += (cd,)
        if directed_acyclic:
            tpl += (dag,)
        if euler_tour:
            tpl += (et,)
        if linked_components:
            tpl += (lc,)
        if parents:
            tpl += (ps,)
        if postorder:
            tpl += (post,)
        if preorder:
            tpl += (pre,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            tpl += (tp_sort,)
        if len(tpl) == 1:
            tpl = tpl[0]
        return tpl

    def Tree_Diameter(self, weighted=False):

        def Farthest_Point(u):
            dist = self.SS_BFS(u, weighted_dist=True) if weighted else self.SS_BFS(u, unweighted_dist=True)
            fp = 0
            for i in range(self.V):
                if dist[fp] < dist[i]:
                    fp = i
            return (fp, dist[fp])
        (u, d) = Farthest_Point(0)
        (v, d) = Farthest_Point(u)
        return (u, v, d)

    def SCC(self):
        reverse_graph = [[] for i in range(self.V)]
        for tpl in self.edges:
            (i, j) = tpl[:2] if self.weighted else tpl
            reverse_graph[j].append(i)
        postorder = self.AP_DFS(postorder=True)
        scc = []
        seen = [False] * self.V
        for s in postorder[::-1]:
            if seen[s]:
                continue
            queue = deque([s])
            seen[s] = True
            lst = []
            while queue:
                x = queue.popleft()
                lst.append(x)
                for y in reverse_graph[x]:
                    if self.weighted:
                        y = y[0]
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
            scc.append(lst)
        return scc

    def Build_LCA(self, s):
        (self.euler_tour, self.parents, depth) = self.SS_DFS(s, euler_tour=True, parents=True, unweighted_dist=True)
        self.dfs_in_index = [None] * self.V
        self.dfs_out_index = [None] * self.V
        for (i, x) in enumerate(self.euler_tour):
            if x >= 0:
                self.dfs_in_index[x] = i
            else:
                self.dfs_out_index[~x] = i
        self.ST = Segment_Tree(2 * self.V, lambda x, y: min(x, y), float('inf'))
        lst = [None] * 2 * self.V
        for i in range(2 * self.V):
            if self.euler_tour[i] >= 0:
                lst[i] = depth[self.euler_tour[i]]
            else:
                lst[i] = depth[self.parents[~self.euler_tour[i]]]
        self.ST.Build(lst)

    def LCA(self, a, b):
        m = min(self.dfs_in_index[a], self.dfs_in_index[b])
        M = max(self.dfs_in_index[a], self.dfs_in_index[b])
        x = self.euler_tour[self.ST.Fold_Index(m, M + 1)]
        if x >= 0:
            return x
        else:
            return self.parents[~x]

    def Dijkstra(self, s, route_restoration=False):
        dist = [float('inf')] * self.V
        dist[s] = 0
        hq = [(0, s)]
        if route_restoration:
            parents = [None] * self.V
            parents[s] = s
        while hq:
            (dx, x) = heapq.heappop(hq)
            if dist[x] < dx:
                continue
            for (y, dy) in self.graph[x]:
                if dist[y] > dx + dy:
                    dist[y] = dx + dy
                    if route_restoration:
                        parents[y] = x
                    heapq.heappush(hq, (dist[y], y))
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Bellman_Ford(self, s, route_restoration=False):
        dist = [float('inf')] * self.V
        dist[s] = 0
        if route_restoration:
            parents = [s] * self.V
        for _ in range(self.V - 1):
            for (i, j, d) in self.edges:
                if dist[j] > dist[i] + d:
                    dist[j] = dist[i] + d
                    if route_restoration:
                        parents[j] = i
                if not self.directed and dist[i] > dist[j] + d:
                    dist[i] = dist[j] + d
                    if route_restoration:
                        parents[i] = j
        negative_cycle = []
        for (i, j, d) in self.edges:
            if dist[j] > dist[i] + d:
                negative_cycle.append(j)
            if not self.directed and dist[i] > dist[j] + d:
                negative_cycle.append(i)
        if negative_cycle:
            is_negative_cycle = [False] * self.V
            for i in negative_cycle:
                if is_negative_cycle[i]:
                    continue
                else:
                    queue = deque([i])
                    is_negative_cycle[i] = True
                    while queue:
                        x = queue.popleft()
                        for (y, d) in self.graph[x]:
                            if not is_negative_cycle[y]:
                                queue.append(y)
                                is_negative_cycle[y] = True
                                if route_restoration:
                                    parents[y] = x
            for i in range(self.V):
                if is_negative_cycle[i]:
                    dist[i] = -float('inf')
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Warshall_Floyd(self, route_restoration=False):
        dist = [[float('inf')] * self.V for i in range(self.V)]
        for i in range(self.V):
            dist[i][i] = 0
        if route_restoration:
            parents = [[j for j in range(self.V)] for i in range(self.V)]
        for (i, j, d) in self.edges:
            if dist[i][j] > d:
                dist[i][j] = d
                if route_restoration:
                    parents[i][j] = i
            if not self.directed and dist[j][i] > d:
                dist[j][i] = d
                if route_restoration:
                    parents[j][i] = j
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        if route_restoration:
                            parents[i][j] = parents[k][j]
        for i in range(self.V):
            if dist[i][i] < 0:
                for j in range(self.V):
                    if dist[i][j] != float('inf'):
                        dist[i][j] = -float('inf')
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Route_Restoration(self, s, g, parents):
        route = [g]
        while s != g and parents[g] != g:
            g = parents[g]
            route.append(g)
        route = route[::-1]
        return route

    def Kruskal(self):
        UF = UnionFind(self.V)
        sorted_edges = sorted(self.edges, key=lambda x: x[2])
        minimum_spnning_tree = []
        for (i, j, d) in sorted_edges:
            if not UF.Same(i, j):
                UF.Union(i, j)
                minimum_spnning_tree.append((i, j, d))
        return minimum_spnning_tree

    def Ford_Fulkerson(self, s, t):
        max_flow = 0
        residual_graph = [defaultdict(int) for i in range(self.V)]
        if self.weighted:
            for (i, j, d) in self.edges:
                if not d:
                    continue
                residual_graph[i][j] += d
                if not self.directed:
                    residual_graph[j][i] += d
        else:
            for (i, j) in self.edges:
                residual_graph[i][j] += 1
                if not self.directed:
                    residual_graph[j][i] += 1
        while True:
            parents = [None] * self.V
            parents[s] = s
            seen = [False] * self.V
            seen[s] = True
            queue = deque([s])
            while queue:
                x = queue.popleft()
                for y in residual_graph[x].keys():
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
                        parents[y] = x
                        if y == t:
                            tt = t
                            while tt != s:
                                residual_graph[parents[tt]][tt] -= 1
                                residual_graph[tt][parents[tt]] += 1
                                if not residual_graph[parents[tt]][tt]:
                                    residual_graph[parents[tt]].pop(tt)
                                tt = parents[tt]
                            max_flow += 1
                            break
                else:
                    continue
                break
            else:
                break
        return max_flow

    def BFS(self, s):
        seen = [False] * self.V
        seen[s] = True
        queue = deque([s])
        while queue:
            x = queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if not seen[y]:
                    seen[y] = True
                    queue.append(y)
        return

    def DFS(self, s):
        seen = [False] * self.V
        finished = [False] * self.V
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
            elif not finished[x]:
                finished[x] = True
        return
N = int(readline())
edges = []
parents = [0] + [p - 1 for p in list(map(int, readline().split()))]
for i in range(1, N):
    edges.append((i, parents[i]))
G = Graph(N, edges=edges)
mod = 10 ** 9 + 7
dp = [1] * N
postorder = G.SS_DFS(0, postorder=True)
for x in postorder:
    for y in G.graph[x]:
        if y == parents[x]:
            continue
        dp[x] *= 1 + dp[y]
        dp[x] %= mod
dp_ = [1] * N
for x in postorder[::-1]:
    lst = [y for y in G.graph[x] if y != parents[x]]
    l = len(lst)
    lst_l = [1] * (l + 1)
    lst_r = [1] * (l + 1)
    for i in range(1, l + 1):
        lst_l[i] = lst_l[i - 1] * (dp[lst[i - 1]] + 1) % mod
    for i in range(l - 1, -1, -1):
        lst_r[i] = lst_r[i + 1] * (dp[lst[i]] + 1) % mod
    for i in range(l):
        dp_[lst[i]] = dp_[x]
        dp_[lst[i]] *= lst_l[i] * lst_r[i + 1]
        dp_[lst[i]] += 1
        dp_[lst[i]] %= mod
ans_lst = [dp[x] * dp_[x] % mod for x in range(N)]
print(*ans_lst)