题目描述

给一棵树的BFS序，兄弟节点的序号是升序，根节点是$1$。求这棵的深度。

输入

第一行T组数据。

每组数据第一行一个n，第二行n个数为这棵树的BFS序。

输出

树的深度。

样例

输入

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

输出

3
1
1

样例1：

样例2：

样例3：

思路

(乱搞) $O(n)$

模拟一遍建树过程。遍历n个节点，用vector把树存一下，深度$d[i]$ = $d[ fa ]+1$ 。

最终$d[n]$ 就是这棵树的深度。

C++ 代码

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define fi first
#define se second
const int Mn=2e5+17;

vector<int> v[Mn];
pair<int ,int> a[Mn];
int d[Mn];

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",&a[i].fi),a[i].se=i;
        for(int i=0;i<=n;++i) v[i].clear();
        int index=1;
        d[1]=0;
        for(int i=2;i<=n;++i){
            if(a[i].fi>a[i-1].fi) v[index].pb(a[i].se);
            else v[++index].pb(a[i].se);
            d[i]=d[index]+1;
        }
        // for(int i=1;i<=n;++i) printf(" ? [%d] %d \n",i,d[i]);
        printf("%d\n",d[n]);
    }
}
/*
1
8
1 2 6 4 3 9 7 5
*/