算法分析
先按给定的 $\operatorname{bfs}$ 序给每个点的邻接表做一遍排序,然后跑一遍 $\operatorname{bfs}$ 求出 $\operatorname{bfs}$ 序,再将求出的 $\operatorname{bfs}$ 序和给定的 $\operatorname{bfs}$ 序进行比较即可。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> to(n);
rep(i, n-1) {
int a, b;
cin >> a >> b;
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
vector<int> a(n);
rep(i, n) cin >> a[i];
rep(i, n) a[i]--;
vector<int> ord(n);
rep(i, n) ord[a[i]] = i;
rep(v, n) {
sort(to[v].begin(), to[v].end(), [&](int x, int y) {
return ord[x] < ord[y];
});
}
vector<int> ans;
queue<int> q;
vector<bool> used(n);
q.push(0); used[0] = true;
while (q.size()) {
int v = q.front(); q.pop();
ans.push_back(v);
for (int u : to[v]) {
if (used[u]) continue;
q.push(u); used[u] = true;
}
}
rep(i, n) {
if (ans[i] != a[i]) {
puts("No");
return 0;
}
}
puts("Yes");
return 0;
}