Dốc Trượt Tuyết

Đ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

Một ngọn núi có $N$ điểm dừng chân đánh số từ $1$ đến $N$ theo thứ tự tăng dần độ cao. Mỗi điểm $i > 1$ có một đường trượt tuyết đến điểm $p_{i}$ ( $p_{i} < i$ ) với độ khó $d_{i}$ và mức vui $e_{i}$ .

Có $M$ người bạn muốn trượt tuyết. Mỗi người bắt đầu tại một điểm và trượt xuống qua các đường cho đến khi đến điểm 1. Người thứ $j$ có kỹ năng $s_{j}$ và lòng can đảm $c_{j}$ : họ chỉ được đi tối đa $c_{j}$ đường có $d_{i} > s_{j}$ .

Tìm tổng mức vui lớn nhất cho mỗi người.

Dữ liệu vào

Dòng 1: Số nguyên $N$ .
$N - 1$ dòng tiếp theo (cho $i$ từ $2$ đến $N$ ): Ba số nguyên $p_{i}$ , $d_{i}$ , $e_{i}$ .
Dòng tiếp: Số nguyên $M$ .
$M$ dòng tiếp: Hai số nguyên $s_{j}$ , $c_{j}$ .

Dữ liệu ra

$M$ dòng, mỗi dòng là tổng mức vui tối đa.

Ràng buộc

$1 \leq N \leq 10^{5}$
$1 \leq M \leq 10^{5}$
$0 \leq d_{i}, e_{i}, s_{j} \leq 10^{9}$
$0 \leq c_{j} \leq 10$

Ví dụ

Input	Output	Giải thích
4 1 20 200 2 30 300 2 10 100 8 19 0 19 1 19 2 20 0 20 1 20 2 29 0 30 0	0 300 500 300 500 500 300 500	Với $s = 19, c = 0$ : không thể đi đường nào (tất cả quá khó), mức vui = 0. Với $s = 19, c = 1$ : có thể đi 1 đường khó, tốt nhất là đường có $e = 300$ .

Bình luận

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