锐客网

  1. 首页 > it技术 > >

online|Codeforces Round #316 (Div. 2)D. Tree Requests

数据结构其他codeforces前缀和onlinejudgedfs序

链接：http://codeforces.com/contest/570/problem/D
题意：给定一棵n个节点的树(1为根)，每个节点上有一个小写字母，m个询问：给定v,h，问在以v为根的子树中深度为h(相对整棵树的深度)的所有点的字符能否组成回文串。
分析：我们来将题目分解一下，首先我们确定构成回文串的条件，很显然要求“字母个数为奇数的字母小于等于1”，这里我们可以用异或储存偶数为0奇数为1，这样我们只要判断这个二进制数中有几个1就行了。然后我们分析子树v和深度h这两个条件，首先子树v我们可以想到dfs序可以将一颗子树的节点排在一段连续的位置，深度h我们可以想到从根开始bfs的话相同深度的点也会在一起。那么我们可以将这两个条件结合一下得到：bfs的同一层的点是在一段连续的区间内，并且也有同一颗子树中的同一深度的节点也会在一段连续的区间内，那么我们在这段区间中找dfs序在根v的dfs序范围内的点就好了，然后将异或值用前缀异或和优化即可。详见代码。O(n+m*logn)
代码：

#include #include #include #include #include #include #include #include #include #include #include #include #pragma comment(linker, "/STACK:102400000,102400000") using namespace std; const int N=500100; const int MAX=151; const int mod=100000000; const int MOD1=1000000007; const int MOD2=1000000009; const double EPS=0.00000001; typedef long long ll; const ll MOD=998244353; const ll INF=10000000010; typedef double db; typedef unsigned long long ull; int tot,u[N],v[N],pre[N]; void add(int x,int y) { v[tot]=y; pre[tot]=u[x]; u[x]=tot++; } char s[N]; int H,ti,l[N],r[N],de[N]; void dfs(int x,int y) { l[x]=++ti; de[x]=de[y]+1; H=max(H,de[x]); for (int i=u[x]; i!=-1; i=pre[i]) dfs(v[i],x); r[x]=ti; } int d[N],w[N],bl[N],br[N],sum[N]; void bfs() { int i,b=1,k=1,deep; memset(br,0,sizeof(br)); memset(bl,0x3f,sizeof(bl)); d[1]=w[1]=bl[1]=br[1]=1; while (b<=k) { for (i=u[d[b]]; i!=-1; i=pre[i]) { k++; d[k]=v[i]; w[k]=l[v[i]]; deep=de[v[i]]; bl[deep]=min(bl[deep],k); br[deep]=max(br[deep],k); } b++; } } int getl(int x,int y,int z) { int mid=(y+z)/2; while (y+1=x) { z=mid; mid=(y+z)/2; } else { y=mid; mid=(y+z)/2; } return z; } int getr(int x,int y,int z) { int mid=(y+z)/2; while (y+1y||l[x]==r[x]||y>H) printf("Yes\n"); else { L=getl(l[x],bl[y]-1,br[y]); R=getr(r[x],bl[y],br[y]+1); if (cala(sum[R]^sum[L-1])<=1) printf("Yes\n"); else printf("No\n"); } } return 0; }



    推荐阅读


    上一篇：#|51nod1227 平均最小公倍数

    下一篇：使用|使用 Linux 实用程序 gPhoto2 备份手机存储 | Linux 中国