锐客网

  1. 首页 > it技术 > >

Codeforces Round #316 (Div. 2) D. Tree Requests (DFS序)

DFS

【Codeforces Round #316 (Div. 2) D. Tree Requests (DFS序)】题目地址：http://codeforces.com/contest/570/problem/D
比赛的时候实在没想到DFS序，。。想到DFS序后，分别存起每个深度的所有节点的DFS序，处理出前缀异或和，然后二分找到两个端点，再异或一下，就求出了所求区间的异或和，由于偶数次的都被异或掉了，所以判断下奇数次数是否大于1即可。
代码如下：

#include #include #include #include #include #include #include #include #include #include using namespace std; #define LL long long #define pi acos(-1.0) #pragma comment(linker, "/STACK:1024000000") const LL mod=3221225473; const int INF=0x3f3f3f3f; const double eqs=1e-9; const int MAXN=500000+10; vectorvec[MAXN]; vector::iterator it; int in[MAXN], out[MAXN], sum[MAXN]; int head[MAXN], cnt, now; char s[MAXN]; struct node { int u, v, next; }edge[MAXN]; void add(int u, int v) { edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void init(int n) { memset(head,-1,sizeof(head)); cnt=now=0; memset(sum,0,sizeof(sum)); for(int i=1; i<=n; i++){ vec[i].clear(); vec[i].push_back(0); } } void dfs(int u, int h) { now++; sum[now]=sum[*(--vec[h].end())]^(1<'a'); vec[h].push_back(now); in[u]=now; for(int i=head[u]; i!=-1; i=edge[i].next){ int v=edge[i].v; dfs(v,h+1); } out[u]=now; } int main() { int n, m, i, j, u, h, ans, l, r, flag; while(scanf("%d%d",&n,&m)!=EOF){ init(n); for(i=2; i<=n; i++){ scanf("%d",&u); add(u,i); } scanf("%s",s+1); dfs(1,1); while(m--){ scanf("%d%d",&u,&h); it=lower_bound(vec[h].begin(),vec[h].end(),out[u]); if((*it)!=out[u]) it--; r=sum[*it]; it=--lower_bound(vec[h].begin(),vec[h].end(),in[u]); l=sum[*it]; ans=r^l; flag=0; for(i=0; i<26; i++){ if(ans&(1<

    推荐阅读


    上一篇：Spring|Spring Boot 2.0 配置图文教程

    下一篇：17年1月9日，小程序来了。深度解析2017微信公开课