Gửi bài giải
Điểm:
1,95 (OI)
Giới hạn thời gian:
4.5s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một cây ~N~ đỉnh, mỗi cạnh của cây có một trọng số nguyên dương ~c~.
Cho 2 số nguyên dương ~L, R~. Tìm một đường đi không lặp có độ dài trong khoảng ~[L,R]~ sao cho trung bình cộng trọng số các cạnh trên đường đi đó là lớn nhất.
Input
Dòng đầu chứa số nguyên dương ~T~ - số test trong 1 file.
Tiếp theo là ~T~ test, mỗi test gồm:
- Dòng đầu tiên chứa số nguyên dương ~N~ là số đỉnh của cây ~(N \leq 50,000)~.
- ~N - 1~ dòng tiếp theo, mỗi dòng gồm 3 số nguyên dương ~u, v, c~ cho biết có một cạnh nối 2 cạnh ~u~ và ~v~, với trọng số là c ~(1 \leq c \leq 10^{6})~.
- Dòng tiếp theo ghi 2 số nguyên dương ~L, R~, ~(1 \leq L \leq R \leq 10^{12})~.
Output
Gồm ~T~ dòng, mỗi dòng gồm số thực duy nhất là trung bình cộng lớn nhất tìm được. Bài của bạn được coi là đưa ra kết quả đúng nếu sai số giữa đáp số của bạn và đáp số của ban tổ chức không quá ~10^{-2}~.
Giới hạn
Trong quá trình thi, bài của bạn sẽ được chấm với ~50\%~ bộ test, và điểm mà bạn đạt được thể hiện phần trăm test mà bạn giải đúng trong các test đó (trên thang điểm ~100~).
Sample Input
1
7
1 2 1
2 3 5
2 4 1
1 5 7
4 6 3
4 7 7
13 15
Sample Output
4.333
Bình luận
có ai có ý tưởng bài này không ạ, em cảm ơn