DFS序學習

對于一棵樹，将他DFS展開成一個數組，就是DFS序，它的作用有很多，下面再說；

先放代碼：

dfs序闆子：
void dfs(int x,int pre,int d)//L,R表示一個子樹的範圍 
{	//目前節點，父節點，深度 
	L[x]=++tot;//目前節點的左時間 
	dep[x]=d;//記錄深度 
	for(int i=0;i<e[x].size;++i)//周遊子節點 
	{
		int y=e[x][i];// 子節點 
		if(y==pre)// 防止回溯
			continue;
		dfs(y,x,d+1);//繼續dfs，深度++； 
	}
	R[x]=tot;//該子樹結束周遊 
}
           

它是将一棵樹，按照DFS周遊順序将他展開成一個數組，展開後的數組中，每個下标對應的元素就是節點元素；

每個節點元素有兩個屬性，L和R，表示的是從L開始進入x節點，直到最後R是該x的子樹周遊完成，是以對應線段樹的修改x的子樹的時候，直接修改L(x)~R(x)的區間範圍即可；

好了，開始介紹DFS序：

dfs序:就是從一棵樹的根節點出發，dfs周遊時依次經過的節點序列 ;

dfs序可以有很多種

dfs周遊，經曆目前節點的所有子節點，後回溯到目前節點，

周遊之前，任何子節點都沒有被通路過 

周遊後，所有子節點必定都被通路過了， 

然後離開目前子樹，回到父節點，在通路其他子樹，同一子樹的節點在bfs序中一定是連續的；

實作：

設定一個時間time=0，每周遊到一個新的節點就+1，目前節點的通路時間範圍即目前節點的通路标号範圍 

設in[x]為進入節點的時間，out[x]為離開目前節點的時間，子樹在dfs序中對應的範圍就是in[x]~out[x];

他的DFS序就是0 1 2 3 4 5（不唯一，也可以是：0 3 4 5 1 2什麼的，對結果一般無影響）

看一些大佬的部落格對DFS序的一些變形和應用，總結出7點，便于以後實作

常用搭配:dfs序+線段樹 ; 

dfs序問題：

1.對于某個節點 x 權值加上一個數 W ，查詢某個子樹 x 裡所有點權的和；

2.對節點 x 到 y 的最短路上所有點都加上一個數 W 查詢某個點的權值；

    等價于：

    x到根節點路徑上所有點權加W；

    y到根節點路徑上所有點權加W； 

    對LCA(x,y)到根節點路徑上所有點權值減W；

    對LCA(x,y)的父節點 fa(LCA(x,y))到根節點路徑上所有權值減W；  

3. 對節點 x 到 y 的最短路上所有點權都加一個數W，查詢某個點子樹的權值之和 

    修改節點A，查詢節點B時；

    隻要A在B子樹内，Y值就會增加：W*(dep[A]-dep[B]+1)

    =>W*(dep[A]+1)-W*dep[B];

    處理兩個數組：

    sum1 更新 W*(dep[A]+1), sum2 更新 W;

    每次查詢結果為sum1(R[B])-sum1(L[B]-1)-(sum2(R[B])-sum2(L[B]-1))*dep[B]; 

4.對某個點 X 權值加上一個數 W ，查詢 X 到 Y 路徑上所有點權之和.

    問題轉化：

    x 到根節點的和 + y 到根節點的和 - lca(x,y)到根節點的和 - fa(lca(x,y))到根節點的和; 

    更新x權值時，隻會對他的子樹産生影響，對 x 的子樹的每個節點到跟的距離都加了 W ; 

    用"刷漆"(差分字首和),更新一個子樹的權值，

    給L[x]加上W，給R[x]+1減去W，那麼sum(1~L[k])就是k到根節點的路徑點權和； 

5.對節點 x 的子樹所有節點加上一個值 W ，查詢 x 到 y 的路徑上所有點的權值和

    同(4):

        x 到根節點的和 + y 到根節點的和 - lca(x,y)到根節點的和 - fa(lca(x,y))到根節點的和; 

    同(3): B在A的子樹内，A對B有貢獻；W*(dep[B]-dep[A]+1)

    =>W*(1-dep[A])+W*dep[B];

    兩個數組sum1 記錄W*(dep[A]+1), sum2 記錄 W ;

    答案就是 sum2*dep[B]-sum1 ;

6.對子樹x中所有節點加上一個值W，查詢某個點的值； 

    對DFS序來說，子樹内所有節點加 W ，就是一段區間加 W；

    區間修改，單點查詢:方法有 (a): 樹狀數組+刷漆 ,(b): 線段樹 

7.對子樹 x 裡的所有節點加上一個值 W ,查詢某個子樹的權值的和：

    子樹所有節點加 W ，就是區間加 W ，查詢某個子樹的權值和，就是查詢某段區間的和；

    區間修改+區間求和，線段樹