离线 + 树状数组
如果子树中的一个深度的所有点中有两个以上的字母出现了奇数次，那么这个询问的答案就是$No$，其他的情况吧都是$Yes$。
由于只有$26$个字母，我们可以考虑暴力检验，把树映射到$dfs$序上然后看一看子树区间中每一个字母出现了多少次。
我先写了一个动态开点的线段树，然后$O(26 * (n + q)logn)$完美爆炸了。
然后我们发现一个深度的所有点是可以相互利用的，这样子只要堆所有的询问离线一下按照深度排个序就好了，开$26$个树状数组单点修改+ 区间求和就做完了。
感觉速度飞快。
时间复杂度$O(nlogn + 26 * qlogn)$。
Code：
文章图片
文章图片
#include#include #include #include using namespace std; const int N = 5e5 + 5; const int M = 30; int n, qn, tot = 0, head[N]; int dfsc = 0, dep[N], id[N], siz[N]; char let[N]; vector vec[N]; struct Edge { int to, nxt; } e[N << 1]; inline void add(int from, int to) { e[++tot].to = to; e[tot].nxt = head[from]; head[from] = tot; }struct Querys { int x, h, res, id; friend bool operator < (const Querys &u, const Querys &v) { return u.h < v.h; }} q[N]; inline void read(int &X) { X = 0; char ch = 0; int op = 1; for(; ch > '9'|| ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; }bool cmp(int x, int y) { return dep[x] < dep[y]; }inline void chkMax(int &x, int y) { if(y > x) x = y; }void dfs(int x, int fat, int depth) { dep[x] = depth, id[x] = ++dfsc, siz[x] = 1; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(y == fat) continue; dfs(y, x, depth + 1); siz[x] += siz[y]; } }namespace Bit { int s[M][N]; #define lowbit(p) (p & (-p))inline void modify(int t, int p, int v) { for(; p <= n; p += lowbit(p)) s[t][p] += v; }inline int query(int t, int p) { int res = 0; for(; p > 0; p -= lowbit(p)) res += s[t][p]; return res; }} using namespace Bit; int main() { //freopen("Sample.txt", "r", stdin); //freopen("my.out", "w", stdout); read(n), read(qn); for(int fat, i = 2; i <= n; i++) { read(fat); add(fat, i), add(i, fat); } dfs(1, 0, 1); int maxd = 0; for(int i = 1; i <= n; i++) { chkMax(maxd, dep[i]); vec[dep[i]].push_back(i); }scanf("%s", let + 1); for(int i = 1; i <= qn; i++) { q[i].res = 0, q[i].id = i; read(q[i].x), read(q[i].h); }sort(q + 1, q + 1 + qn); for(int i = 1; i <= qn; i++) { int lst = i; for(; q[i].h == q[lst].h; i++); i--; if(q[i].h > maxd) continue; int vecSiz = vec[q[i].h].size(); for(int j = 0; j < vecSiz; j++) { int pos = vec[q[i].h][j]; modify(let[pos] - 'a', id[pos], 1); }for(int j = lst; j <= i; j++) for(int c = 0; c < 26; c++) { int tmp = query(c, id[q[j].x] + siz[q[j].x] - 1) - query(c, id[q[j].x] - 1); if(tmp & 1) ++q[q[j].id].res; }for(int j = 0; j < vecSiz; j++) { int pos = vec[q[i].h][j]; modify(let[pos] - 'a', id[pos], -1); } }/*for(int i = 1; i <= qn; i++) printf("%d ", q[i].res); printf("\n"); */for(int i = 1; i <= qn; i++) if(q[i].res <= 1) puts("Yes"); else puts("No"); return 0; }
View Code
【CF570D|CF570D Tree Requests】转载于:https://www.cnblogs.com/CzxingcHen/p/9911207.html
