CF570D Tree Requests

题意

给定一棵根为 \(1\) 的有根树，以及字符串 \(S\)。

• \(x, h\) 求 \(x\) 的子树内，深度为 \(h\) 的节点的字符能否重排为一个回文串。

Sol

不难发现，回文串显然至多有一个字符出现奇数个。

所以我们对于每种字符随机附权值，维护前缀异或值。

查询时枚举 \(26\) 种为奇数的情况，这是显然平凡的。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#include <random>
#include <vector>
#include <ctime>
#include <cassert>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
string read_() {
	string ans;
	char c = getchar();
	while (c < 'a' || c > 'z')
		c = getchar();
	while (c >= 'a' && c <= 'z') {
		ans += c;
		c = getchar();
	}
	return ans;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
const int N = 5e5 + 5, M = 1e6 + 5;

namespace G {

array <int, N> fir;
array <int, M> nex, to;
int cnt;
void add(int x, int y) {
	cnt++;
	nex[cnt] = fir[x];
	to[cnt] = y;
	fir[x] = cnt;
}

}


string s;
array <int, 28> cur;

array <vector <int>, N> isl;

namespace Hpt {

using G::fir; using G::nex; using G::to;

array <int, N> siz, dep, fa, son;

void dfs1(int x) {
	siz[x] = 1;
	for (int i = fir[x]; i; i = nex[i]) {
		if (to[i] == fa[x]) continue;
		dep[to[i]] = dep[x] + 1;
		fa[to[i]] = x;
		dfs1(to[i]);
		siz[x] += siz[to[i]];
		if (siz[to[i]] > siz[son[x]]) son[x] = to[i];
	}
}

array <int, N> dfn, top, idx;
int cnt;

void dfs2(int x, int Mgn) {
	cnt++;
	dfn[x] = cnt;
	idx[cnt] = x;
	top[x] = Mgn;
	isl[dep[x]].push_back(dfn[x]);
	if (son[x]) dfs2(son[x], Mgn);
	for (int i = fir[x]; i; i = nex[i]) {
		if (to[i] == fa[x] || to[i] == son[x]) continue;
		dfs2(to[i], to[i]);
	}
}

}
namespace Bit {

array <int, N> edge;

int lowbit(int x) {
	return x & -x;
}

void modify(int x, int y, int n) {
	while (x <= n) {
		edge[x] ^= y;
		x += lowbit(x);
	}
	return;
}
int query(int x) {
	int ans = 0;
	while (x) {
		ans ^= edge[x];
		x -= lowbit(x);
	}
	return ans;
}

}
array <int, N> prl;

signed main() {
	int n = read(), q = read();
	for (int i = 2; i <= n; i++) {
		int x = read();
		G::add(i, x), G::add(x, i);
	}
	s = " " + read_();
	mt19937_64 rnd(time(0));
	for (int i = 1; i <= 26; i++)
		cur[i] = rnd() % 147744151;
	Hpt::dfs1(1), Hpt::dfs2(1, 0);
	int cnt = 0;
	for (int i = 0; i <= n; i++) {
		for (auto x : isl[i]) {
			cnt++;
			Bit::modify(cnt, cur[s[Hpt::idx[x]] - 'a' + 1], n);
		}
		prl[i] += prl[i - 1] + isl[i].size();
	}
	while (q--) {
		int x = read(), y = read() - 1;
		int l = Hpt::dfn[x], r = Hpt::dfn[x] + Hpt::siz[x] - 1;
		if (!isl[y].size()) {
			puts("Yes");
			continue;
		}
		int st = lower_bound(isl[y].begin(), isl[y].end(), l) - isl[y].begin() + 1,
			ed = 0;
		auto it = upper_bound(isl[y].begin(), isl[y].end(), r);
		ed = it - isl[y].begin();
		st += prl[y - 1], ed += prl[y - 1];
		int tp = Bit::query(ed) ^ Bit::query(st - 1);
		/* for (auto k : isl[y]) */
			/* write(k), putchar(32); */
		/* puts(""); */
		/* write(st), putchar(32); */
		/* write(ed), puts(""); */
		bool flg = 0;
		for (int i = 0; i <= 26; i++) {
			if (tp ^ cur[i]) continue;
			flg = 1;
		}
		if (flg) puts("Yes");
		else puts("No");
	}
	return 0;
}