コード
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.NoSuchElementException;
public class Main {
public void solve() {
FastScanner scanner = new FastScanner();
int N = scanner.nextInt();
int Q = scanner.nextInt();
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
for (int i = 0; i < N; i++) {
graph.add(new ArrayList<Integer>());
}
for (int to = 1; to < N; to++) {
int from = scanner.nextInt() - 1;
graph.get(from).add(to);
}
char[] string = scanner.next().toCharArray();
ArrayList<ArrayList<Integer>> queryV = new ArrayList<>();
for (int i = 0; i <= N; i++) {
queryV.add(new ArrayList<Integer>());
}
int[] queryH = new int[Q];
for (int queryID = 0; queryID < Q; queryID++) {
int v = scanner.nextInt() - 1;
int h = scanner.nextInt();
queryV.get(v).add(queryID);
queryH[queryID] = h;
}
int[] ansBit = new int[Q];
int[] xorH = new int[N + 1];
ArrayDeque<Integer[]> dfs = new ArrayDeque<>();
dfs.push(new Integer[] { 0, 1 });
boolean[] visited = new boolean[N];
while (!dfs.isEmpty()) {
int from = dfs.peek()[0];
int depth = dfs.peek()[1];
if (!visited[from]) {
visited[from] = true;
for (int queryID : queryV.get(from)) {
ansBit[queryID] = xorH[queryH[queryID]];
}
for (int to : graph.get(from)) {
dfs.push(new Integer[] { to, depth + 1 });
}
} else {
int strBit = 1 << (string[from] - 'a');
xorH[depth] ^= strBit;
for (int queryID : queryV.get(from)) {
ansBit[queryID] ^= xorH[queryH[queryID]];
}
dfs.pop();
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < Q; i++) {
if (Integer.bitCount(ansBit[i]) > 1) {
sb.append("No\n");
} else {
sb.append("Yes\n");
}
}
System.out.print(sb.toString());
}
public static void main(String[] args) {
new Main().solve();
}
}
class FastScanner {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int ptr = 0;
private int buflen = 0;
private boolean hasNextByte() {
if (ptr < buflen) {
return true;
} else {
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
if (buflen <= 0) {
return false;
}
}
return true;
}
private int readByte() {
if (hasNextByte())
return buffer[ptr++];
else
return -1;
}
private static boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private void skipUnprintable() {
while (hasNextByte() && !isPrintableChar(buffer[ptr]))
ptr++;
}
public boolean hasNext() {
skipUnprintable();
return hasNextByte();
}
public String next() {
if (!hasNext())
throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b = readByte();
while (isPrintableChar(b)) {
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
public int nextInt() {
return (int) nextLong();
}
public long nextLong() {
if (!hasNext())
throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (b < '0' || '9' < b) {
throw new NumberFormatException();
}
while (true) {
if ('0' <= b && b <= '9') {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) {
return minus ? -n : n;
} else {
throw new NumberFormatException();
}
b = readByte();
}
}
}