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

    solution

    Đề bài: [Giải thuật] Tổ tiên chung gần nhất (LCA)

    Cho cây có gốc tại đỉnh 111 gồm nnn đỉnh và qqq truy vấn. Mỗi truy vấn gồm hai đỉnh u,vu, vu,v; hãy in tổ tiên chung gần nhất (LCA) của chúng.

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

      Dòng đầu nnn. Dòng thứ hai gồm n−1n-1n−1 số: p2,p3,…,pnp_2, p_3, \dots, p_np2​,p3​,…,pn​ với pip_ipi​ là cha của đỉnh iii. Dòng tiếp theo là qqq. qqq dòng sau mỗi dòng uuu vvv.

    • Ràng buộc đầu vào:

      1≤n≤1051 \le n \le 10^51≤n≤105, 1≤q≤1051 \le q \le 10^51≤q≤105, 1≤pi<i1 \le p_i < i1≤pi​<i.

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

      Với mỗi truy vấn, in LCA của uuu và vvv trên một dòng.

    Ví dụ:

    Đầu vào:

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

    Đầu ra:

    2
1
1

    Giải thích:

    4 và 5 đều con của 2 nên LCA=2; 4 và 3 có LCA=1; 5 và 1 có LCA=1.

    Đang tải editor...