mayoko’s diary

プロコンとかいろいろ。

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

解法

質問のクエリだけがやってくるので先に質問を全部読んでおきます。

で, 各クエリについて,
query_v[v] は頂点 v に関するクエリ番号の集合を表し,
query_h[i] はクエリ番号 i の質問では高さがいくつの頂点について聞かれているか,
をメモしておきます。

ある文字の集合が回文になっているかどうかは, 26 個のアルファベットのそれぞれの文字で奇数個ある文字が 1 つ以下だったら OK です。なので, 各文字の偶奇さえわかれば良いわけです。これは, 整数の 26 個のビットを使って偶奇を管理すれば行けそうです。

ということで,
xor_h[h] : 高さ h の頂点について, 各文字の偶奇のフラグ
という配列も用意します。

で, 木に関する dfs(v) (v は訪れている頂点) で以下のようなことをします。

後に頂点 v 以下の子を探索することで, 各高さのフラグ(xor_h)がどうなっているのかをチェックします。しかし, 高さが h の頂点全部について, xor_h はフラグを取ってしまうので, v の子の頂点のみを影響させるには, 先に xor_h[h] を加えておけば良いです(そうすれば, ダブっているところは xor で 0 になるので関係なくなる)。ちょっと説明下手ですが許してください。

で, 実際に v の各子について dfs をします。
その後, もう一度 xor_h で xor をとります。これで, 頂点 v 以下の高さ h の点がどのようなフラグを持つかを求めることが出来ました。

これを利用して, 各クエリについて回文かどうかを判定します。

const int MAX = 500500;
int query_h[MAX];
vector<int> query_v[MAX];
char s[MAX];
vector<vector<int> > G;
int ret[MAX];
int xor_h[MAX];

int n, m;

void dfs(int v, int d) {
    for (int q : query_v[v]) {
        ret[q] = xor_h[query_h[q]];
    }
    for (int ch : G[v]) {
        dfs(ch, d+1);
    }
    xor_h[d] ^= 1<<(s[v]-'a');
    for (int q : query_v[v]) {
        ret[q] ^= xor_h[query_h[q]];
    }
}

int main() {
    scanf("%d%d", &n, &m);
    G.resize(n);
    for (int i = 1; i < n; i++) {
        int p;
        scanf("%d", &p);
        p--;
        G[p].push_back(i);
    }
    scanf("%s", s);
    for (int i = 0; i < m; i++) {
        int v, h;
        scanf("%d %d", &v, &h);
        v--;
        query_v[v].push_back(i);
        query_h[i] = h;
    }
    dfs(0, 1);
    for (int i = 0; i < m; i++) {
        int cnt = __builtin_popcount(ret[i]);
        if (cnt <= 1) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}