cfD.cpp

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <string.h>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

const int maxN = 500010;

int in[maxN];
int out[maxN];
vector<int> matrix[maxN];
vector<int> depth[maxN];
int dep[maxN];
char letters[maxN];
int tx = 1;

void getDepth() {
	queue<pair<int, int> > q;
	dep[1] = 1;
	depth[1].push_back(1);
	q.push(make_pair(1, 1));
	while (!q.empty()) {
		pair<int, int> now = q.front(); q.pop();
		for (int i = 0; i < (int)matrix[now.first].size(); i++) {
			dep[matrix[now.first][i]] = now.second + 1;
			depth[now.second + 1].push_back(matrix[now.first][i]);
			q.push(make_pair(matrix[now.first][i], now.second + 1));
		}
	}
}

void getInOut(int current) {
	in[current] = tx++;
	for (int i = 0; i < matrix[current].size(); i++)
		getInOut(matrix[current][i]);
	out[current] = tx++;
}

int isIn(int a, int b) {
	return in[a] <= in[b] && out[b] <= out[a];
}

int isLeft(int a, int b) {
	return out[b] < in[a];
}


map<pair<int, int>, int> mem;

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);

	for (int i = 2, j; i <= n; i++) {
		cin >> j;
		matrix[j].push_back(i);
	}
	scanf("%s", letters);
	tx = 1;
	getDepth();
	getInOut(1);

	for (int i = 0; i < m; i++) {
		int v, h;
		scanf("%d%d", &v, &h);;

		if (dep[v] >= h) {
			puts("Yes");
			continue;
		}

		if (mem[make_pair(v, h)] == 1)puts("Yes");
		else if (mem[make_pair(v, h)] == -1) puts("No");
		else {
			int ans = -1;
			int l = 0, r = depth[h].size() - 1, m;
			while (l <= r) {
				m = (l + r) >> 1;
				if (isIn(v, depth[h][m])) {
					ans = m;
					r = m - 1;
				}
				else {
					if (isLeft(v, depth[h][m]))
						l = m + 1;
					else r = m - 1;
				}

			}
			if (ans == -1) {
				puts("Yes");
				continue;
			}
			l = 0, r = (int)depth[h].size() - 1;
			int ans2 = -1;
			while (l <= r) {
				m = (l + r) >> 1;
				if (isIn(v, depth[h][m])) {
					ans2 = m;
					l = m + 1;
				}
				else {
					if (isLeft(v, depth[h][m]))
						l = m + 1;
					else r = m - 1;
				}
			}

			if (ans2 == -1) {
				puts("Yes");
				continue;
			}

			char deg[26];
			for (int i = 0; i < 26; i++)
				deg[i] = 0;

			for (int i = ans; i <= ans2; i++)
				deg[letters[depth[h][i] - 1] - 'a']++;


			int x = 0;
			for (int i = 0; i < 26; i++) {
				x += deg[i] & 1;
			}

			if (x <= 1) {
				puts("Yes");
				mem[make_pair(v, h)] = 1;
			}
			else {
				puts("No");
				mem[make_pair(v, h)] = -1;
			}
		}
	}
	return 0;
}