Nội dung Bài tập
- Mã:
- Tree
- Tên:
- Tree (ACM 2014)
- Dạng thi:
- acm
- Thang điểm:
- 1 điểm
- Giới hạn thời gian:
- 3 giây
- Giới hạn bộ nhớ:
- 64 MB
- Được tạo bởi:
- admin
Cho một cây có hướng T gồm N đỉnh (N ≤ 105). Các đỉnh được đánh số từ 1 tới N, với gốc cây là đỉnh 1. Bạn cần thực hiện Q truy vấn thuộc 1 trong 2 loại sau: (Q ≤ 105)
- Cho 2 đỉnh u và v, tách u khỏi nút cha và cho u làm con cuối cùng của nút v. Input bảo đảm nút u không phải là tổ tiên của nút v.
- Tìm nút thứ K khi duyệt cây theo thứ tự pre-order.
Việc duyệt cây theo thứ tự pre-order được thực hiện theo đoạn giả mã (kèm theo hình minh họa) dưới đây:
Input
Dòng đầu chứa số nguyên dương T - số test (T ≤ 10). Sau đó là T test. Mỗi test có định dạng như sau:
- Dòng đầu chứa số nguyên dương N.
- N - 1 dòng tiếp theo, mỗi dòng chứa 2 số x và y cho biết y là con của x. Các con của x xuất hiện theo đúng thứ tự.
- Dòng tiếp theo chứa số nguyên dương Q.
- Q dòng tiếp theo chứa các truy vấn với 1 trong 2 định dạng sau:
- 1 u v (1 ≤ u, v ≤ N), input bảo đảm u không là tổ tiên của v.
- 2 k (1 ≤ k ≤ N).
Output
Với mỗi truy vấn loại 2, in ra 1 số nguyên dương là đáp án của truy vấn đó.
Sample test(s)
Input
1
7
1 3
1 2
3 5
3 4
2 6
2 7
15
2 1
2 2
2 3
2 4
2 5
2 6
2 7
1 3 2
2 1
2 2
2 3
2 4
2 5
2 6
2 7
Output
1
3
5
4
2
6
7
1
2
6
7
3
5
4
Hình minh họa cho test ví dụ:
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <iostream>using namespace std;struct ps { int tu, mau; &...