Valid BFS? [Manthan, Codefest 18 D]

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;
}