DFS序

总结：

1、树转化为线性：将树通过dfs转化为线性结构，这就是dfs序，和树链剖分有点相似

2、普通树转化为线段树：记录每个节点构成的树（子树）的起点和终点，起点是自己，这样每个点就构成了一个区间，然后对区间的操作就和线段树和树状数组一样了。

3、DFS序主要用来做子树的更新，因为DFS序中子树都是连续的。时间复杂度看树的储存结构，O（1）。

4、树的储存可以用图来存储，图的数组模拟邻接矩阵：小兵应该先武装好自己，然后再加入队伍，队长负责周转（管最前面一个）。

 

 

详解：

给定一棵n个节点的树，m次查询，每次查询需要求出某个节点深度为h的所有子节点。

 

对于这个问题如果试图去对每个节点保存所有深度的子节点，在数据大的时候内存会吃不消；或者每次查询的时候去遍历一遍，当数据大的时候，时间效率会非常低。

 

此时如果使用dfs序维护树结构就可以轻松地解决这个问题。

 

作为预处理，首先将将树的所有节点按深度保存起来，每个深度的所有节点用一个线性结构保存，每个深度的节点相对顺序要和前序遍历一致。

 

然后从树的根节点进行dfs，对于每个节点记录两个信息，一个是dfs进入该节点的时间戳in[id]，另一个是dfs离开该节点的时间戳out[id]。

 

最后对于每次查询，求节点v在深度h的所有子节点，只需将深度为h并且dfs进入时间戳在in[v]和out[v]之间的所有节点都求出来即可，由于对于每个深度的所有节点，相对顺序和前序遍历的顺序以致，那么他们的dfs进入时间戳也是递增的，于是可以通过二分搜索求解。

 

分析

Step 1：

如下图，可以看到，由于普通的树并不具有区间的性质，所以在考虑使用线段树作为解题思路时，需要对给给定的数据进行转化，首先对这棵树进行一次dfs遍历，记录dfs序下每个点访问起始时间与结束时间，记录起始时间是前序遍历，结束时间是后序遍历，同时对这课树进行重标号。

 

Step 2：

         如下图，DFS之后，那么树的每个节点就具有了区间的性质。

 

         那么此时，每个节点对应了一个区间，而且可以看到，每个节点对应的区间正好“管辖”了它子树所有节点的区间，那么对点或子树的操作就转化为了对区间的操作。

【PS: 如果对树的遍历看不懂的话，不妨待会对照代码一步一步调试，或者在纸上模拟过程~】

Step 3：

         这个时候，每次对节点进行更新或者查询，就是线段树和树状数组最基本的实现了…

 

树是一种非线性结构，一般而言，我们总是想办法将其转化为线性结构，将树上操作包括子树操作、路径操作等转化为数组上的区间操作，从而在一个较为理想的复杂度内加以解决。将树“拍平”的方法有很多，例如欧拉序、等。实际上欧拉序也是在DFS过程中得到的。不过通常而言，我们所说的DFS序是指：每个节点进出栈的时间序列。

 

考虑上图中树的DFS序，应为 

其中，每个节点均会出现2次，第一次是进入DFS的时刻，第二次是离开DFS的时刻。分别称之为In与Out。在区间操作中，如果某个节点出现了2次，则该节点将被“抵消”。所以通常会将Out时刻对应的点设置为负数。

树的DFS序列有几个有用的性质：

1. 任意子树是连续的。例如子树BEFK，在序列中对应BEEFKKFB；子树CGHI，在序列中对应连续区间CGGHHIIC。
2. 任意点对(a,b)之间的路径，可分为2种情况，首先令lca是a、b的最近公共祖先： 
   1. 若lca是a、b之一，则a、b之间的In时刻的区间或者Out时刻区间就是其路径。例如AK之间的路径就对应区间ABEEFK，或者KFBCGGHHIICA。
   2. 若lca另有其人，则a、b之间的路径为In[a]、Out[b]之间的区间或者In[b]、Out[a]之间的区间。另外，还需额外加上lca！！！考虑EK路径，对应为EFK再加上B。考虑EH之间的路径，对应为EFKKFBCGGH再加上A。

利用这些性质，可以利用DFS序列完成子树操作和路径操作，同时也有可能将应用到树上从而得到。

 

 

代码：

dfs序是处理树上问题很重要的一个武器，主要能够解决对于一个点，它的子树上的一些信息的维护。 

就比如那天百度之星round1A的1003题，就是dfs序+线段树维护每个点到0点的距离，然后对于每个点的更新，只需要更新它和它的子树上的点到0点的距离，查询的话就是它的子树上的最大值即可 

我的dfs序开的空间就是n，因为只在入的地方时间戳++，出来的地方时间戳不变，线段树的每个节点应该是时间戳

1 void dfs(int u,int fa){ 2     p1[u]=++ti; 3     dfsnum[ti]=u; 4     for(int i=head[u];i!=-1;i=edge[i].next){ 5         int v=edge[i].v; 6         if(v==fa) continue; 7         dfs(v,u); 8     } 9     p2[u]=ti;//时间戳不变，空间为O(n)10 }

 

例题：

需要在树上完成3类操作，单点更新，子树更新，以及根到指定节点的路径查询。利用性质1以及性质2.1即可完成，连LCA都无需求出。对整个DFS序列使用线段树进行维护，注意到整个序列实际上有正有负，因此额外用一个域来表示正数的个数。

4034: [HAOI2015]树上操作

Time Limit: 10 Sec  Memory Limit: 256 MB

Submit: 6323  Solved: 2094

[][][]

Description

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个

操作，分为三种：

操作 1 ：把某个节点 x 的点权增加 a 。

操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。

操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

Input

第一行包含两个整数 N, M 。表示点数和操作数。接下来一行 N 个整数，表示树中节点的初始权值。接下来 N-1 

行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。再接下来 M 行，每行分别表示一次操作。其中

第一个数表示该操作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。

 

Output

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

 

Sample Input

5 5

1 2 3 4 5

1 2

1 4

2 3

2 5

3 3

1 2 1

3 5

2 1 2

3 3

Sample Output

6

9

13

HINT

 

 对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。

 

Source

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 using namespace std;  6   7 int const SIZE = 100100;  8 typedef long long weight_t;  9  10 struct edge_t{
   //边  11     int to; 12     int next; 13 }Edge[SIZE<<1];//双向的  所以*2  14 int Vertex[SIZE]; 15 int ECnt; 16 weight_t W[SIZE]; 17  18 //数组模拟邻接矩阵：顶点记录的是下一个点，顶点负责转运  19 inline void mkEdge(int a,int b){
   //造a-b这条边  20     //先把节点的信息补充好，再建立联系 21     //先武装好自己，然后再图报效 22     //每个队的长官记录每个队节点的分配信息  23     Edge[ECnt].to = b; 24     Edge[ECnt].next = Vertex[a]; 25     Vertex[a] = ECnt++; 26  27     Edge[ECnt].to = a; 28     Edge[ECnt].next = Vertex[b]; 29     Vertex[b] = ECnt++; 30 } 31  32 int InIdx[SIZE],OutIdx[SIZE]; 33 int InOut[SIZE<<1]; 34 int NewIdx[SIZE<<1]; 35 int NCnt; 36  37 void dfs(int node,int parent){ 38     NewIdx[NCnt] = node; 39     InOut[NCnt] = 1; 40     InIdx[node] = NCnt++; 41     for(int next=Vertex[node];next;next=Edge[next].next){ 42         int son = Edge[next].to; 43         if ( son != parent ) dfs(son,node); 44     } 45     NewIdx[NCnt] = node; 46     InOut[NCnt] = -1; 47     OutIdx[node] = NCnt++; 48 } 49  50 int N; 51 weight_t StSum[SIZE<<3]; 52 weight_t Lazy[SIZE<<3]; 53 int Flag[SIZE<<3];//The count of the positive number in the range 54  55 inline int lson(int x){
   return x<<1;} 56 inline int rson(int x){
   return lson(x)|1;} 57  58 inline void _pushUp(int t){ 59     StSum[t] = StSum[lson(t)] + StSum[rson(t)]; 60     Flag[t] = Flag[lson(t)] + Flag[rson(t)]; 61 } 62  63 inline void _pushDown(int t){ 64     if ( 0LL == Lazy[t] ) return; 65  66     weight_t& x = Lazy[t]; 67  68     int son = lson(t); 69     StSum[son] += Flag[son] * x; 70     Lazy[son] += x; 71  72     son = rson(t); 73     StSum[son] += Flag[son] * x; 74     Lazy[son] += x; 75  76     x = 0LL; 77 } 78  79 void build(int t,int s,int e){ 80     Lazy[t] = 0LL; 81     if ( s == e ){ 82         StSum[t] = InOut[s] * W[NewIdx[s]]; 83         Flag[t] = InOut[s]; 84         return; 85     } 86  87     int m = ( s + e ) >> 1; 88     build(lson(t),s,m); 89     build(rson(t),m+1,e); 90     _pushUp(t); 91 } 92  93 void modify(int t,int s,int e,int a,int b,weight_t delta){ 94     if ( a <= s && e <= b ){ 95         StSum[t] += Flag[t] * delta; 96         Lazy[t] += delta; 97         return; 98     } 99 100     _pushDown(t);101     int m = ( s + e ) >> 1;102     if ( a <= m ) modify(lson(t),s,m,a,b,delta);103     if ( m < b ) modify(rson(t),m+1,e,a,b,delta);104     _pushUp(t);105 }106 107 weight_t query(int t,int s,int e,int a,int b){108     if ( a <= s && e <= b ){109         return StSum[t];110     }111 112     _pushDown(t);113 114     weight_t ret = 0LL;115     int m = ( s + e ) >> 1;116     if ( a <= m ) ret += query(lson(t),s,m,a,b);117     if ( m < b ) ret += query(rson(t),m+1,e,a,b);118     return ret;119 }120 121 inline weight_t query(int x){122     return query(1,1,N<<1,1,InIdx[x]);123 }124 125 inline void modify(int x,weight_t delta){126     modify(1,1,N<<1,InIdx[x],InIdx[x],delta);127     modify(1,1,N<<1,OutIdx[x],OutIdx[x],delta);128 }129 130 inline void modifySubtree(int x,weight_t delta){131     modify(1,1,N<<1,InIdx[x],OutIdx[x],delta);132 }133 134 //这里树的储存方式用的是图里面的数组仿邻接矩阵 135 inline void initTree(int n){136     ECnt = NCnt = 1;137     //vertex是顶点，这就是存储边的方式 138     fill(Vertex,Vertex+n+1,0);139 }140 141 int M;142 bool read(){143     if ( EOF == scanf("%d%d",&N,&M) ) return false;144 145     initTree(N);146     for(int i=1;i<=N;++i)scanf("%lld",W+i);//读权值 147 148     int a,b;149     for(int i=1;i
        
       
      
     

 

 

HDU 3887 

题目传送门： 

问你对于每个节点，它的子树上标号比它小的点有多少个 

子树的问题，dfs序可以很轻松的解决，因为点在它的子树上，所以在线段树中，必定在它的两个时间戳的区间之间，所以我们只需要从小到大考虑，它的区间里有多少个点已经放了，然后再把它放进去。很容易的解决了 

代码：

1 #include 

 

poj 3321 

题目传送门： 

这题是一开始告诉你树上每个节点都有1个苹果，然后你对一个节点操作，如果有苹果，就拿走，没苹果，就放上，然后询问你以x为根的子树上有多少个苹果。 

dfs序水题，代码：

1 #include 

 

 

CodeForces 620E 

题目传送门： 

给你一棵树，每个节点都有颜色，然后问你子树上有多少种不同的颜色 

考虑到颜色一共只有60种，所以可以直接二进制记录，每个节点记录这个节点的颜色，然后区间直接左右子树或起来，然后对x为根的子树都变成c颜色，区间赋值，需要pushdown，pushup。 

有个坑点就是需要记录每个时间戳是哪个点，然后在build线段树的时候，sum[rt]=c[dfsnum[l]]，这个坑点我错了好久，因为线段树的节点的下标应该是时间戳。GG，仍需努力 

代码：

1 #include