描述
题解
这个题也没有想象中那么难,主要是对 dfs 序进行处理,我们获取 dfs 序的过程中,记录下来每个子树在 dfs 序中的位置区域,同时也要记录下来不同深度的结点,添加到 vector 中,当然,添加的顺序也是满足 dfs 序的,这样,我们在查找的过程中利用二分即可查找到对应的区段。这个题综合性挺强的,可以好好看看。
代码
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 5e5 + 10;
const int MAX_LETTER = 27;
int n, m;
int cnt, max_h;
char s[MAXN];
int high[MAXN];
int POW[MAX_LETTER];
vector<int> E[MAXN];
vector<int> A[MAXN];
vector<int> B[MAXN];
pair<int, int> order[MAXN]; // dfs 序
void dfs(int x, int h)
{
max_h = max(h, max_h);
high[x] = h;
order[x].first = ++cnt;
A[h].push_back(POW[s[x - 1] - 'a']);
B[h].push_back(cnt);
for (int i = 0; i < E[x].size(); i++)
{
dfs(E[x][i], h + 1);
}
order[x].second = cnt;
}
int solve(int x, int h)
{
if (h <= high[x] || !B[h].size())
{
return 1;
}
int l = (int)(lower_bound(B[h].begin(), B[h].end(), order[x].first) - B[h].begin());
int r = (int)(upper_bound(B[h].begin(), B[h].end(), order[x].second) - B[h].begin() - 1);
if (l > r)
{
return 1;
}
int ans = A[h][r] ^ (l ? A[h][l - 1] : 0);
if (ans == (ans & (-ans)))
{
return 1;
}
return 0;
}
void init()
{
cnt = max_h = 0;
POW[0] = 1;
for (int i = 1; i < MAX_LETTER; i++)
{
POW[i] = POW[i - 1] << 1;
}
}
template <class T>
inline void scan_d(T &ret)
{
char c;
ret = 0;
while ((c = getchar()) < '0' || c > '9');
while (c >= '0' && c <= '9')
{
ret = ret * 10 + (c - '0'), c = getchar();
}
}
int main()
{
init();
scan_d(n), scan_d(m);
int x;
for (int i = 2; i <= n; i++)
{
scan_d(x);
E[x].push_back(i);
}
scanf("%s", s);
dfs(1, 0);
max_h++;
for (int i = 0; i < max_h; i++)
{
for (int j = 1; j < A[i].size(); j++)
{
A[i][j] ^= A[i][j - 1];
}
}
int v, h;
while (m--)
{
scan_d(v), scan_d(h);
if (solve(v, h - 1))
{
puts("Yes");
}
else
{
puts("No");
}
}
return 0;
}