Con đường Tơ lụa XOR
Đề bài
Mô tả
Con đường Tơ lụa XOR huyền thoại không chỉ là một tuyến đường thương mại; đó là một mạng lưới kết nối các nền văn minh. Mạng lưới gồm thành phố cổ, được nối bởi tuyến đường, tạo thành một mạng lưới không có chu trình. Mỗi tuyến đường giữa hai thành phố được gán một chỉ số may mắn , là một số thể hiện rủi ro và cơ hội trên tuyến đường đó. Đường đi từ thành phố đến thành phố là một đường XOR với chỉ số may mắn bằng tổng XOR của tất cả các "chỉ số may mắn" trên các tuyến đường mà nó đi qua.
Một nhà khảo cổ vừa phát hiện bản đồ của mạng lưới này cùng toàn bộ các chỉ số may mắn. Để hiểu được sự thịnh vượng và quy mô kinh tế của nền văn minh cổ đại này, ông muốn tính tổng giá trị may mắn của toàn mạng lưới, tức là tổng các "chỉ số may mắn" của mọi cặp thành phố phân biệt trên Con đường Tơ lụa XOR.
Nhiệm vụ của bạn là giúp nhà khảo cổ giải đáp bí ẩn này.
Dữ liệu vào
- Dòng đầu tiên gồm một số nguyên : số thành phố.
- dòng tiếp theo, mỗi dòng gồm ba số nguyên , và , thể hiện một tuyến đường nối thành phố và với chỉ số may mắn .
Dữ liệu ra
In ra một dòng gồm tổng giá trị may mắn của toàn mạng lưới.
Ràng buộc
- ,
- Các tuyến đường tạo thành một cây.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 4 1 2 3 2 3 5 2 4 6 |
28 | Có cặp: có giá trị ; có ; có ; có ; có ; có . Tổng là ( là phép XOR). |
| 5 1 2 1 1 3 2 3 4 4 3 5 7 |
42 | Ví dụ bổ sung. |
Bình luận