CF|【CF 570D】Tree Requests CF|DFS&BFS

【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; }

CF|【CF 570D】Tree Requests

推荐阅读

车子低速起步咔咔响车辆低速行驶有咔咔响

快速提高情商的5大方法

mongodb参数 mongodb 函数性能

为什么斗鱼的服务器消失了？斗鱼怎么看不见服务器了

超好听的男生女生网名独特好听男生女生网名

龟苓膏和烧仙草的区别有什么

肠粉添加硼砂的比例请查看答案

jquery自适应位置，js自适应

联想电视屏幕出现竖线维修报价

香椿用热水烫完之后用过凉水吗

男性包皮过长是什么原因造成的

iphone14pro暗夜紫色，Iphone屏幕上方出现暗紫色圆圈

三星tab s6 lite 三星tab s

进天国的七大条件天国在哪里

加湿器里面可以加香薰精油吗

极左是什么意思极右是什么意思

牛皮

猪肉价格今日价最新价

新车贴车衣的好处和坏处有哪些新车贴车衣的好处和坏处

什么叫危机公关