#P3089. [USACO23FEB] Fertilizing Pastures G

[USACO23FEB] Fertilizing Pastures G

题目描述

There are NN pastures (2N2105)(2 \le N \le 2 \cdot 10^5), connected by N1N−1 roads, such that they form a tree. Every road takes 11 second to cross. Each pasture starts out with 00 grass, and the ith pasture's grass grows at a rate of ai(1ai108)a_i (1 \le a_i \le 10^8) units per second. Farmer John is in pasture 11 at the start, and needs to drive around and fertilize the grass in every pasture. If he visits a pasture with xx units of grass, it will need xx amount of fertilizer. A pasture only needs to be fertilized the first time it is visited, and fertilizing a pasture takes 00 time.

The input contains an additional parameter T{0,1}T \in \{0,1\}.

  • If T=0T=0, Farmer John must end at pasture 11.
  • If T=1T=1, Farmer John may end at any pasture.

Compute the minimum amount of time it will take to fertilize every pasture and the minimum amount of fertilizer needed to finish in that amount of time.

输入格式

The first line contains NN and TT.

Then for each ii from 22 to NN, there is a line containing pip_i and aia_i, meaning that there is a road connecting pastures pip_i and ii. It is guaranteed that 1pi<i1 \le p_i<i.

输出格式

The minimum amount of time and the minimum amount of fertilizer, separated by spaces.

题目大意

有N个顶点的树,经过节点之间的每一条边都需要1s。每个顶点一开始的权值均为0,第i个点的权值的增长速率为a[i]/s。FJ从1号顶点出发遍历整棵树。当FJ走到某个节点时,若该节点的权值为x,则需要支出大小为x的费用。(当然,只需在第一次经过该节点时需要支出。)

给出一个参数T:

(i)若T=0,FJ必须回到1号节点

(ii)若T=1,FJ可以在任意节点结束他的遍历

求遍历所有节点的最小时间和此时需要付出的费用。

输入格式

第一行包括N和T。

第2行到第N行,包含两个整数p[i]和a[i],a[i]的含义见上文。p[i]则表示节点i和p[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

提示

Explanation for Sample 1

The optimal route for Farmer John is as follows:

  • At time 11, move to node 33, which now has 12=21 \cdot 2=2 grass and so needs 22 fertilizer.
  • At time 22, move to node 55, which now has 24=82 \cdot 4=8 grass and so needs 88 fertilizer.
  • At time 33, move back to node 33, which we already fertilized and so don't need to fertilize again.
  • At time 44, move to node 44, which now has 41=44 \cdot 1=4 grass and so needs 44 fertilizer.
  • At time 55, move back to node 33, which we already fertilized.
  • At time 66, move back to node 11.
  • At time 77, move to node 22, which now has 71=77 \cdot 1=7 grass and so needs 77 fertilizer.
  • At time 88, return to node 11.

This route takes 88 time and uses 2+8+4+7=212+8+4+7=21 fertilizer. It can be shown that 88 is the least possible amount of time for any route that returns to node 11 at the end and 2121 is the least possible fertilizer used for any route that returns to node 11 and takes 88 time.

Explanation for Sample 2

The optimal route for Farmer John is as follows:

  • At time 11, move to node 22, which now has 11=11 \cdot 1=1 grass and so needs 11 fertilizer.
  • At time 22, move back to node 11.
  • At time 33, move to node 33, which now has 32=63 \cdot 2=6 grass and so needs 66 fertilizer.
  • At time 44, move to node 55, which now has 44=164 \cdot 4=16 grass and so needs 1616 fertilizer.
  • At time 55, move back to node 33, which we already fertilized and so don't need to fertilize again.
  • At time 66, move to node 44, which now has 61=66 \cdot 1=6 grass and so needs 66 fertilizer.

This route takes 66 time and uses 1+6+16+6=291+6+16+6=29 fertilizer. It can be shown that 66 is the least possible amount of time for any route and 2929 is the least possible fertilizer used for any route that takes 66 time.

SCORING

  • Inputs 3103-10: T=0T=0
  • Inputs 112211-22: T=1T=1
  • Inputs 363-6 and 111411-14: No pasture is adjacent to more than three roads.