Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Số biến khả kiến tại mỗi khối trên cây phạm vi

    Cho một cây khối như ở phần truy vấn phạm vi tĩnh: nnn khối đánh số 1..n1..n1..n, khối 111 là gốc, mỗi khối iii (i≥2i \ge 2i≥2) có cha pi<ip_i < ipi​<i, và mỗi khối có một danh sách tên biến khai báo trực tiếp (không trùng tên trong cùng một khối).

    Với mỗi khối iii, định nghĩa tập biến khả kiến (visible) tại iii là tập hợp mọi tên biến được khai báo trực tiếp tại iii hoặc tại bất kỳ khối tổ tiên nào của iii (kể cả khối gốc) — theo đúng luật phạm vi tĩnh, một tên có thể được khai báo lại (che khuất) ở nhiều khối khác nhau trên cùng đường đi, nhưng khi đếm số lượng tên phân biệt khả kiến thì mỗi tên chỉ được tính một lần dù nó xuất hiện ở bao nhiêu khối tổ tiên.

    Với mỗi khối iii từ 111 đến nnn, hãy in ra số lượng tên biến phân biệt khả kiến tại khối iii.

    Ví dụ: cây gồm 5 khối: khối 1 (gốc) khai báo x; khối 2 (cha 1) khai báo y; khối 3 (cha 2) khai báo x (che khối 1); khối 4 (cha 1) không khai báo gì; khối 5 (cha 3) khai báo z. Khi đó: khối 1 khả kiến {x}\{x\}{x} (1 tên); khối 2 khả kiến {x,y}\{x, y\}{x,y} (2 tên); khối 3 khả kiến {x,y}\{x, y\}{x,y} (2 tên, vì x dù được khai lại vẫn chỉ tính một lần); khối 4 khả kiến {x}\{x\}{x} (1 tên); khối 5 khả kiến {x,y,z}\{x, y, z\}{x,y,z} (3 tên). Kết quả in ra 5 dòng: 1 2 2 1 3.

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

      Dòng đầu tiên chứa số nguyên nnn (1≤n≤50001 \le n \le 50001≤n≤5000). nnn dòng tiếp theo, dòng thứ iii mô tả khối iii: gồm pip_ipi​ (chỉ số khối cha, quy ước p1=0p_1 = 0p1​=0), kik_iki​ (số biến khai báo trực tiếp), và kik_iki​ tên biến cách nhau bởi khoảng trắng.

    • Định dạng đầu ra:

      In ra nnn dòng, dòng thứ iii là số lượng tên biến phân biệt khả kiến tại khối iii (với iii chạy từ 111 đến nnn).

    Ví dụ:

    Đầu vào:

    1
0 0

    Đầu ra:

    0

    Đầu vào:

    5
0 1 x
1 1 y
2 1 x
1 0
3 1 z

    Đầu ra:

    1
2
2
1
3

    Đang tải editor...