Bedao OI Contest 5 - Xtree
Xem dạng PDF
Cho một cây có trọng số gồm ~n~ đỉnh. Giá trị của một đường đi được tính bằng tổng XOR của trọng số các cạnh trên đường đi. Tìm giá trị lớn nhất có thể của một đường đi đơn~^\dagger~ trên cây sau khi thêm đúng một cạnh có trọng số nằm trong đoạn ~[l, r]~ nối giữa hai đỉnh bất kỳ trên cây.
~^\dagger~Đường đi đơn là đường đi có các đỉnh đôi một phân biệt.
Input
Dữ liệu vào từ file văn bản xtree.inp:
Dòng đầu tiên gồm một số nguyên ~n, l, r~ (~1 \le n \le 700~; ~0 \le l \le r < 2^{63}~) — số đỉnh của cây và giới hạn trọng số cạnh được thêm vào.
Mỗi dòng trong ~n - 1~ dòng tiếp theo gồm ba số nguyên ~u,v,w~ (~1 \le u, v \le n~; ~0 \le w < 2^{63}~) — thể hiện một cạnh nối ~u~ và ~v~ với trọng số ~w~ trên cây.
Output
In ra file văn bản xtree.out giá trị lớn nhất có thể của một đường đi đơn sau khi thêm một cạnh.
Scoring
| Subtask | Điểm | Giới hạn |
|---|---|---|
| ~1~ | ~15\%~ | ~n\le 40~ |
| ~2~ | ~15\%~ | ~n\le 100~ |
| ~3~ | ~20\%~ | ~u_i = i~ và ~v_i = i + 1~ ~(1 \le i \lt n)~ |
| ~4~ | ~25\%~ | ~l = r~ |
| ~5~ | ~25\%~ | Không có ràng buộc gì thêm |
Sample Input 1
4 1 10
1 2 1
2 3 2
3 4 3
Sample Output 1
11
Notes
Ở test ví dụ, ta thêm một cạnh với trọng số ~9~ nối hai đỉnh ~3~ và ~4~, ta được đường đi ~2\rightarrow 3\rightarrow 4~ có giá trị bằng ~2\oplus 9=11~.
Bình luận
.