Đường thẳng nhỏ nhất trên đường đi từ gốc

Buổi 30 — Persistent Segment Tree
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho cây gốc $1$ gồm $n$ đỉnh; đỉnh $i$ chứa đường thẳng $y=k_ix+b_i$. Mỗi truy vấn $(u,x)$: tìm giá trị nhỏ nhất của $k_wx+b_w$ trên mọi đỉnh $w$ nằm trên đường đi từ gốc $1$ đến $u$.

Dữ liệu vào

Dòng đầu: $n,q$. Tiếp theo $n$ dòng, dòng $i$ gồm $p_i,k_i,b_i$ ($p_1=0$, $p_i<i$ là cha của $i$). Sau đó $q$ dòng: $u,x$.

Dữ liệu ra

Với mỗi truy vấn in đáp án.

Ví dụ

Input

5 5

0 99 -32435
1 -39 337713
2 90 -238590
2 52 297313
3 89 -447924
4 1000000
4 981917
3 9
1 902116
1 598662

Output

-38662287
-37957050
-237780
89277049
59235103
Giới hạn
  • $1\le n,q\le 10^5$; $0\le x\le 10^6$; $|k_i|\le 10^6$; $|b_i|\le 10^{12}$.
  • Thời gian: 2 giây; bộ nhớ: 256 MB.
Draft saved