Имеется \(N\) пастбищ (\(2 \le N \le 2\cdot 10^5\)), соединённых \(N-1\) дорогой,
так что ои образуют дерево. Перемещение по каждой дороге занимает одну секунду.
В начале на каждом пастбище 0 травы, трава на \(i\)-ом пастбище растёт со скоростью
\(a_i\) (\(1\le a_i\le 10^8\)) единиц в секунду. Фермер Джон вначале находится в пастбище 1
и должен удобрить траву на каждом пастбище. Если он посещает пастбище, в котором
\(x\) единиц травы, он должен потратить \(x\) единиц удобрений. Удобрять требуется
только при первом посещении пастбища и удобрение пастбища занимает 0 единиц времени.
Ввод содержит дополнительный параметр \(T\in \{0,1\}\).
- Если \(T=0\), ФД должен завершить путь в пастбище 1.
- Если \(T=1\), ФД может завершить путь в любом пастбище.
Вычислите минимальное количество времени, которое требуется ФД, чтобы удобрить все пастбища
и минимальное количество удобрений, которое потребуется, чтобы закончить в этот момент времени.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит
\(N\) и
\(T\).
Затем для каждого \(i\) от \(2\) до \(N\), имеется строка содержащая \(p_i\) и \(a_i\),
означающая что есть дорога соединяющая пастбища \(p_i\) и \(i\). Гарантируется, что
\(1\le p_i<i\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Минимальное количество времени и минимальное количество удобрений, разделённые одиночным пробелом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 0
1 1
1 2
3 1
3 4
|
8 21
|