Chạy trốn khỏi chuồng

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.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$ ô cỏ nối nhau thành cây có gốc tại ô $1$ . Mỗi cạnh có độ dài $l_{i}$ . Bò chỉ di chuyển xa gốc (từ cha xuống con) và không chạy quá tổng quãng đường $L$ .

Với mỗi ô $i$ , đếm số ô có thể đến từ $i$ (bao gồm chính $i$ ) bằng cách di chuyển xa gốc với tổng quãng đường không quá $L$ .

Dữ liệu vào

Dòng $1$ : Hai số nguyên $N$ và $L$ ( $1 \leq N \leq 200000$ , $1 \leq L \leq 10^{18}$ ).
Dòng $2$ đến $N$ : Dòng $i$ gồm hai số nguyên $p_{i}$ và $l_{i}$ — cha của ô $i$ và độ dài cạnh ( $1 \leq p_{i} < i$ , $1 \leq l_{i} \leq 10^{12}$ ).

Dữ liệu ra

$N$ dòng, dòng $i$ là số ô có thể đến từ ô $i$ .

Ràng buộc

$1 \leq N \leq 200000$
$1 \leq L \leq 10^{18}$
$1 \leq l_{i} \leq 10^{12}$

Ví dụ

Input	Output	Giải thích
4 5 1 4 2 3 1 5	3 2 1 1	Từ ô 1: đến được ô 1, 2, 4 (ô 3 cách 7 > 5). Từ ô 2: đến được ô 2, 3.
10 48 1 57 2 29 2 33 4 1 3 49 1 33 2 53 7 53 4 41	2 4 1 3 1 1 1 1 1 1

Bình luận

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