Đường thẳng nhỏ nhất trên đường đi từ gốc
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Đề 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.
Community Discussion