P9128 [USACO23FEB] Fertilizing Pastures G

题目描述

有 $N$ 个顶点的树，经过节点之间的每一条边都需要 $1s$。每个顶点一开始的权值均为 $0$，第 $i$ 个点的权值的增长速率为 $a_i/s$。FJ 从 $1$ 号顶点出发遍历整棵树。当 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

5 0
1 1
1 2
3 1
3 4

8 21

输入输出样例 2

5 1
1 1
1 2
3 1
3 4

6 29