trang chủ / đề bài / icpc25_mt_b

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 N thành phố cổ, được nối bởi N−1 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 wi, 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ố u đến thành phố v là một đường XOR với chỉ số may mắn Wuv 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" Wuv 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 N: số thành phố.
  • N−1 dòng tiếp theo, mỗi dòng gồm ba số nguyên u, v và w, thể hiện một tuyến đường nối thành phố u và v với chỉ số may mắn w.

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

  • 2≤N≤105
  • 1≤u,v≤N, 0≤w<226
  • 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ó 6 cặp: (1,2) có giá trị 3; (1,3) có 3⊕5=6; (1,4) có 3⊕6=5; (2,3) có 5; (2,4) có 6; (3,4) có 5⊕6=3. Tổng là 3+6+5+5+6+3=28 (⊕ 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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0