Codeforces Round 316 (Div. 2) D题 Tree Requests（二分，dfs，在线，前缀异或）

题目链接

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

思路

将$26$个字母全部当作一个二进制数。

将每个深度的结点按照dfs序放到一个vector里，同时记录每个vector对应的前缀异或。

对于每一个询问x，只需在给定深度里找到$\ge$L[x]和$\le$R[x]的两个端点，取区间异或和即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5 + 5;
int n, m;
int depth[N], L[N], R[N], ID[N], tim;
char s[N];
vector<int>mp[N], XOR[N], dep[N];
int lowbit(int x) {return (x) & (-x);}
void dfs(int u, int deep)
{tim++;depth[u] = deep;L[u] = tim;ID[tim] = u;dep[deep].push_back(L[u]);for (int j : mp[u]){dfs(j, deep + 1);}R[u] = tim;
}
void solve()
{cin >> n >> m;for (int i = 2, p; i <= n; i++){cin >> p;mp[p].push_back(i);}for (int i = 1; i <= n; i++){cin >> s[i];}dfs(1, 1);int maxdeep = *max_element(depth + 1, depth + 1 + n);for (int i = 1; i <= maxdeep; i++){XOR[i].push_back(1ll << (s[ID[dep[i][0]]] - 'a'));for (int j = 1; j < dep[i].size(); j++){XOR[i].push_back(XOR[i][j - 1] ^ (1ll << (s[ID[dep[i][j]]] - 'a')));}}while (m--){int x, d, ans = 0;cin >> x >> d;int l = lower_bound(dep[d].begin(), dep[d].end(), L[x]) - dep[d].begin();int r = upper_bound(dep[d].begin(), dep[d].end(), R[x]) - dep[d].begin();r--;if (r < 0){cout << "Yes" << endl;}else{if (l == 0) ans = XOR[d][r];else ans = XOR[d][l - 1] ^ XOR[d][r];if (ans == lowbit(ans)){cout << "Yes" << endl;}else cout << "No" << endl;}}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}