solution

Thay vì mô tả các khối lệnh bằng một dãy BEGIN/END tuần tự, phần này biểu diễn cấu trúc lồng khối của chương trình dưới dạng cây khối cho trước một cách tường minh: có $n$ khối đánh số từ $1$ đến $n$, khối số $1$ là khối gốc (không có khối cha). Với mỗi khối $i$ ($2 \le i \le n$), $p_i$ là chỉ số khối cha của nó, và $p_i < i$. Mỗi khối $i$ có một danh sách các tên biến được khai báo trực tiếp trong khối đó (dữ liệu vào đảm bảo trong cùng một khối không có hai biến trùng tên).

Theo luật phạm vi tĩnh (static scoping), khi tìm một biến tên $v$ xuất phát từ khối $b$, trình biên dịch sẽ tìm trong chính khối $b$ trước, nếu không thấy thì tìm tiếp ở khối cha của $b$, rồi khối cha của khối cha, cứ thế đi lên cho tới khối gốc.

Cho $q$ truy vấn, mỗi truy vấn gồm một khối $b$ và một tên biến $v$: hãy tìm chỉ số của khối gần $b$ nhất (tính cả $b$) trên đường đi từ $b$ lên khối gốc mà có khai báo trực tiếp biến tên $v$; nếu không có khối nào trên đường đi đó khai báo $v$, trả lời $-1$.

Ví dụ: cây gồm 4 khối: khối 1 (gốc) khai báo x; khối 2 (cha là 1) khai báo y; khối 3 (cha là 2) không khai báo gì; khối 4 (cha là 1) khai báo x. Với truy vấn (3, x): đường đi $3 \to 2 \to 1$, khối 3 và 2 không có x, khối 1 có x $\Rightarrow$ trả lời $1$.