Bessie đang đi trượt tuyết cùng bạn bè. Ngọn núi có \(N\) điểm mốc (\(1\leq N\leq 10^5\)), được đánh số \(1,2,\ldots,N\) theo thứ tự độ cao tăng dần (điểm mốc \(1\) nằm dưới chân núi).

Với mỗi điểm mốc \(i>1\), có một đường trượt bắt đầu tại điểm mốc \(i\) và kết thúc tại điểm mốc \(p_i\) (\(1\le p_i<i\)). Đường trượt này có độ khó \(d_i\) (\(0\leq d_i\leq 10^9\)) và độ thú vị \(e_i\) (\(0\leq e_i\leq 10^9\)).

Mỗi người trong số \(M\) người bạn của Bessie (\(1\leq M\leq 10^5\)) sẽ làm như sau: họ chọn một điểm mốc ban đầu \(i\), rồi đi theo các đường trượt xuống dưới (đến \(p_i\), rồi đến \(p_{p_i}\), v.v.) cho tới khi đến điểm mốc \(1\).

Độ thú vị mà mỗi người nhận được bằng tổng độ thú vị của các đường trượt họ đi qua. Mỗi người cũng có một trình độ kỹ năng \(s_j\) (\(0\leq s_j\leq 10^9\)) và mức độ can đảm \(c_j\) (\(0\leq c_j\leq 10\)) khác nhau; vì thế họ chỉ được chọn điểm mốc ban đầu sao cho hành trình có nhiều nhất \(c_j\) đường trượt có độ khó lớn hơn \(s_j\).

Với mỗi người bạn, hãy tính độ thú vị lớn nhất họ có thể nhận được.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Tiếp theo, với mỗi \(i\) từ \(2\) đến \(N\), có một dòng chứa ba số nguyên cách nhau bởi dấu cách \(p_i\), \(d_i\), \(e_i\).

Dòng tiếp theo chứa \(M\).

\(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(s_j\) và \(c_j\).

Dữ liệu ra

In ra \(M\) dòng, mỗi dòng là đáp án của một người bạn.

Lưu ý rằng các số nguyên lớn trong bài này có thể đòi hỏi kiểu số nguyên 64-bit (chẳng hạn long long trong C/C++).

Ví dụ

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

Phân nhóm

• Dữ liệu 2–4: \(N,M\le 1000\).
• Dữ liệu 5–7: Mọi \(c_j=0\).
• Dữ liệu 8–17: Không có ràng buộc bổ sung.

Đề bài: Brandon Wang.

Nguồn

USACO 2025 US Open Contest, Silver — Ski Slope: https://usaco.org/index.php?page=viewproblem2&cpid=1520