Codeforces Round #316 (Div.2) D. Tree Requests

問題文

http://codeforces.com/contest/570/problem/D

解法

部分木の特定の高さのノードだけ取り出すのもオイラーツアーでできる。
この場合は高さごとにノードを管理すればよい。
各ノードが持つ区間は普通のオイラーツアーと同じで、各高さごとに持つデータは (今の index、文字を表す bit の xor sum) とする。
文字を表すビットとは、文字 c に対して 1 << (c - 'a') のことをいう。
どうしてこんなことをするかというと、今回制約が厳しいので 26 * m * log が間に合わないからである（log は区間の左端と右端を検索するのにどうしても必要）。
文字の状態を 32bit int で管理しておけば 26 が落とせるので嬉しい。
オイラーツアーのDFSで、頂点 v に到達したら data[height[v]] に ( l[v], data[height[v]].back() ^ (1 << (s[v] - 'a')) ) を追加する。xor の累積和。
各クエリに対しては、その区間の xor sum の popcount が 2 以上であれば回分にできないし、それ未満であれば回分にできる。

bit で26文字を圧縮して O(m * (log + 26)) で解けた。

ソースコード

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i = 1; i < n; ++i) {
        int p; cin >> p;
        g[p - 1].push_back(i);
    }
    string s; cin >> s;
    vector<int> bit(26);
    for(int i = 0; i < 26; ++i) {
        bit[i] = 1 << i;
    }

    vector<vector<pii>> hs(1 << 20, vector<pii>(1, make_pair(0, 0)));
    vector<int> l(n), r(n);
    {
        int cur = 1;
        function<void(int, int)> euler_tour = [&] (int v, int d) {
            l[v] = cur;
            hs[d].emplace_back(cur, hs[d].back().second ^ bit[s[v] - 'a']);
            for(auto to : g[v]) {
                euler_tour(to, d + 1);
            }
            r[v] = ++cur;
        };
        euler_tour(0, 1);
    }

    for(int i = 0; i < m; ++i) {
        int v, h; cin >> v >> h;
        v--;
        const auto lb = lower_bound(begin(hs[h]), end(hs[h]), make_pair(l[v], -1)) - begin(hs[h]) - 1;
        const auto ub = lower_bound(begin(hs[h]), end(hs[h]), make_pair(r[v], -1)) - begin(hs[h]) - 1;
        const auto t = hs[h][ub].second ^ hs[h][lb].second;
        cout << ((t - (t & -t)) == 0 ? "Yes" : "No") << endl;
    }
}

感想

26 を最初落とさなくてTLEしてしまった。
定番テクなのにすぐに思いつけなかったので反省。