题意：给定一棵树，n个节点，每个节点处有一个字母，结点的深度定义为节点到根结点1的距离，
有m个询问（u，v），每次回答以结点u为根的子树的深度为v的那些节点处的字母能否组成一个回文串，特别的，空串也是回文串。
思路：首先说明判断回文串的方法，只要出现次数为奇数个字母个数不超过2，那么这些字母一定可以组成回文串。
接下来考虑将树转成线性结构。
利用dfs+时间戳将结点按照深度存入一个线性结构里，Depth[i]数组里存的是深度为i的所有结点，
那么对于询问有三种情况，，一种是dep[u]>=v输出Yes
第二种是desdep[u]<v(以结点u为根的子树中的最大节点深度)，输出Yes
剩余情况为第三种，比较复杂也是我们要解决的问题
因为以结点u为根的深度为v的结点在Dep[v]数组中下标肯定是连续的，
所以利用时间戳两次二分找到以结点u为根的深度为v的结点在Dep[v]数组中的起始下标ql和截止下标qr，
因为我们只需要判断每个字母是否出现奇数次，所以我们可以用一个长26位的状态表示每个字母出现奇数次还是偶数次，
而且这样的话这个状态具有一个很优美的性质，可以通过异或来转移状态
那么这样我们只需要预处理出每个深度的前缀的状态su[dep][i]即可，
判断时只需判断su[dep][qr] xor su[dep][ql-1]中有多少位为1即可，
若一的位数小于2输出Yes，否则输出No。
#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<iostream>#include<algorithm>#include<vector>#include<map>#include<queue>#include<stack>#include<string>#include<map>#include<set>#include<ctime>#define eps 1e-6#define LL long long#define pii (pair<int, int>)//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;const int maxn = 500000+1000;//const int INF = 0x3f3f3f3f;vector<int> G[maxn];vector<int> Depth[maxn], su[maxn];int w[maxn];int dep[maxn], tim[maxn][2], desdep[maxn];int n, m, clock_cnt;char str[maxn];void dfs(int cur) {desdep[cur] = dep[cur];tim[cur][0] = ++clock_cnt;for(int i = 0; i < G[cur].size(); i++) {int u = G[cur][i];dep[u] = dep[cur] + 1;Depth[dep[u]].push_back(u);dfs(u);desdep[cur] = max(desdep[cur], desdep[u]);}tim[cur][1] = ++clock_cnt;}void init() {int d = 1;while(1) {int sz = Depth[d].size();if(!sz) break;for(int i = 0; i < sz; i++) {int t = w[Depth[d][i]];int tmp = su[d][i];su[d].push_back(tmp^(1<<t));}d++;}}bool check(int dep, int ql, int qr) {int palin = su[dep][qr]^su[dep][ql];int cnt = 0;for(int i = 0; i < 26; i++) {if((1<<i)&palin) cnt++;}if(cnt>1) return false;return true;}int main() {//freopen("input.txt", "r", stdin);while(scanf("%d%d", &n, &m) == 2) {for(int i = 1; i <= n; i++) G[i].clear(), Depth[i].clear(), su[i].clear();for(int i = 1; i <= n; i++) su[i].push_back(0);clock_cnt = 0;for(int i = 2; i <= n; i++) {int t; scanf("%d", &t);G[t].push_back(i);}Depth[1].push_back(1), dep[1] = 1;scanf("%s", str);for(int i = 1; i <= n; i++) w[i] = str[i-1]-'a';dfs(1);init();//for(int i = 1; i <= n; i++) cout << tim[i][0] << " " << tim[i][1] << endl;for(int i = 0; i < m; i++) {int u, v; scanf("%d%d", &u, &v);if(dep[u] >= v) printf("Yes\n");else if(desdep[u] < v) printf("Yes\n");else {int ql, qr;int L = 0, R = Depth[v].size()-1;while(L < R) {int M = (L+R)>>1;int tmp = Depth[v][M];if(tim[tmp][0] > tim[u][0]) R = M;else L = M+1;}ql = R;L = 0, R = Depth[v].size()-1;while(L <= R) {int M = (L+R)>>1;int tmp = Depth[v][M];if(tim[tmp][1] > tim[u][1]) R = M-1;else L = M+1;}qr = R;if(check(v, ql, qr+1)) printf("Yes\n");else printf("No\n");}}}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
梦想，并不奢侈，只要勇敢地迈出第一步。
