P9128 [USACO23FEB] Fertilizing Pastures G

有 $N$ 个顶点的树，经过节点之间的每一条边都需要 $1s$。每个顶点一开始的权值均为 $0$，第 $i$ 个点的权值每秒增长 $a_i$。FJ 从 $1$ 号顶点出发遍历整棵树，此时为时刻 $0$。当 FJ 走到某个节点时，若该节点的权值为 $x$，则需要支出大小为 $x$ 的费用。（当然，只需在第一次经过该节点时需要支出。） 给出一个参数 $T$: + **若 $T=0$，FJ 必须回到 $1$ 号节点**。 + **若 $T=1$，FJ 可以在任意节点结束他的遍历**。 求遍历所有节点的最小时间和此时需要付出的最小的费用。

第一行包括 $N$ 和 $T$。 第 $2$ 行到第 $N$ 行，包含两个整数 $p_i$ 和 $a_i$,$a_i$ 的含义见上文。$p_i$ 则表示节点 $i$ 和 $p_i$ 之间有一条边相连。

两个整数：遍历所有节点的最小时间和此时需要付出的最小的费用。 $2 \le N \le 2 \times 10^5,T \in \{0,1\},1 \le a_i \le 10^8, 1 \le p_i < i$。

#### 样例 1 解释 农夫约翰的最优路线如下： - 在时间 $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$ 是可能达到的最小费用。 --- #### 样例 2 解释 农夫约翰的最优路线如下： - 在时间 $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 \sim 10$：$T=0$ - 测试点 $11 \sim 22$：$T=1$ - 测试点 $3 \sim 6$ 和 $11 \sim 14$：不存在度数超过 $3$ 的节点。