本题使用标准输入、标准输出，无需读写题面中提到的文件。

题目描述

有 $N$ 个牧场（$2 \le N \le 2\cdot 10^5$），由 $N-1$ 条道路连接，构成一棵树。穿过每条道路需要 1 秒。每个牧场初始有 0 单位的草，第 $i$ 个牧场的草以每秒 $a_i$（$1\le a_i\le 10^8$）单位的速度生长。

农夫 John 在开始时位于牧场 1，他需要开车四处走动并给每个牧场的草施肥。如果他访问某个牧场时该牧场有 $x$ 单位的草，那么需要 $x$ 单位的肥料。一个牧场只需要在第一次被访问时施肥，且施肥耗时为 0。

输入中还有一个额外参数 $T\in \{0,1\}$。 如果 $T=0$，农夫 John 必须最终回到牧场 1。 如果 $T=1$，农夫 John 可以最终停在任意牧场。

请计算：施肥完所有牧场所需的最短时间，以及在达到该最短时间的前提下所需的最少肥料量。

输入格式

第一行包含 $N$ 和 $T$。 接下来对每个 $i$（从 $2$ 到 $N$），有一行包含 $p_i$ 和 $a_i$，表示有一条道路连接牧场 $p_i$ 与牧场 $i$。保证 $1\le p_i<i$。

输出格式

输出最短时间与最少肥料量，用空格分隔。

5 0
1 1
1 2
3 1
3 4

8 21

5 1
1 1
1 2
3 1
3 4

6 29

提示

农夫 John 的最优路线如下： 在时间 $1$，移动到节点 $3$，此时它有 $1 \cdot 2 = 2$ 单位草，因此需要 $2$ 单位肥料。 在时间 $2$，移动到节点 $5$，此时它有 $2 \cdot 4 = 8$ 单位草，因此需要 $8$ 单位肥料。 在时间 $3$，移动 回到节点 $3$，我们已经施过肥，因此不需要再次施肥。 在时间 $4$，移动到节点 $4$，此时它有 $4 \cdot 1 = 4$ 单位草，因此需要 $4$ 单位肥料。 在时间 $5$，移动回节点 $3$， 我们已经施过肥。 在时间 $6$，移动回节点 $1$。 在时间 $7$，移动到节点 $2$，此时它有 $7 \cdot 1 = 7$ 单位草 因此需要 $7$ 单位肥料。 在时间 $8$，返回节点 $1$。 该路线耗时 $8$，并使用了 $2 + 8 + 4 + 7 = 21$ 单位肥料。可以证明：对于任何最终回到节点 $1$ 的路线，$8$ 是可能的最短时间；并且在所有耗时 $8$ 且最终回到节点 $1$ 的路线中，$21$ 是最少的肥料用量。

农夫 John 的最优路线如下： 在时间 $1$，移动到节点 $2$，此时它有 $1 \cdot 1 = 1$ 单位草，因此 需要 $1$ 单位肥料。 在时间 $2$，移动回节点 $1$。 在时间 $3$，移动到节点 $3$，此时它有 $3 \cdot 2 = 6$ 单位草，因此需要 $6$ 单位肥料。 在时间 $4$，移动到节点 $5$，此时它有 $4 \cdot 4 = 16$ 单位草，因此需要 $16$ 单位肥料。 在时间 $5$， 移动回节点 $3$，我们已经施过肥，因此不需要 再次施肥。 在时间 $6$，移动到节点 $4$，此时它有 $6 \cdot 1 = 6$ 单位草，因此需要 $6$ 单位肥料。 该路线耗时 $6$，并使用了 $1 + 6 + 16 + 6 = 29$ 单位肥料。可以证明：对于任何路线，$6$ 是可能的最短时间；并且在所有耗时 $6$ 的路线中，$29$ 是最少的肥料用量。

评分： 输入 3-10：$T=0$ 输入 11-22：$T=1$ 输入 3-6 和 11-14：任意牧场的相邻道路数不超过三条。 题目鸣谢：Rohin Garg

来源

USACO|2023|Gold