Skip to content

1138: 恶魔打工

题目

题目描述

本题可以使用STL。

大恶魔要去打工买好吃的给小恶魔吃,办公室的负责人看大恶魔似乎懂那么一点点算法,指着一棵树说:“这树现在是褐色的,给你一桶油漆给树染色,使得从树上特定节点出发到其他节点至多只有一条边是褐色的。有多少种染色方法呢?”。大恶魔发现自己的手指头不够数数,来求助聪明的你帮他计算方案数。

给出一个有n个节点的树,每个节点编号从1到n。初始状态下所有的边都是褐色的,可以将边染成红色。求对图上每一个点各自有多少种染色方法,使得以这个点作为起点到所有其他点的路径上各自至多只有一条褐色边。由于方案数可能很多,请输出方案数模1e9+7的结果。

输入格式

输入数据有2行。 第一行为一个整数n,代表树的节点数。 第二行有n-1个正整数$a_2, \cdots, a_n$,代表树上边的情况。$a_i$表示在$i$和$a_i$之间存在一条边。

输出格式

输出1行,共n个整数$s_i$。 其中$s_i$表示以$i$为起点情况下,满足条件的方案数。由于方案数可能很多,请输出方案数模1e9+7的结果。

样例输入

输入样例1

txt 5 1 1 3 3

输入样例2

txt 3 1 2

输入样例3

txt 5 1 2 1 1

样例输出

输出样例1

txt 10 6 12 7 7

输出样例2

txt 3 4 3

输出样例3

txt 12 10 6 7 7

数据范围

对100%的数据,$2\le n \le 1e5$, $1\le a_i \le i-1$。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!