Cho một đồ thị vô hướng liên thông \(n\) đỉnh và \(n - 1\) cạnh, các đỉnh đánh số từ 1 đến \(n\). Mỗi cạnh của đồ thị được gán một giá trị nguyên dương được gọi là trọng số của cạnh.

Một đường đi đơn từ đỉnh \(u\) đến đỉnh \(v\) là dãy \(u = x_{1}x_{2}\ldots x_{k} = v\) trong đó \(\left( x_{i},\ x_{i + 1} \right)\ i = 1 \div (k - 1)\) là các cạnh của đồ thị và ngoài ra \(x_{i}
eq x_{j}\forall\ i
eq j\). Giá trị của đường đi trên là:

\[\min\left\{ L\left( x_{i},\ x_{i + 1} \right)\ :i = 1,2,\ldots,k - 1 \right\}\ \]

Ở đây \(L(x_{i},\ x_{i + 1})\) là trọng số của cạnh \((x_{i},\ x_{i + 1})\)

Yêu cầu: Trả lời \(Q\) câu hỏi, mỗi câu hỏi được mô tả bởi hai số nguyên \(k,\ v\) với ý nghĩa: Đếm xem có bao nhiêu đỉnh \(\mathbf{u}\) của đồ thị mà có trọng số của đường đi đơn từ \(\mathbf{u}\) đến \(\mathbf{v}\) lớn hơn hoặc bằng \(\mathbf{k}\)?

Dữ liệu vào:

• Dòng thứ nhất chứa hai số nguyên \(n,\ Q\ (1 \leq n,\ Q \leq 10^{5})\)

• \(n - 1\) dòng tiếp theo mô tả các cạnh của đồ thị, dòng thứ \(i\) chứa ba số nguyên \(p_{i},\ q_{i}\) và \(r_{i}\) (\(1 \leq p_{i},q_{i} \leq n,\ 1 \leq r_{i} \leq 10^{9})\) thể hiện rằng có cạnh nối hai đỉnh \(p_{i},\ q_{i}\) có trọng số \(r_{i}\)

• \(Q\) dòng tiếp theo, mỗi dòng ghi một truy vấn gồm hai số nguyên \(k,\ v\) (\(1 \leq k \leq 10^{9},\ 1 \leq v \leq n)\) thể hiện yêu cầu đếm xem có bao nhiêu đỉnh mà trọng số đường đi đơn từ nó đến \(v\) lớn hơn hoặc bằng k?.

Kết quả: gồm \(Q\) dòng, mỗi dòng ghi một số nguyên là kết quả của truy vấn tương ứng (theo thứ tự xuất hiện trong file dữ liệu vào)

Ví dụ:

Subtasks:

• Subtask 1: \(n \leq 1000\) [50%]

• Subtask 2: \(n \leq 10^{5}\) [50%]