OR đường đi

Trong một hệ thống định tuyến tín hiệu số, \(N\) bộ định tuyến được kết nối với nhau bởi \(N-1\) đường truyền. Mỗi đường truyền có một mặt nạ tín hiệu (là số nguyên dương). Khi một gói tin đi từ bộ định tuyến u đến v, nó sẽ mang mặt nạ tổng hợp bằng phép OR (ký hiệu \(|\)) của tất cả các mặt nạ trên đường đi. Hãy tính mặt nạ tổng hợp cho mỗi đường truyền tin.

Yêu cầu: Cho \(N\) bộ định tuyến và \(N-1\) đường truyền. Trả lời Q truy vấn, mỗi truy vấn in ra giá trị OR của các cạnh trên đường đi từ u đến \(v\).

Dữ liệu vào:

• Dòng đầu chứa số nguyên dương \(N\). - N-\(1\) dòng tiếp theo, mỗi dòng gồm ba số u, v, \(w\).
• Dòng tiếp theo chứa số nguyên dương \(Q\).
• \(Q\) dòng sau, mỗi dòng gồm hai số u, \(v\).

Kết quả:

• In ra \(Q\) dòng, mỗi dòng là kết quả OR của các cạnh trên đường đi.

Ví dụ:

Dữ liệu vào:

3
1 2 3
2 3 5
2
1 3
2 1

Kết quả:

7
3

Giải thích:

• Đường \(1 \to 2 \to 3\): \(3 \,|\, 5 = 7\).
• Đường \(2 \to 1\): \(3\).

Giới hạn: | Subtask | \(N\) | \(Q\) | Điểm | |---------|-----|-----|------| | 1 | \(N \le 100\) | \(Q \le 100\) | 5 | | 2 | \(N \le 500\) | \(Q \le 500\) | 5 | | 3 | \(N \le 2000\) | \(Q \le 2000\) | 10 | | 4 | \(N \le 10000\) | \(Q \le 10000\) | 10 | | 5 | \(N \le 50000\) | \(Q \le 50000\) | 15 | | 6 | \(N \le 100000\) | \(Q \le 100000\) | 15 | | 7 | \(N \le 100000\) | \(Q \le 100000\) | 20 | | 8 | \(N \le 100000\) | \(Q \le 100000\) | 20 |

Định dạng đầu vào

• Dòng 1: Số nguyên \(N\) (\(1 \le N \le 10^5\)). - N-\(1\) dòng tiếp theo: mỗi dòng chứa 3 số nguyên \(u, v, w\) (\(0 \le w < 2^{30}\)).
• Dòng tiếp theo: Số nguyên \(Q\) (\(1 \le Q \le 10^5\)).
• \(Q\) dòng tiếp theo: mỗi dòng chứa 2 số nguyên \(u, v\).

Định dạng đầu ra

• In ra giá trị phép OR các trọng số cạnh trên đường đi từ \(u\) đến \(v\).

Ví dụ

Input:

4
1 2 1
2 3 2
2 4 4
2
1 3
3 4

Output:

3
6

Giải thích: Đường đi 1->3 gồm 1 và 2 -> 1 OR 2 = 3. Đường đi 3->4 gồm 2 và 4 -> 2 OR 4 = 6.

Ràng buộc & Subtasks