1994: [USACO 2023 February Contest Gold] Problem 2. Fertilizing Pastures

文件提交：无需freopen 内存限制：256 MB 时间限制：2.000 S
评测方式：普通裁判 命题人：
提交：1 解决：1

题目描述

There are N pastures (2≤N≤2⋅105), connected by N−1 roads, such that they form a tree. Every road takes 1 second to cross. Each pasture starts out with 0 grass, and the ith pasture's grass grows at a rate of ai (1≤ai≤108) units per second. Farmer John is in pasture 1 at the start, and needs to drive around and fertilize the grass in every pasture. If he visits a pasture with x units of grass, it will need x amount of fertilizer. A pasture only needs to be fertilized the first time it is visited, and fertilizing a pasture takes 0 time.

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

  • If T=0, Farmer John must end at pasture 1.
  • If T=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 N and T.

Then for each i from 2 to N, there is a line containing pi and ai, meaning that there is a road connecting pastures pi and i. It is guaranteed that 1≤pi<i.

输出

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

样例输入 

5 0
1 1
1 2
3 1
3 4

样例输出 

8 21

提示

The optimal route for Farmer John is as follows:

  • At time 1, move to node 3, which now has 1⋅2=2 grass and so needs 2 fertilizer.
  • At time 2, move to node 5, which now has 2⋅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⋅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⋅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.

SAMPLE INPUT:

5 1

1 1

1 2

3 1

3 4

SAMPLE OUTPUT:

6 29

The optimal route for Farmer John is as follows:

  • At time 1, move to node 2, which now has 1⋅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⋅2=6 grass and so needs 6 fertilizer.
  • At time 4, move to node 5, which now has 4⋅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⋅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.

来源/分类

提交提交记录统计露一手!
codingfuture is powered by HUSTOJ, Theme by SYZOJ