http://codeforces.com/contest/1037/problem/D
N頂点の木と[1,N]の順列Aがある。
この木について、頂点1からBFSをして訪れた頂点を順番に記録して、順列Aにできるか判定せよ。
解法
http://codeforces.com/contest/1037/submission/42453314
※全て0-indexedに置き換えて解説する
まずはA[0]=0である必要がある。
その後は順列Aに寄せて、BFSをシミュレートしていく。
順列AはBFSで用いるqueueの中身とも言える。
offset := 順列Aの何番目が今のqueueの最後尾か
頂点0からスタートした場合は、キューに0は入っていて、最後尾は1番目なので、offset=1
ここから、キューに入れられるのは、現在見ている頂点の子供である。
子供がn頂点あるなら、木でのn頂点の子供と順列Aでのn頂点の子供は集合としてはおなじになるはず。
そのため、それぞれn頂点取ってきて、ソートして先頭から比較すれば、集合として同じか確認できる。
同じであれば、順列Aの通りの順番でキューに入れる。
このようにすると、順列Aに寄せてBFSをシミュレートできる。
これを続けていって、不整合がなければYes
int N, A[201010]; vector<int> E[201010]; //--------------------------------------------------------------------------------------------------- int vis[201010]; #define yes "Yes" #define no "No" string solve() { if (A[0] != 0) return no; queue<int> q; q.push(0); int offset = 1; while (!q.empty()) { int cu = q.front(); q.pop(); vis[cu] = 1; vector<int> v; fore(to, E[cu]) if (!vis[to]) v.push_back(to); int n = v.size(); vector<int> a; rep(i, 0, n) a.push_back(A[offset + i]); sort(all(v)); sort(all(a)); rep(i, 0, n) if (v[i] != a[i]) return no; rep(i, 0, n) q.push(A[offset + i]); offset += n; } return yes; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(i, 0, N - 1) { int a, b; cin >> a >> b; a--; b--; E[a].push_back(b); E[b].push_back(a); } rep(i, 0, N) cin >> A[i]; rep(i, 0, N) A[i]--; cout << solve() << endl; }