#P4974. 毒瘤之神秘通道

毒瘤之神秘通道

题目背景

Viston就是一个小蒟蒻 By CYJian(自己YY出来的)
Viston最喜欢冒险了。

题目描述

(假的算法标签) Viston发现了一个巨大的城堡,他走了进去,城堡里有一个巨大的房间,Viston进去打算参观参观,然后.......他就被困在里面了。 Viston发现了在房间里有很多同样冒险者和一个个通道,冒险者们一个个冲向了不同的通道,而Viston一脸懵逼。

Viston动用他莫大的蒟蒻之力摸清了这些通道是什么东东厉害吧,他们是一些单向通道,而这些通道会把你传送到另一些房间里,一个房间里有一个传送到另一个房间里的传送门。

已知所有的房间最后都通向一个地方,那就是出口。但传送门把你传送到另一个房间也是需要时间的,这个时间取决于之前有多少人使用过这个传送门,计算公式是

$$T=M$$,其中$M$表示传送门的使用人数。 ~~(你前面发啥呆啊,其他人早走光了。)~~ Viston记得每个通道有多少人进入,也探测出了每个房间里的传送门通向哪里,他想知道他从哪个通道进入初始房间才能最快的到达出口,~~毕竟Viston还想着颓金拱门呢。~~ ### 注意:只有使用传送门消耗时间,而通道(即到达初始房间)不消耗时间!!! ## 输入格式 第一行输入两个整数$M$,$N$,其中$M$表示有多少个房间(编号为$1-M$),$N$表示有多少个初始的通道。 接下来的$2-------M+1$行,每行输入一个整数$P$,表示第$i$个房间通过一个传送门通向哪个房间,其中$0$号节点表示出口。数据保证是一棵树。 第$M+2-------M+N+1$行,每行输入两个整数$A,B$,表示这个**通道**通向房间$A$,之前有$B$个人进入其中。 ### 不同**通道**可能通向相同房间。 ## 输出格式 输出只有一行,$c,d$其中$c$表示Viston选择通过通道到达**哪个**初始房间所需时间最短,$d$表示需要多少时间。 当然,如果有多个初始房间时间最短,就输出编号最大的**通道**通向的初始房间.. ```input1 5 2 0 1 2 2 4 5 10 3 10 ``` ```output1 3 50 ``` ## 提示 ## 样例解释 (用的WindowsXP画图画的不好请见谅) ![](https://i.loli.net/2018/10/05/5bb7632fb40f4.jpg) 对于1-5号测试点(10 pts): $1 \leq N, M \leq 50$ 对于6-10号测试点(20 pts): $1 \leq N, M \leq 5000$ 对于11-15号测试点(30 pts): $1 \leq N, M \leq 100000$ 对于16-20号测试点(40 pts): $1 \leq N, M \leq 1000000$ 对于5,10,15,20号测试点,给定的树为随机生成。 保证答案都在long long范围内.. $\color{white}\text{这样你才能看出来随机树强度有多低}$ @[Viston](https://www.luogu.org/space/show?uid=107101) $\color{white}\text{(还想卡树剖的)}$ $$