Fertilizing Pastures

【题目描述】

有 $N$ 个牧场，编号 $1 \sim N$，由 $N-1$ 条双向道路连接，构成一棵树。

每条道路的经过时长均为 $1$ 秒。

初始时，所有牧场中的草量均为 $0$。

第 $i$ 个牧场的草以每秒 $a_i$ 单位的速度生长。

农夫约翰一开始位于 $1$ 号牧场，他需要来回奔波，给每个牧场的草施肥。

当他到达某一牧场时，如果该牧场有 $x$ 单位的草，则他需要给该牧场施 $x$ 单位的肥。

每个牧场只需要在第一次抵达时施肥，施肥时间忽略不计。

输入包含一个附加参数 $T \in \{0,1\}$。

如果 $T=0$，表示约翰最后必须回到牧场 $1$，才算施肥结束。

如果 $T=1$，表示约翰最后不必回到牧场 $1$，他可以在任何牧场结束施肥。

请你计算给所有牧场施肥所需要的最短时间以及在该时间内完成工作所需的最少肥料量。

【输入格式】

第 $1$ 行：包含整数 $N$ 和 $T$。

第 $2 \sim N$ 行：第 $i$ 行包含 $p_i$ 和 $a_i$，表示牧场 $p_i$ 和牧场 $i$ 之间存在一条道路，牧场 $i$ 的长草速度为每秒 $a_i$ 单位。

【输出格式】

共一行，输出给所有牧场施肥所需要的最短时间以及在该时间内完成工作所需的最少肥料量。

【样例1输入】

5 0
1 1
1 2
3 1
3 4

【样例1输出】

8 21

【样例1解释】

农夫约翰的最优路线如下：

第 $1$ 秒，前往牧场 $3$，其中包含 $1 \times 2 = 2$ 单位草，因此需要施 $2$ 单位肥。

第 $2$ 秒，前往牧场 $5$，其中包含 $2 \times 4 = 8$ 单位草，因此需要施 $8$ 单位肥。

第 $3$ 秒，回到牧场 $3$，无需再次施肥。

第 $4$ 秒，前往牧场 $4$，其中包含 $4 \times 1 = 4$ 单位草，因此需要施 $4$ 单位肥。

第 $5$ 秒，回到牧场 $3$，无需再次施肥。

第 $6$ 秒，回到牧场 $1$，这里注意，由于一开始位于牧场 $1$，因此再次回到牧场 $1$ 无需施肥。

第 $7$ 秒，前往牧场 $2$，其中包含 $7 \times 1 = 7$ 单位草，因此需要施 $7$ 单位肥。

第 $8$ 秒，回到牧场 $1$，施肥结束。

一共花费时间为 $8$ 秒，需要肥料为 $2+8+4+7=21$ 单位。

在最终需要回到牧场 $1$ 的前提下，没有比 $8$ 秒更短的路线。

在 $8$ 秒内完成工作的前提下，至少需要 $21$ 单位肥料。

【样例2输入】

5 1
1 1
1 2
3 1
3 4

【样例2输出】

6 29

【样例2解释】

农夫约翰的最优路线如下：

第 $1$ 秒，前往牧场 $2$，其中包含 $1 \times 1 = 1$ 单位草，因此需要施 $1$ 单位肥。

第 $2$ 秒，回到牧场 $1$，这里注意，由于一开始位于牧场 $1$，因此再次回到牧场 $1$ 无需施肥。

第 $3$ 秒，前往牧场 $3$，其中包含 $3 \times 2 = 6$ 单位草，因此需要施 $6$ 单位肥。

第 $4$ 秒，前往牧场 $5$，其中包含 $4 \times 4 = 16$ 单位草，因此需要施 $16$ 单位肥。

第 $5$ 秒，回到牧场 $3$，无需再次施肥。

第 $6$ 秒，前往牧场 $4$，其中包含 $6 \times 1 = 6$ 单位草，因此需要施 $6$ 单位肥。

一共花费时间为 $6$ 秒，需要肥料为 $1+6+16+6=29$ 单位。

没有比 $6$ 秒更短的路线，在 $6$ 秒内完成工作的前提下，至少需要 $29$ 单位肥料。

【样例3/4】

点击下载样例3/4

【数据规模与约定】

测试点 $1 \sim 8$：$T=0$

测试点 $9 \sim 20$：$T=1$

测试点 $1 \sim 4$ 和 $9 \sim 12$：没有牧场毗邻三条以上的道路。

全部数据，满足：$2 \le N \le 2 \times 10^5,0 \le T \le 1,1 \le p_i \lt i,1 \le a_i \le 10^8$