cf1037D. Valid BFS?(BFS?)

题意

题目链接

sol

非常妙的一道题。。

可以这样想，在bfs序中较早出现的一定是先访问的，所以把每个点连出去的边按出现的前后顺序排个序

看一下按顺序遍历出来的序列与给出的是否相同就行了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, a[maxn], dfn[maxn], tot, vis[maxn], tim[maxn];
vector<int> v[maxn];
int comp(const int &x, const int &y) {
    return tim[x] < tim[y];
}
void bfs() {
    queue<int> q;
    q.push(1);
    while(!q.empty()) {
        int p = q.front(); q.pop();
        dfn[++tot] = p; vis[p] = 1;
        for(int i = 0, to; i < v[p].size(); i++) {
            if(!vis[(to = v[p][i])]) q.push(to);
        }
    }
}
main() {
    n = read();
    for(int i = 1; i <= n - 1; i++) {
        int x = read(), y = read();
        v[x].push_back(y); v[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) tim[a[i] = read()] = i;
    for(int i = 1; i <= n; i++) 
        sort(v[i].begin(), v[i].end(), comp);
    bfs();
    //for(int i = 1; i <= n; i++) printf("%d ", dfn[i]); puts("");
    for(int i = 1; i <= n; i++)
        if(dfn[i] != a[i]) {puts("no"); return 0;}
    puts("yes");
}