AND đường đi

Hệ thống phân quyền bảo mật của công ty FPTOJ gồm \(N\) phòng ban được nối với nhau bởi \(N-1\) kênh liên lạc nội bộ. Mỗi kênh liên lạc có một mã quyền (là số nguyên dương). Để truyền một tài liệu mật từ phòng ban u đến v, tài liệu phải hội tụ đủ tất cả các quyền trên đường đi, tức là phép AND (ký hiệu \(\&\)) của các mã quyền. Hãy tính mã quyền tổng hợp cho mỗi đường truyền tài liệu.

Yêu cầu: Cho \(N\) phòng ban và \(N-1\) kênh liên lạc. Trả lời Q truy vấn, mỗi truy vấn in ra giá trị AND 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ả AND của các cạnh trên đường đi.

Ví dụ:

Dữ liệu vào:

3
1 2 7
2 3 3
2
1 3
2 1

Kết quả:

3
7

Giải thích:

• Đường \(1 \to 2 \to 3\): \(7 \,\&\, 3 = 3\) (vì 111_2 \, \&\, \(011_2 = 011_2 = 3\)).
• Đường \(2 \to 1\): \(7\).

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\) (\(1 \le u, v \le N, 0 \le w < 2^{30}\)) mô tả cạnh nối \(u, v\) có trọng số \(w\).
• 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\) là truy vấn.

Định dạng đầu ra

• Với mỗi truy vấn, in ra giá trị phép AND các trọng số cạnh trên đường đi từ \(u\) đến \(v\).

Ví dụ

Input:

4
1 2 7
2 3 3
2 4 5
2
1 3
3 4

Output:

3
1

Giải thích: Đường đi 1->3 gồm cạnh 7 (\(111_2\)) và 3 (011_2) -> AND = 3. Đường đi 3->4 gồm cạnh 3 và 5 (\(101_2\)) -> AND = 1.

Ràng buộc & Subtasks