Cây Chiều Cao Nhỏ Nhất

Điểm: 5,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Dart, Go, Groovy, Java, Javascript, Kotlin, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một dãy số nguyên $a_{1}, a_{2}, \dots, a_{n}$ là thứ tự duyệt BFS của một cây có gốc tại đỉnh $1$ . Cụ thể, thuật toán BFS được mô tả bằng đoạn giả mã sau:

a = []          # thứ tự các đỉnh được xử lý
q = Queue()
q.put(1)        # đặt gốc vào hàng đợi
while q không rỗng:
    k = q.pop()
    a.append(k)
    for y in g[k]:   # g[k] là danh sách con của k, đã sắp xếp tăng dần
        q.put(y)

Lưu ý rằng đối với mỗi đỉnh, các con của nó được duyệt theo thứ tự tăng dần giá trị nhãn.

Có thể có nhiều cây cùng cho ra dãy duyệt BFS $a$ . Hãy tìm chiều cao nhỏ nhất trong tất cả các cây như vậy.

Chiều cao của cây là độ sâu lớn nhất của một đỉnh, trong đó độ sâu của đỉnh là số cạnh trên đường đi từ gốc tới đỉnh đó (gốc có độ sâu $0$ ).

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ — số bộ dữ liệu.
Mỗi bộ dữ liệu gồm:
- Dòng đầu chứa số nguyên $n$ — số đỉnh của cây.
- Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ là thứ tự duyệt BFS.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên là chiều cao nhỏ nhất có thể.

Ràng buộc

$1 \leq t \leq 1000$
$2 \leq n \leq 2 \cdot 10^{5}$
$1 \leq a_{i} \leq n$ , các $a_{i}$ phân biệt, $a_{1} = 1$
Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^{5}$ .

Ví dụ

Input	Output	Giải thích
3 4 1 4 3 2 2 1 2 3 1 2 3	3 1 1	Bộ 1: dãy $1, 4, 3, 2$ giảm dần sau đỉnh $1$ , nên mỗi đỉnh cha chỉ có thể có đúng một con — cây trở thành đường thẳng, chiều cao $3$ . Bộ 3: dãy $1, 2, 3$ tăng dần, có thể cho cả $2$ và $3$ làm con của $1$ — chiều cao $1$ .
1 4 1 4 2 3	2	Cho $4$ làm con của $1$ (độ sâu $1$ ), rồi $2$ và $3$ làm con của $4$ (độ sâu $2$ , các nhãn $2 < 3$ tăng dần thoả mãn).

Bình luận

Không có bình luận tại thời điểm này.