生命不息，學習不止，昨天學了兩個算法，總結一下，然而隻是略懂，請路過的大佬多多諒解。
一、dfs序
1、什麼是dfs序？
其實完全可以從字面意義上了解，dfs序就是指一棵樹被dfs時所經過的節點的順序
原圖來源于網絡，并經過靈魂畫師xhk的一發魔改。
好的，這張圖的dfs序顯然為A-B-D-E-G-C-F-H
2、dfs序怎麼寫？
首先你得會寫dfs（不會的請先自行學習）
然後我們都知道正常的dfs一般是長這樣的（以及部落客是隻蒟蒻）
我們隻需要多一個輔助數組來記錄dfs序就行了
代碼：
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> g[100010];
int dfs_[200020],len;
void dfs(int u,int fa)
{
dfs_[++len]=u;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
if(g[u][i]!=fa)
{
dfs(g[u][i],u);
}
}
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs(1,0);
for(int i=1;i<=len;i++)
{
printf("%d ",dfs_[i]);
}
printf("\n");
} 好的，都應該可以了解了吧。
于是問題來了，我們要dfs序有什麼用呢？
3、dfs序的用處
這得從dfs的優勢來探讨了。
dfs是深度優先的，是以對于一個點，它會先周遊完它的所有子節點，再去周遊他的兄弟節點以及其他
是以對于一棵樹的dfs序來說，這個點和他所有的子節點會被存儲在連續的區間之中。
仍然是這張圖：
我們都知道它的dfs序是：A-B-D-E-G-C-F-H
然後我們可以發現B字樹B-D-E-G，C子樹C-F-H都在一段連續的區間中。
那麼這有什麼好處呢？
比如說現在有一道題：給你一顆樹，給出m個x和w，意為将x子樹中的所有點加上一個權值w，最後詢問所有點的權值
既然dfs序中x和他的所有子節點都在連續的區間上，那麼我們就可以将它簡化成差分的問題。
比如說給b節點加2，就可以簡化為給b的差分數組+2，c的差分數組-2
也就是說我們隻需要找到第一個不包括在B的子樹的位置減掉2，到時候還原回字首和就可以求解了。
是不是很簡單？
那麼問題來了，我們怎麼找第一個不在B子樹中的點？
這裡，需要引進一個新的東西
4、時間戳
時間戳也很好了解，它就好比一個标簽，貼在每一個點上，記錄dfs第一次開始通路這個點的時間以及最後結束通路的時間。
是以它還是和dfs結合的
不過需要注意，dfs序和1-n是不一樣的
是以可千萬不要像部落客一樣傻傻地用s[i]來表示點i的起始時間！
那麼怎麼儲存呢？反正部落客比較愚昧，隻想到用另一個數組來記錄一下（這就是部落客自帶大常數和大空間的原因）
于是變成了這樣
好的，那麼知道了起始時間和終結時間以後我們該怎麼用呢？
因為搜尋進下一個點時時間增加，且結束時間逐級傳遞。
是以說我們的點的子節點的時間區間一定包含在這個點的時間區間内。
是以如果一個點的起始時間和終結時間被另一個點包括，這個點肯定是另一個點的子節點。（算導裡稱之為括号化定理）
是以可以判斷一個點是否是另一個點的子節點。
代碼：
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> g[100010];
int dfs_[200020],len,time,s[200020],e[200020],pos[200020];
void dfs(int u,int fa)
{
int x=len+1;
s[++len]=++time;
dfs_[len]=u;
pos[u]=len;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
if(g[u][i]!=fa)
{
dfs(g[u][i],u);
}
}
e[x]=time;
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs(1,0);
for(int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
x=pos[x];
y=pos[y];
if(s[x]<=s[y]&&e[y]<=e[x])
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
} 至于如何讓找出第一個？
還是上面那張圖，設如果是B的子節點就為1，否則0
嗯，這玩意好像可以二分呢！
于是乎就做好了！log（n）的修改，似乎還挺可做的！
好吧假裝代碼是這樣的：
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> g[100010];
int dfs_[200020],len,time,s[200020],e[200020],pos[200020],a[200020],b[200020],sub[200020];
void dfs(int u,int fa)
{
int x=len+1;
s[++len]=++time;
dfs_[len]=u;
b[len]=a[u];
pos[u]=len;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
if(g[u][i]!=fa)
{
dfs(g[u][i],u);
}
}
e[x]=time;
}
int main()
{
int n,m,t;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n-1;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs(1,0);
sub[1]=b[1];
for(int i=2;i<=len;i++)
{
sub[i]=b[i]-b[i-1];
}
for(int i=1;i<=m;i++)
{
int x,w;
scanf("%d%d",&x,&w);
x=pos[x];
sub[x]+=w;
int l=x,r=a[len];
while(l<r)
{
int mid=(l+r)>>1;
if(s[x]<=s[mid]&&e[mid]<=e[x])
{
l=mid+1;
}
else
{
r=mid;
}
}
int y=r;
sub[y]-=w;
}
for(int i=1;i<=n;i++)
{
sub[i]=sub[i-1]+sub[i];
}
for(int i=1;i<=n;i++)
{
int x=pos[i];
printf("%d ",sub[x]);
}
} 然後還能再優化嗎?當然可以,我們隻需要記錄一下每個點的dfs結束的位置,這樣子就不用二分了,怎麼寫?自己想想吧先╮(￣▽￣)╭,如果你能堅持看完歐拉序,也許你能找到差不多的代碼哦~
二、歐拉序
1、什麼是歐拉序
就是從根結點出發，按dfs的順序在繞回原點所經過所有點的順序
2、歐拉序有怎麼寫？
（1）dfs到加進，dfs回加進，總共加入度遍。
歐拉序1為A-B-D-B-E-G-E-B-A-C-F-H-F-C-A
同時需要一個輔助數組
代碼1：
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> g[40010];
int len,a[80020];
void dfs(int u,int fa)
{
a[++len]=u;
int sz=g[u].size();
for(int i=0; i<sz; i++)
{
if(g[u][i]!=fa)
{
dfs(g[u][i],u);
a[++len]=u;
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
len=0;
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
g[i].clear();
}
for(int i=1; i<=n-1; i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs(1,0);
for(int i=1;i<=len;i++)
{
printf("%d ",a[i]);
}
}
} （2）dfs進加進，dfs最後一次回加進，總共加兩遍
歐拉序2為A-B-D-D-E-G-G-E-B-C-F-H-H-F-C-A
代碼2：
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> g[40010];
int len,a[80020];
void dfs(int u,int fa)
{
a[++len]=u;
int sz=g[u].size();
for(int i=0; i<sz; i++)
{
if(g[u][i]!=fa)
dfs(g[u][i],u);
}
}
a[++len]=u;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
len=0;
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
g[i].clear();
}
for(int i=1; i<=n-1; i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs(1,0);
for(int i=1;i<=len;i++)
{
printf("%d ",a[i]);
}
}
} 當然還有幾種寫法，各有長處，不在介紹了就。
好的，那麼我們來講下這幾種歐拉序的用處
三、歐拉序的用處
1、求LCA
假設我們使用歐拉序1
則我們要求的兩個點在歐拉序中的第一個位置之間肯定包含他們的lca,因為歐拉序1上任意兩點之間肯定包含從第一個點走到第二個點通路的路徑上的所有點
是以隻需要記錄他們的深度，然後從兩個詢問子節點x,y第一次出現的位置之間的深度最小值即可,可能不大好了解,看張圖吧。
代碼:
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int > g[40010];
int len,a[80020],dep[80020],pos[80020][17],dp[80020][17],vis[80020],cnt[80020];
void dfs(int u,int fa,int deep)
{
a[++len]=u;
dep[len]=deep+1;
if(!vis[u])
{
cnt[u]=len;
vis[u]=1;
}
int sz=g[u].size();
for(int i=0; i<sz; i++)
{
if(g[u][i]!=fa)
{
dfs(g[u][i],u,deep+1);
a[++len]=u;
dep[len]=deep+1;
}
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n,m;
len=0;
memset(a,0,sizeof(a));
memset(dep,0,sizeof(dep));
memset(pos,0,sizeof(pos));
memset(dp,0,sizeof(dp));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++)
{
g[i].clear();
}
for(int i=1; i<=n-1; i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs(1,0,0);
printf("%d\n",len);
for(int i=1; i<=len; i++)
{
dp[i][0]=dep[i];
pos[i][0]=i;
}
for(int j=1; j<=17; j++)
{
for(int i=1; i<=len; i++)
{
if(i+(1<<(j-1))>=len)
{
break;
}
if(dp[i][j-1]>dp[i+(1<<(j-1))][j-1])
{
dp[i][j]=dp[i+(1<<(j-1))][j-1];
pos[i][j]=pos[i+(1<<(j-1))][j-1];
}
else
{
dp[i][j]=dp[i][j-1];
pos[i][j]=pos[i][j-1];
}
}
}
for(int i=1; i<=m; i++)
{
int x,y;
scanf("%d%d",&x,&y);
int dx=cnt[x];
int dy=cnt[y];
if(dx>dy)
{
swap(dx,dy);
swap(x,y);
}
int k=(int)(log((double)(dy-dx+1))/log(2.0));
int p;
if(dp[dx][k]>dp[dy-(1<<k)+1][k])
{
p=pos[dy-(1<<k)+1][k];
}
else
{
p=pos[dx][k];
}
printf("%d\n",a[p]);
}
}
} 例題:HDU 2586
2、求子樹的權值之和
先來道滑稽題:(由于純屬手糊,如有錯誤,還請諒解)
給你一棵樹,告訴你每個點的點權,給你m個x和w,表示将子樹x中每個點的權值和加w,然後再給你t個x,表示詢問x子樹中所有點的權值之和.
樣例輸入:
7 2 7
6 5 4 2 1 8 7
1 2
2 3
2 4
4 5
1 6
6 7
5 1
3 2
1
2
3
4
5
6
7
樣例輸出:
36 15 6 4 2 15 7
這道題和dfs序中那道很像不是嗎?
好,我們來看歐拉序2,它有什麼優點呢?你可以發現,每個點都出現了兩遍,而這個點第一次出現和第二次出現的位置之間就是他的所有子孫節點.
ちょっと まで!
有沒有發現這就是之前記錄結束位置的想法?
隻不過這個更具體更好懂呢!
然後同樣是差分,隻不過差分時我們可以直接通過該點第二次出現的位置+1來獲得第一個不是該子樹的點,然後,o(1)的修改就實作了.
但是如果這樣怎麼查詢權值和呢?
我們都知道這個點第一次出現的位置和第二次出現的位置之間是他的子樹,那麼我們隻需要維護一遍字首和,用第二個的位置減第一個的位置前的那個位置,就可以得到權值和了.
不過由于每個子樹中的點都被算了兩遍,我們要除以二.
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
vector<int> g[100010];
int euler[200020],pos[100010][2],len,a[100010],sub[200020];
void dfs(int u,int fa)
{
euler[++len]=u;
pos[u][0]=len;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
if(g[u][i]!=fa)
{
dfs(g[u][i],u);
}
}
euler[++len]=u;
pos[u][1]=len;
}
int main()
{
int n,m,t;
len=0;
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=n-1;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
dfs(1,0);
sub[1]=a[euler[1]];
for(int i=2;i<=len;i++)
{
sub[i]=a[euler[i]]-a[euler[i-1]];
}
for(int i=1;i<=m;i++)
{
int x,w;
scanf("%d %d",&x,&w);
sub[pos[x][0]]+=w;
sub[pos[x][1]+1]-=w;
}
for(int i=1;i<=len;i++)
{
sub[i]=sub[i-1]+sub[i];
}
for(int i=1;i<=len;i++) //如果删去維護字首和的過程,就是查詢單個點的權值
{
sub[i]=sub[i-1]+sub[i];
}
for(int i=1;i<=t;i++)
{
int x;
scanf("%d",&x);
printf("%d\n",(sub[pos[x][1]]-sub[pos[x][0]-1])/2);
}
} 沉迷學習,無法自拔......