USACO 2023 February Contest, Gold, Fertilizing Pastures
Xem PDFCó \(N\) đồng cỏ \((2\leq N\leq2*10^5)\), được nối với nhau bởi \(N-1\) con đường, sao cho chúng tạo thành một cây. Mỗi con đường mất \(1\) giây để vượt qua. Mỗi đồng cỏ ban đầu không có cỏ và cỏ của đồng cỏ thứ \(i\) phát triển với tốc độ \(a_i(1\leq a_i\leq10^8)\) đơn vị mỗi giây. Lúc đầu, nông dân John ở đồng cỏ 1 và cần phải lái xe vòng quanh để bón phân cho cỏ ở mọi đồng cỏ. Nếu anh ta đến thăm một đồng cỏ có \(x\) đơn vị cỏ thì sẽ cần \(x\) lượng phân bón. Đồng cỏ chỉ cần được bón phân trong lần đầu tiên đến và việc bón phân không mất thời gian.
Đầu vào chứa tham số \(T\in{0,1}\):
- Nếu \(T=0\), nông dân John phải kết thúc ở đồng cỏ \(1\).
- Nếu \(T=1\), nông dân John có thể kết thúc ở bất kỳ đồng cỏ nào.
Tính thời gian tối thiểu cần thiết để bón phân cho tất cả đồng cỏ và lượng phân bón tối thiểu cần với khoảng thời gian đó.
Input
- Dòng đầu tiên chứa số \(N\) và \(T\).
- Với mỗi dòng \(i\) từ \(2\) đến \(N\), có hai số \(p_i\) và \(a_i\) miêu tả một con đường. Đảm bảo rằng \(1 \leq p_i < i\).
Output
Lượng thời gian tối thiểu và lượng phân bón tối thiểu, cách nhau bằng khoảng trống.
Scoring
- Subtask \(1\): \(T=0\)
- Subtask \(2\): \(T=1\)
- Subtask \(3\): Không có đồng cỏ nào nối với hơn \(3\) con đường.
Example
Test 1
Input
5 0
1 1
1 2
3 1
3 4
Output
8 21
Note
Lộ trình tối ưu cho như sau:
- Tại thời điểm \(1\), di chuyển đến đỉnh \(3\), lúc này có \(1*2=2\) cỏ nên cần \(2\) phân bón.
- Tại thời điểm \(2\), di chuyển đến đỉnh \(5\), lúc này có \(2*4=8\) cỏ nên cần \(8\) phân bón.
- Tại thời điểm \(3\), di chuyển đến đỉnh \(3\) đã được bón phân.
- Tại thời điểm \(4\), di chuyển đến đỉnh \(4\), lúc này có \(4*1=4\) cỏ nên cần \(4\) phân bón.
- Tại thời điểm \(5\), di chuyển đến đỉnh \(3\) đã được bón phân.
- Tại thời điểm \(6\), di chuyển đến đỉnh \(1\).
- Tại thời điểm \(7\), di chuyển đến đỉnh \(2\), lúc này có \(7*1=4\) cỏ nên cần \(7\) phân bón.
- Tại thời điểm \(8\), di chuyển đến đỉnh \(1\).
Lộ trình này mất \(8\) giây và sử dụng \(2+8+4+7=21\) phân bón. Có thể chỉ ra rằng \(8\) giây là khoảng thời gian ít nhất cần và \(21\) là lượng phân bón ít nhất cần cho bất kỳ tuyến đường nào quay trở lại nút \(1\) và mất \(8\) giây.
Test 2
Input
5 1
1 1
1 2
3 1
3 4
Output
6 29
Note
Lộ trình tối ưu cho như sau:
- Tại thời điểm \(1\), di chuyển đến đỉnh \(2\), lúc này có \(1*1=2\) cỏ nên cần \(2\) phân bón.
- Tại thời điểm \(2\), di chuyển đến đỉnh \(1\).
- Tại thời điểm \(3\), di chuyển đến đỉnh \(3\), lúc này có \(3*2=6\) cỏ nên cần \(6\) phân bón.
- Tại thời điểm \(4\), di chuyển đến đỉnh \(5\), lúc này có \(4*4=16\) cỏ nên cần \(16\) phân bón.
- Tại thời điểm \(5\), di chuyển đến đỉnh \(3\) đã được bón phân.
- Tại thời điểm \(6\), di chuyển đến đỉnh \(4\), lúc này có \(6*1=4\) cỏ nên cần \(6\) phân bón.
Lộ trình này mất \(6\) giây và sử dụng \(1+6+16+6=29\) phân bón. Có thể chỉ ra rằng \(6\) giây là khoảng thời gian ít nhất cần và \(29\) là lượng phân bón ít nhất cần cho bất kỳ tuyến đường mất \(6\) giây.
Bình luận