Ký ức của N được biểu diễn bằng một dãy \([a_0,a_1,\ldots,a_{n-1}]\).

Mỗi cây gạo trong ký ức là một cây vô hướng có nhãn. Một đoạn nửa kín \([l,r)\) của dãy mô tả một cây như sau:

• Cây có \(k=r-l+2\) đỉnh, đánh số từ \(0\) đến \(k-1\).
• Dãy

là mã Prüfer của cây.

Có \(m\) truy vấn. Truy vấn thứ \(i\) hỏi: trong cây được mô tả bởi đoạn \([l_i,r_i)\), hai đỉnh \(x_i,y_i\) có kề nhau hay không?

Yêu cầu cài đặt

Bạn không được cài đặt hàm main. Submission phải include kapok.h và cài đặt:

std::vector<bool> kapok(
    int c, int n, int m,
    std::vector<int> a,
    std::vector<int> l,
    std::vector<int> r,
    std::vector<int> x,
    std::vector<int> y
);

• c là số hiệu test; c=0 biểu thị dữ liệu mẫu.
• n, m là độ dài dãy và số truy vấn.
• a là dãy ký ức.
• l, r là hai đầu đoạn của từng truy vấn.
• x, y là hai đỉnh được hỏi trong từng truy vấn.
• Hàm phải trả về một vector có đúng \(m\) phần tử. Phần tử thứ \(i\) là true khi \(x_i,y_i\) kề nhau và false trong trường hợp còn lại.
• Bộ chấm gọi hàm đúng một lần cho mỗi test.

Khung khai báo:

#include "kapok.h"

Dữ liệu bộ chấm

• Dòng đầu chứa \(c,n,m\).
• Dòng thứ hai chứa \(a_0,a_1,\ldots,a_{n-1}\).
• Mỗi trong \(m\) dòng tiếp theo chứa \(l_i,r_i,x_i,y_i\).

Grader ghi \(m\) dòng, mỗi dòng là 1 nếu câu trả lời là true, ngược lại là 0.

Ràng buộc

• \(1\le n,m\le2\cdot10^5\).
• \(0\le a_i<n+2\).
• \(0\le l_i\le r_i\le n\).
• \(0\le x_i,y_i<r_i-l_i+2\).

Phân nhóm

Mỗi test có giá trị \(4\) điểm.

Tính chất A: sau khi đã cho \(l_i,r_i\), hai giá trị \(x_i,y_i\) được sinh độc lập và đều trên toàn bộ miền giá trị hợp lệ của chúng.

Nhắc lại về mã Prüfer

Với cây vô hướng \(T\) có các đỉnh \(0,1,\ldots,c-1\), \(c\ge2\), thực hiện \(c-2\) lần:

1. Chọn lá có nhãn nhỏ nhất \(v_i\) trong cây hiện tại.
2. Ghi lại nhãn \(p_i\) của đỉnh kề duy nhất với \(v_i\).
3. Xóa \(v_i\) và cạnh duy nhất nối với nó.

Dãy \([p_0,p_1,\ldots,p_{c-3}]\) thu được là mã Prüfer của \(T\).

Ví dụ

0 8 3
2 0 2 6 0 7 2 2
0 3 0 2
3 5 1 2
0 0 0 1

1
0
1

• Đoạn \([0,3)\) cho mã Prüfer \([2,0,2]\) của cây có các cạnh \((1,2),(0,3),(0,2),(2,4)\), nên \(0,2\) kề nhau.
• Đoạn \([3,5)\) cho mã \([3,0]\) của cây có các cạnh \((1,3),(0,2),(0,3)\), nên \(1,2\) không kề nhau.
• Đoạn \([0,0)\) cho cây hai đỉnh với cạnh duy nhất \((0,1)\).

Nguồn

CCF NOI 2026 - Ngày 2, bài Kapok. Đề và dữ liệu chính thức được phát hành theo giấy phép CC BY-NC.