Codeforces 1037D(BFS序)

Codeforces 1037D
题意：给出一棵树以及一个序列，问这个序列是否可能是原树的 BFS 序。
考虑 BFS 分层，然后每次读进来数判断一下是否能接上。看代码即可。
注意 BFS 序要按顺序，比如上一层在前面入队的是1，那么遍历这一层时一定是1的所有孩子在前面

本题结合了 BFS 序，对于 BFS 不一定要用队列，可以边处理边 BFS 一层。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

const int MAXN = 200000 + 5, ZINF = 1000000000;

int n, bfn[MAXN], vis[MAXN], sz;
std::vector<int > G[MAXN];
std::multiset<int > s;

void clean() {
    sz = 0, ms(bfn, 0), ms(vis, 0);
}
int solve() {
    clean();
    for (int x, y, i = 1; i < n; i++) scanf("%d%d", &x, &y), G[x].push_back(y), G[y].push_back(x);
    vis[1] = 1, s.insert(0);
    for (int a, i = 1; i <= n; i++) {
        scanf("%d", &a);
        if (!vis[a]) return printf("No\n"), 0; 
        if (bfn[a] != *s.begin()) return printf("No\n"), 0;
        sz++;
        for (int i = 0; i < (int)G[a].size(); i++) {
            int v = G[a][i];
            if (!vis[v]) vis[v] = 1, bfn[v] = sz, s.insert(sz);
        }
        s.erase(s.find(bfn[a]));
    }
    printf("Yes\n");
    return 0;
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}