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 可以在任意节点结束他的遍历**。 求遍历所有节点的最小时间和此时需要付出的最小的费用。

无

无

### Explanation for Sample 1 The optimal route for Farmer John is as follows: - At time $1$, move to node $3$, which now has $1 \cdot 2=2$ grass and so needs $2$ fertilizer. - At time $2$, move to node $5$, which now has $2 \cdot 4=8$ grass and so needs $8$ fertilizer. - At time $3$, move back to node $3$, which we already fertilized and so don't need to fertilize again. - At time $4$, move to node $4$, which now has $4 \cdot 1=4$ grass and so needs $4$ fertilizer. - At time $5$, move back to node $3$, which we already fertilized. - At time $6$, move back to node $1$. - At time $7$, move to node $2$, which now has $7 \cdot 1=7$ grass and so needs $7$ fertilizer. - At time $8$, return to node $1$. This route takes $8$ time and uses $2+8+4+7=21$ fertilizer. It can be shown that $8$ is the least possible amount of time for any route that returns to node $1$ at the end and $21$ is the least possible fertilizer used for any route that returns to node $1$ and takes $8$ time. ### Explanation for Sample 2 The optimal route for Farmer John is as follows: - At time $1$, move to node $2$, which now has $1 \cdot 1=1$ grass and so needs $1$ fertilizer. - At time $2$, move back to node $1$. - At time $3$, move to node $3$, which now has $3 \cdot 2=6$ grass and so needs $6$ fertilizer. - At time $4$, move to node $5$, which now has $4 \cdot 4=16$ grass and so needs $16$ fertilizer. - At time $5$, move back to node $3$, which we already fertilized and so don't need to fertilize again. - At time $6$, move to node $4$, which now has $6 \cdot 1=6$ grass and so needs $6$ fertilizer. This route takes $6$ time and uses $1+6+16+6=29$ fertilizer. It can be shown that $6$ is the least possible amount of time for any route and $29$ is the least possible fertilizer used for any route that takes $6$ time. ### SCORING - Inputs $3-10$: $T=0$ - Inputs $11-22$: $T=1$ - Inputs $3-6$ and $11-14$: No pasture is adjacent to more than three roads.