CodeForces 1037D - Valid BFS? 题解

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define for1(i, n) for (int i = 1; i <= int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i <= int(r); ++i)
#define ford(i, n) for (int i = int(n)-1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define ms(a, x) memset(a, x, sizeof(a))
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define de(x) cout<<#x<<" = "<<(x)<<endl
#define de2(x,y) cout<<#x<<" = "<<(x) <<' '<< #y<<" = "<<y<<endl;
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
constexpr int INF = 0x3f3f3f3f;
mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());
 
const int N=2e5+5;
vector<int> G[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    forn(i,n-1){
        int x,y;
        cin>>x>>y;
        G[x].pb(y);
        G[y].pb(x);
    }
    vector<int> input(n), a(n+1);
    forn(i,n){
        cin>>input[i];
        a[input[i]]=i;
    }
    for1(i,n){
        sort(all(G[i]),[&](int x,int y){return a[x]<a[y];});
    }
    queue<int> q;
    q.push(1);
    vector<bool> vis(n+1);
    vector<int> ans;
    while(!q.empty()){
        int now=q.front();
        q.pop();
        ans.pb(now);
        vis[now]=1;
        for(auto it:G[now]) if(!vis[it]) q.push(it);
    }
    forn(i,n) if(ans[i]!=input[i]) return cout<<"no",0;
    cout<<"yes";
    return 0;
}