OI题库

【题目描述】

森林中生长着许多奇特的果树，它们不仅外形独特，其果实更是可口。这天，两只小虫Nileh和Nixed决定一起分享一颗果树。他们从早晨一直辛勤工作到下午，终于把这颗果树锯倒。他们观察着这颗果树，果树开始端是露出地面的根部，接着像其他果树一样，有着诸多分叉（如图所示就是一颗果树），在每个分叉处生长着果实，自然Nileh和Nixed的食物就是这些果实了！他们准备把果树分成两部分，每个虫虫得到各自的一部分，而分果树的方法就是选择一个分叉点，虫虫将他们咬断（自然分叉点上的果实也被扔掉了），这样果树就变成了两个部分（每个部分不一定是连在一起的）：分叉点上面的部分和分叉点下面的部分。Nileh和Nixed就会各自选一个部分吃啦！比如对于左边这颗果树，如果他们咬掉蓝色的果子，那么就被分为红色和黄色的两个部分。

考虑到被咬掉的果子会被浪费，他们想尽可能的减少浪费，于是虫虫给每个果子一个美味值，对于每个果子，他们决定计算如果咬掉这个果子，上面部分、下面部分和从树根到这个分叉点的路径中比这个果子更美味的果子各有多少个。他们以此来选择最终要被咬掉的果子是哪一个。遗憾的是果树可能很庞大，而小虫几乎是不会计算的，身为程序员的你帮帮他们吧。

【输入格式】

输入文件第一行一个整数n（n<=10^5）表示树的分叉数（包括树根）。

输入文件的第i(2<=i<=n)行一个数pi，表示分叉i的上一级分叉的编号（pi<i）。（1号分叉即树根，它没有上级分叉点）

输入文件的第n+i(1<=i<=n)行一个正整数ai，表示生长在i号分叉点上的果实的美味值。（每个果子的美味值不相等）

【输出格式】

输出共n行，每行三个数，分别表示咬掉第i个果实后上面部分、下面部分、从树根到这个分叉点的路径中比它美味的果实数。

【样例输入】

4

1

1

2

2

4

1

3

【样例输出】

2 0 0

0 0 0

0 3 1

0 1 1

【来源】

ZJOI 2004 Day 3