Editorial: Mathematical Algorithms TWK Open ∮ Problem #F - Tuyến Đường Cấm

1. Ý tưởng

Với mỗi \(A_i\), chỉ cần quan tâm đến phần tự do chính phương: tích các prime có số mũ lẻ. Biểu diễn nó bằng hash \(64\) bit, khi đó tích trên một đường đi tương ứng với phép XOR hash.

Đặt \(H_v\) là XOR hash trên đường từ gốc đến \(v\). Với đường đi \(u\leftrightarrow v\), ta có:

Do đó đường đi tốt khi:

2. Centroid Decomposition + NTT

Ta dùng centroid decomposition trên cây. Tại mỗi centroid \(c\), gom các đỉnh thành các nhóm theo từng nhánh của \(c\).

Với mỗi đỉnh lưu:

• \(d\): khoảng cách đến \(c\).
• \(H\): hash XOR từ \(c\) đến đỉnh.
• \(W\): tích trọng số trên đoạn từ \(c\) đến đỉnh.

Hai đỉnh thuộc hai nhánh khác nhau tạo thành đường đi đi qua \(c\). Điều kiện tốt trở thành một điều kiện XOR giữa hai hash, đồng thời khoảng cách là tổng hai độ sâu.

Các đỉnh có cùng hash mục tiêu được gom nhóm. Với mỗi cặp nhóm, ta cần tích chập theo độ sâu:

Nếu số phần tử nhỏ thì duyệt trực tiếp, còn trường hợp lớn dùng NTT để tính tích chập nhanh.

Để tránh đếm hai lần, chỉ ghép mỗi cặp nhóm theo một thứ tự cố định. Các đường đi có một đầu chính là centroid cũng được xử lý riêng.

Sau khi xử lý centroid, loại centroid khỏi cây và đệ quy trên các thành phần còn lại.

Hash dùng hai giá trị \(64\) bit để giảm xác suất collision. Việc phân tích \(A_i\) thành prime có số mũ lẻ được thực hiện bằng sieve.

3. Độ phức tạp

Gọi \(N\) là số đỉnh. Centroid decomposition có \(O(\log N)\) tầng.

Các phép tích chập được tối ưu bằng cách chọn giữa duyệt trực tiếp và NTT, cho tổng độ phức tạp khoảng:

với bộ nhớ \(O(N)\).