背景

真人真事

描述

一首经过精心排版过的诗能给这个星球上的所有智慧生物极大的精神伤害。

一首诗包含了若干个句子,对于一些连续的短句,可以把他们用单个空格隔开​并放在一行中,一行中可以放的句子数目是没有限制的。行的长度定义为一行中符号的总个数。每首诗都有一个事先确定好的行标准长度L与一个正整数P。一般来说,诗人们都希望排版后每行的长度都和标准长度相差不远。一个通行的标准是,定义每行的不协调度为这行的实际长度与行标准长度L的差的P次方的绝对值,定义一个排版的不协调度为每行的不协调度之和。诗人们总希望采用不协调度最小的排版。

500年前,吟游诗人GTK凭借惊人的文学素养和强大的排版能力横行天下。

500年后,诗坛升起了一颗新星,人们都称他为小W。小W拥有比GTK更加卓越的文学天赋,更可怕的是,小W异常的高产。他往往一口气就能创作出一大批的诗句,然后给它们选择一个相同的L与P,最后再找出其中最容易排版的一首。

500年间,不少文学爱好者已经掌握了GTK的排版技术。诗坛并不乏小W一样的高产者,但他们在同小W的较量中,不是因为文学素养不够而落败,就是因为没能快速的进行排版而出局。很显然,小W已经掌握了更加先进的排版技术。小W的粉丝小F找到了你,希望你能破解他排版的秘密。

小W每一次创作出来的诗可以看成一棵n个结点的有根树,结点编号为1-n。1号结点是根,1号结点以外的点都代表了一个短句。每一条从1号结点到某个叶子的路径都对应小W创作出的一首诗,这首诗由这条路径经过的短句顺次连接而成。给定这样的一棵树,小F希望你找出其中排版后不协调度最低的那首诗,输出这个不协调度。

输入格式

第一行,三个整数n,P,L。

接下来有n-1行,第i行描述了i号结点的信息,包含两个正整数,分别是i号结点对应短句的长度与i号结点的父亲编号。

输出格式

若最小的不协调度不超过10^18,则输出这个数。

否则输出"JiuZheYangLe"(不包含引号)。

样例输入

11 3 9
1 1
2 2
3 3
4 4
5 5
1 1
3 7
3 8
3 9
3 10

样例输出

2

数据范围与约定

  • 对于50%的数据:给出的树是一条链,即小W这次只创作出了一首诗,虽然实际情况中这是不可能的= =
  • 对于100%的数据:n<=100000,每个短句的长度不超过300,1<=P<=4,0<=L<=10000。

样例解释

样例中包含两首诗,短句长度分别是(1,2,3,4,5)与(1,3,3,3,3)。

两首诗各自最优的排版分别是((1,2,3),(4,5))与((1,3,3),(3,3)).

来源

真人真事

因为很重要所以要说两遍。