Bón Phân Đồng Cỏ

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ đồng cỏ được nối bởi $N - 1$ con đường tạo thành một cây. Mỗi con đường tốn 1 giây để đi qua. Đồng cỏ $i$ có cỏ mọc với tốc độ $a_{i}$ đơn vị/giây (ban đầu tất cả bằng 0). Nông dân John bắt đầu tại đồng cỏ 1 và phải thăm tất cả các đồng cỏ để bón phân. Khi đến đồng cỏ có $x$ đơn vị cỏ, anh cần $x$ đơn vị phân bón (chỉ cần bón lần đầu thăm).

Tham số $T$ xác định FJ phải quay về đồng cỏ 1 ( $T = 0$ ) hay được kết thúc ở bất kỳ đâu ( $T = 1$ ).

Hãy tìm thời gian tối thiểu và lượng phân bón tối thiểu cho thời gian đó.

Dữ liệu vào

Dòng 1: Hai số nguyên $N$ và $T$ ( $2 \leq N \leq 2 \cdot 10^{5}$ , $T \in {0, 1}$ ).
Dòng $i$ ( $2 \leq i \leq N$ ): Hai số nguyên $p_{i}$ và $a_{i}$ ( $1 \leq p_{i} < i$ , $1 \leq a_{i} \leq 10^{8}$ ) — cha của đỉnh $i$ và tốc độ mọc cỏ.

Dữ liệu ra

Hai số nguyên cách nhau bởi dấu cách: thời gian tối thiểu và lượng phân bón tối thiểu cho thời gian đó.

Ràng buộc

$2 \leq N \leq 2 \cdot 10^{5}$
$T \in {0, 1}$
$1 \leq a_{i} \leq 10^{8}$

Ví dụ

Input	Output	Giải thích
5 0 1 1 1 2 3 1 3 4	8 21	Phải quay về gốc. DFS tối ưu tốn $2 (N - 1) = 8$ giây. Sắp xếp thứ tự thăm con tối ưu cho phân bón tổng 21.
5 1 1 1 1 2 3 1 3 4	6 29	Không cần quay về. Tiết kiệm được đường đi dài nhất, tổng 6 giây, phân bón 29.

Bình luận

Không có bình luận tại thời điểm này.