Đếm đường đi XOR
Đề bài
Mô tả
Cho một cây gồm đỉnh (đánh số từ đến ). Mỗi cạnh có trọng số .
Xét một đường đi đơn (không lặp đỉnh) bất kỳ gồm các đỉnh phân biệt với , trong đó mỗi cặp liên tiếp được nối bởi một cạnh của cây.
Vẻ đẹp của đường đi được định nghĩa là XOR của các trọng số trên đường đi:
Bạn được cho truy vấn, mỗi truy vấn là một giá trị . Với mỗi , hãy đếm số lượng đường đi (tương ứng với các cặp đỉnh không kể thứ tự) có vẻ đẹp đúng bằng .
Dữ liệu vào
- Dòng đầu chứa số nguyên .
- dòng tiếp theo, mỗi dòng gồm ba số : một cạnh nối và với trọng số .
- Dòng tiếp theo chứa số nguyên .
- dòng tiếp theo, mỗi dòng chứa một số nguyên .
Dữ liệu ra
In ra dòng, dòng thứ là số lượng đường đi có vẻ đẹp bằng .
Ràng buộc
- , .
- .
Subtasks
- Subtask 1 ( số điểm): .
- Subtask 2 ( số điểm): .
- Subtask 3 ( số điểm): Không có ràng buộc thêm.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 1 2 0 2 3 1 3 0 1 2 |
1 2 0 |
Đường đi giữa cặp đỉnh có vẻ đẹp bằng ; cặp có vẻ đẹp bằng ; cặp có vẻ đẹp bằng . |
| 3 1 2 10 2 3 5 3 0 5 15 |
0 1 1 |
Cặp có vẻ đẹp bằng ; cặp có vẻ đẹp bằng ; cặp có vẻ đẹp bằng . |
Bình luận