Đường Đi Trung Vị Trọng Số Lớn Nhất

Binary-search Buổi 46 — Centroid Decomposition
Points
95
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
graph
Submissions

Đề bài

Cho một cây có trọng số gồm $N$ đỉnh đánh số từ $1$ đến $N$ và hai số nguyên dương $L, R$ ($1 \le L \le R < N$).

Với một đường đi đơn gồm $k$ cạnh có trọng số sau khi sắp xếp tăng dần là $w_1 \le w_2 \le \dots \le w_k$, trung vị trên của đường đi đó được định nghĩa là $w_{\lfloor k/2 \rfloor + 1}$ (ví dụ: với $k=2$, trung vị là $w_2$; với $k=3$, trung vị là $w_2$).

Hãy tìm giá trị trung vị trên lớn nhất có thể của một đường đi đơn có số cạnh nằm trong đoạn $[L, R]$. Nếu không tồn tại đường đi nào có số cạnh trong $[L, R]$, in ra -1.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên $N, L, R$ ($1 \le L \le R < N \le 10^5$).
  • $N - 1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, w$ ($1 \le u, v \le N$, $1 \le w \le 10^9$) biểu thị một cạnh có trọng số $w$.

Dữ liệu ra

  • In ra một số nguyên duy nhất là trung vị trên lớn nhất tìm được (hoặc -1).

Ví dụ

Dữ liệu vào
6 2 4
1 2 5
2 3 2
2 4 8
4 5 3
5 6 7
Dữ liệu ra
8

Giới hạn

  • $2 \le N \le 10^5$, $1 \le L \le R < N$, $1 \le w \le 10^9$.
Draft saved