【CF 570D】Tree Requests
【CF|【CF 570D】Tree Requests】树节点标号递增 规定父亲标号<儿子
dfs重标号 同时用一个数组存该节点为根的树的最小节点 一个数组存该节点为树根的最大节点 一个数组存对应深度存在的节点 再来一个数组存每一位置累计字符(26个字符 由于偶数次可压缩 故用异或即可)
每查询一个节点和他对应的深度 只需在该深度查该节点为根的最小和最大节点 然后用左右节点字符累计数互相异或 最后看它二进制存在几个奇数 两个以上便无法成回文。。
代码写挫了 胆小慎点
#include
#define INF 0x3f3f3f3fusing namespace std;
typedef struct Edge
{
int v,next;
}Edge;
char str[500005];
set dep[500001];
set ::iterator it;
Edge eg[500000];
int head[500001],hn[500001];
int in[500001],out[500001];
int num[500001],inh[500001];
int aa[500001];
int tp,cnt;
void dfs(int site,int h)
{
in[site] = ++cnt;
aa[cnt] = site;
dep[h].insert(cnt);
num[in[site]] = num[inh[h]]^(1<<(str[site]-'a'));
inh[h] = in[site];
int i;
for(i = head[site];
i != -1;
i = eg[i].next)
{
dfs(eg[i].v,h+1);
}
out[site] = cnt;
}int main()
{
int n,m,i,x,u,h,l,r,tmp;
scanf("%d %d",&n,&m);
tp = 0;
cnt = 0;
memset(head,-1,sizeof(head));
memset(hn,-1,sizeof(hn));
for(i = 2;
i <= n;
++i)
{
scanf("%d",&x);
if(hn[x] == -1)head[x] = tp;
else eg[hn[x]].next = tp;
eg[tp].v = i;
eg[tp].next = -1;
hn[x] = tp++;
}for(i = 1;
i<= 500000;
++i)
{
dep[i].insert(0);
dep[i].insert(INF);
}
memset(inh,0,sizeof(inh));
memset(num,0,sizeof(num));
scanf("%s",str+1);
dfs(1,1);
while(m--)
{
scanf("%d %d",&u,&h);
l = *dep[h].lower_bound(in[u]);
it = dep[h].lower_bound(out[u]);
if(*it != out[u]) --it;
// printf("%d %d %d %d\n",l,*it,num[l],num[*it]);
if(l <= in[u] || *it <= in[u]) puts("Yes");
else
{
l = num[l]^(num[*it])^(1<<(str[aa[l]]-'a'));
tmp = 0;
while(l)
{
if(l&1) tmp++;
l >>= 1;
}
if(tmp > 1) puts("No");
else puts("Yes");
}
}
return 0;
} 推荐阅读
- Codeforces Round #585 (Div. 2) F. Radio Stations
- CodeForces CF #499 Div.2 赛后补题
- #|C. Choosing flowers（枚举+思维+二分）
- #|A. Distance and Axis（思维） Codeforces Round #665 (Div. 2)
- #|D. Distinct Characters Queries（set处理） Codeforces Round #590 (Div. 3)
- #|C. Mere Array（排序+思维） Codeforces Round #665 (Div. 2)
- cf|Codeforces1182E Product Oriented Recurrence(递推+矩乘快速幂）
- cf|Codeforces1182F Maximum Sine (类欧几里得)
- 题解|Codeforces Round #643 (Div. 2)【A—D】
- CodeForces 14B Young Photographer