CF1437D Minimal Height Tree

tony102

2020 年 10 月 28 日

1571 次浏览

暂无评论

772字数

题解

[CF1437D](https://www.luogu.com.cn/problem/CF1437D)

## Description

Monocarp有一棵树，可是他已经忘记了它的形态。但是他有这棵树的$bfs$序，并且对于每一个节点，$bfs$都会按照升序遍历它的子节点。现在给出这个$bfs$序，求出这棵树的最小深度。

## Solution

先观察一下这个BFS序的性质

因为它给的BFS是按照升序访问子节点的，那么对于每个点后面出现的节点，如果它后面的点比他的编号还小，说明要新开一层，否则就可以一直堆在一层

举个例子：`1 4 3 2`

`1`已经确定是根，那么`1`的第一个子节点就是`4`，观察到`4`是目前`1`的子节点中编号最小的，如果我们要把`2`也弄成`1`的子节点，那么按照BFS序，`2`应该在`4`前面出现，所以这样是不合法的，说明`2`要新开一层成为`4`的子节点

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;
 
const int SIZE = 2e5 + 5;
 
int T, n, ans;
int a[SIZE], dep[SIZE];
 
inline int read()
{
	char ch = getchar();
	int f = 1, x = 0;
	while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
	return x * f;
}
 
inline void bfs()
{
    std::queue < int > q;
    memset(dep, 0, sizeof(dep));
    q.push(1);
    int pos = 2;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans = std::max(ans, dep[u]);
        int lst = pos;
        if (pos > n) break;
        while (a[pos + 1] > a[pos] && pos < n) ++ pos;
        for (int i = lst; i <= pos; ++ i) {
            dep[a[i]] = dep[u] + 1;
            q.push(a[i]);
        }
        ++ pos;
    }
}
 
int main()
{
    T = read();
    while (T --) {
        n = read();
        for (int i = 1; i <= n; ++ i) a[i] = read();
        ans = 0;
        bfs();
        for (int i = 1; i <= n; ++ i) ans = std::max(ans, dep[i]);
        printf("%d\n", ans);
    }
    return 0;
}
```

最后修改：2021 年 09 月 04 日