trang chủ / đề bài / thpn26_xorpathcnt

Đếm đường đi XOR

Đề bài

Mô tả

Cho một cây gồm n đỉnh (đánh số từ 1 đến n). Mỗi cạnh có trọng số w.

Xét một đường đi đơn (không lặp đỉnh) bất kỳ gồm các đỉnh phân biệt u1,u2,…,uk với k≥2, trong đó mỗi cặp liên tiếp (ui,ui+1) đượ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:

w(u1,u2)⊕w(u2,u3)⊕…⊕w(uk−1,uk).

Bạn được cho q truy vấn, mỗi truy vấn là một giá trị f. Với mỗi f, 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 f.

Dữ liệu vào

  • Dòng đầu chứa số nguyên n (2≤n≤2·105).
  • n−1 dòng tiếp theo, mỗi dòng gồm ba số u,v,w (0≤w<220): một cạnh nối u và v với trọng số w.
  • Dòng tiếp theo chứa số nguyên q (1≤q≤2·105).
  • q dòng tiếp theo, mỗi dòng chứa một số nguyên f (0≤f<220).

Dữ liệu ra

In ra q dòng, dòng thứ i là số lượng đường đi có vẻ đẹp bằng fi.

Ràng buộc

  • 2≤n≤2·105, 1≤q≤2·105.
  • 0≤w,f<220.

Subtasks

  • Subtask 1 (28% số điểm): n,q≤100.
  • Subtask 2 (20% số điểm): n,q≤1000.
  • Subtask 3 (52% 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 (1,2) có vẻ đẹp bằng 0; cặp (1,3) có vẻ đẹp bằng 1; cặp (2,3) có vẻ đẹp bằng 1.
3
1 2 10
2 3 5
3
0
5
15
0
1
1
Cặp (1,2) có vẻ đẹp bằng 10; cặp (1,3) có vẻ đẹp bằng 15; cặp (2,3) có vẻ đẹp bằng 5.

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