传送门
Luogu https://www.luogu.org/problem/CF1037D
解题思路
考虑直接模拟 \(\text{BFS}\) 的过程.
对于每一个节点的儿子, 先遍历在输入序列中靠前的, 判断 \(\text{BFS}\) 是否匹配即可.
细节注意事项
注意一下输出格式
参考代码
- #include <algorithm>
- #include <iostream>
- #include <cstring>
- #include <cstdlib>
- #include <cstdio>
- #include <cctype>
- #include <vector>
- #include <cmath>
- #include <ctime>
- #define rg register
- using namespace std;
- template <typename T> inline void read(T& s) {
- s = 0; int f = 0; char c = getchar();
- while (!isdigit(c)) f |= (c == '-'), c = getchar();
- while (isdigit(c)) s = s * 10 + (c ^ 48), c = getchar();
- s = f ? -s : s;
- }
- const int _ = 200010;
- int n, in[_], p[_];
- int hd, tl, q[_], vis[_];
- vector <int> G[_];
- inline bool cmp(const int& x, const int& y) { return p[x] < p[y]; }
- inline void bfs() {
- hd = tl = 0, q[++tl] = 1;
- while (hd < tl) {
- int u = q[++hd], X = G[u].size();
- vis[u] = 1;
- for (rg int i = 0; i < X; ++i) {
- int v = G[u][i];
- if (!vis[v]) q[++tl] = v;
- }
- }
- }
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("in.in", "r", stdin);
- #endif
- read(n);
- for (rg int u, v, i = 1; i < n; ++i) read(u), read(v), G[u].push_back(v), G[v].push_back(u);
- for (rg int i = 1; i <= n; ++i) read(in[i]), p[in[i]] = i;
- for (rg int i = 1; i <= n; ++i) sort(G[i].begin(), G[i].end(), cmp);
- bfs();
- for (rg int i = 1; i <= n; ++i) if (in[i] != q[i]) return puts("No"), 0;
- puts("Yes");
- return 0;
- }
完结撒花 \(qwq\)
来源: http://www.bubuko.com/infodetail-3258956.html