首页 > 代码库 > dfs序题目练习
dfs序题目练习
参考博文:http://blog.csdn.net/qwe2434127/article/details/49819975
http://blog.csdn.net/qq_24489717/article/details/50569644
dfs序比较重要的性质：一棵子树的所有节点在dfs序里是连续一段，主要就是利用这个性质来解题.
作为预处理，首先将将树的所有节点按深度保存起来，每个深度的所有节点用一个线性结构保存，每个深度的节点相对顺序要和前序遍历一致。
然后从树的根节点进行dfs，对于每个节点记录两个信息，一个是dfs进入该节点的时间戳in[id]，另一个是dfs离开该节点的时间戳out[id]。
最后对于每次查询，求节点v在深度h的所有子节点，只需将深度为h并且dfs进入时间戳在in[v]和out[v]之间的所有节点都求出来即可，由于对于 每个深度的所有节点，相对顺序和前序遍历的顺序以致，那么他们的dfs进入时间戳也是递增的，于是可以通过二分搜索求解。
Poj 3321:
题型一：对某个点X权值加上一个数W，查询某个子树X里所有点权值和。
解：列出dfs序，实现修改一个数，查询一段序列的和，显然这个序列可以用树状数组维护。
#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>using namespace std;typedef long long LL;const int N = 500005;struct Edge{ int v,next;}edge[N];int head[N],tot,c[N];int in[N],out[N];bool have[N];int cnt;void init(){ tot = 0; cnt = 0; memset(head,-1,sizeof(head)); memset(c,0,sizeof(c));}void addEdge(int u,int v,int &k){ edge[k].v = v,edge[k].next = head[u],head[u] = k++;}void dfs(int u){ in[u] = ++cnt; for(int k=head[u];k!=-1;k=edge[k].next){ dfs(edge[k].v); } out[u] = ++cnt;}int lowbit(int x){ return x&(-x);}int getsum(int id){ int sum = 0; for(int i=id;i>=1;i-=lowbit(i)){ sum+=c[i]; } return sum;}void update(int id,int x){ for(int i=id;i<=cnt;i+=lowbit(i)){ c[i]+=x; }}int main(){ int n,m; while(scanf("%d",&n)!=EOF){ init(); for(int i=0;i<n-1;i++){ int u,v; scanf("%d%d",&u,&v); addEdge(u,v,tot); } dfs(1); /*for(int i=1;i<=n;i++){ printf("%d %d\n",in[i],out[i]); }*/ for(int i=1;i<=n;i++){ have[i] = 1; update(in[i],1); } int q; scanf("%d",&q); while(q--){ char s[5]; int x; scanf("%s%d",s,&x); if(s[0]==‘Q‘){ printf("%d\n",getsum(out[x])-getsum(in[x]-1)); }else{ if(have[x]) update(in[x],-1); else update(in[x],1); have[x] = !have[x]; } } } return 0;}
hdu 3886 :
统计某一个结点下面比编号比其小的结点数目.
#pragma comment(linker,"/STACK:1024000000,1024000000")#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>using namespace std;typedef long long LL;const int N = 500005;struct Edge{ int v,next;}edge[N];int head[N],tot,c[N];int in[N],out[N];bool have[N];int cnt;void init(){ tot = 0; cnt = 0; memset(head,-1,sizeof(head)); memset(c,0,sizeof(c));}void addEdge(int u,int v,int &k){ edge[k].v = v,edge[k].next = head[u],head[u] = k++;}void dfs(int u,int fa){ in[u] = ++cnt; for(int k=head[u];k!=-1;k=edge[k].next){ if(edge[k].v == fa) continue; dfs(edge[k].v,u); } out[u] = ++cnt;}int lowbit(int x){ return x&(-x);}int getsum(int id){ int sum = 0; for(int i=id;i>=1;i-=lowbit(i)){ sum+=c[i]; } return sum;}void update(int id,int x){ for(int i=id;i<=cnt;i+=lowbit(i)){ c[i]+=x; }}int main(){ int n,q; while(scanf("%d%d",&n,&q)!=EOF,n+q){ init(); for(int i=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); addEdge(u,v,tot); addEdge(v,u,tot); } dfs(q,-1); bool flag = true; for(int i=1;i<=n;i++){ if(!flag) printf(" "); printf("%d",getsum(out[i])-getsum(in[i]-1)); flag = false; update(in[i],1); } printf("\n"); } return 0;}
update中...
dfs序题目练习
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。