[学习笔记13] dfs序和欧拉序
Imaginative · · 算法·理论
dfs序
今天学习了dfs序，顺便来写一下学习笔记。太抽象了，我尽量尝试理解。
学习dfs序时，需要先了解什么是dfs。了解完后，可以开始了学习dfs序了。
知识点说明
定义
dfs序指的是每个节点在dfs中的进出栈的时间序列,我们一般称这个时间序列为时间戳。 设时间戳为1，每次遍历结点的时候，给他时间戳，时间戳自增，这样就可以记录他进入的时间。同理，同样可以记录出来的时间。其实tarjan就有用到时间戳。由之前学过的知识得到，这张图的遍历顺序应该为:
A B C D E F G H I J K L M
我们打上时间戳后，图片就成了： 其中节点旁边数字较小的为入时间戳，数字较大的为出时间戳。
而他的dfs序就是在他原遍历顺序上，把出去这个节点也记录一次，酱紫遍历顺序就成了:
A B C C B D E F F G G E H I I H D J K K L L J M M A
特点
通过上面的dfs序，我们可以发现其中一些特点。观察:
ABCCB\red{D}\orange{EFFGGEHIIH}\red{D}JKKLLJMMA
两个D之间所经过的
我们可以发现，如果x节点的入时间戳和出时间戳被y节点的两个时间戳完全覆盖(区间覆盖)，则x节点为y子节点，y为x的祖先节点
为什么呢？
因为时间是递增的，所以子节点未遍历完时，父节点一定不会有出时间戳。而这个特性也叫括号化定理。
代码实现时间戳
void dfs(int x,int fa){
in[x]=++timer;
update(timer,w[x]);//这个待会解释
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;//找临点
if(v!=fa) dfs(v,x);
}
out[x]=timer;//遍历完所有孩子离开了，记录出时间戳。这里不是欧拉序，所以不占用出时间戳
} 特殊用法(LCA)
其实dfs还有一种其他的用法，那就是求两个点的LCA，再放上刚刚那张图片：
任意挑选两个点出来，比如
ABCCBDEF\red{F}\orange{GGE}\red{H}IIHDJKKLLJMMA
发现深度最浅的是节点
所以我们猜测，两个点的dfs中间深度最浅的点的父亲，就是两个点的最近公共祖先。
这又是为什么捏？
设点y，z的最近公共祖先是x，那么在dfs序中，由于x的孩子没有被遍历完，一定不会遍历到x.而从y遍历到z，因为不能遍历到x，所以两个点之间进行转移的时候，一定会经过x的孩子。
思路完成了:那就是先跑一遍dfs序，然后用并查集记录每个节点的父亲，这样就能做到
以下代码是来自Alex_Wei的P3379
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e5 + 5;
int n, m, R, dn, dfn[N], mi[19][N];
vector<int> e[N];
int get(int x, int y) {return dfn[x] < dfn[y] ? x : y;}
void dfs(int id, int f) {
mi[0][dfn[id] = ++dn] = f;
for(int it : e[id]) if(it != f) dfs(it, id);
}
int lca(int u, int v) {
if(u == v) return u;
if((u = dfn[u]) > (v = dfn[v])) swap(u, v);
int d = __lg(v - u++);
return get(mi[d][u], mi[d][v - (1 << d) + 1]);
}
int main() {
scanf("%d %d %d", &n, &m, &R);
for(int i = 2, u, v; i <= n; i++) {
scanf("%d %d", &u, &v);
e[u].push_back(v), e[v].push_back(u);
}
dfs(R, 0);
for(int i = 1; i <= __lg(n); i++)
for(int j = 1; j + (1 << i) - 1 <= n; j++)
mi[i][j] = get(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
for(int i = 1, u, v; i <= m; i++) scanf("%d %d", &u, &v), printf("%d\n", lca(u, v));
return 0;
}欧拉序
在dfs序后，还有一种遍历顺利，被称为欧拉序(虽然我不知道和欧拉有什么关系)，他的遍历顺序是每经过这个点就记录一次。
比如说下面这张图
他的欧拉序就是:
当然，欧拉序也可以用来求LCA，但是似乎没有dfs序优秀(?)不过，也比st表跳LCA好理解多了，时间方面也略胜一筹。
先看预处理部分:
void dfs(int x,int fa) { //x的父亲是fa结点
f[x][0]=fa;
for(int i=1;i<=h;i++) //预处理倍增数组，这个少不了
f[x][i]=f[f[x][i-1]][i-1];
d[x]=d[fa]+1;//记录深度
//求欧拉序每个点的进出时间
in[x]=++tot;
for(int i=head[x];i;i=nxt[i]) {
int y=to[i];
if(y!=fa)
dfs(y,x);
}
out[x]=++tot;//这里是欧拉序，要自增
}
作者：洛零（不是我代码哈）
链接：https://www.acwing.com/blog/content/3414/
来源：AcWing然后是LCA找祖先部分:
int lca(int x,int y) {
//两种特殊情况
if(up(x,y))
return x;
if(up(y,x))
return y;
for(int i=h;i>=0;i--)
if(!up(f[x][i],y) and f[x][i]!=0) //如果不是祖先，又不是0号结点
x=f[x][i]; //往上跳
return f[x][0]; //最后x的父亲必定是x与y的LCA
}而up函数，就是判断区间是否完全包含,剩下的也很好办了，就不展示了
dfs序一般应用（著名的七个问题）
由于我们成功的将图论问题转化为了区间问题，所以那些优秀的区间算法便可以应用起来了。拿线段树或者树状数组还是平衡树巴拉巴拉的，无脑拍上去就可以了。
1.单点修改，查询子树和
模板题链接:#144
根据上面的知识，这道题变得就不那么难了。把图论转成树上问题，链式前向星建图，建树状数组(或线段树)，然后输出区间即可。
代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
struct edge{
int to,nxt;
}e[N*2];
int head[N],cnt;
void add(int u,int v){
e[++cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int lowbit(int x){
return x&(-x);
}
int n,w[N],r;
int c[N];
void update(int k,int x){
for(int i=k;i<=n;i+=lowbit(i)){
c[i]+=x;
}
}
int query(int k){
int ans=0;
for(int i=k;i>0;i-=lowbit(i)){
ans+=c[i];
}
return ans;
}
int in[N],out[N],timer;
void dfs(int x,int fa){
in[x]=++timer;
update(timer,w[x]);
for(int i=head[x];i;i=e[i].nxt){
int v=e[i].to;
if(v!=fa) dfs(v,x);
}
out[x]=timer;
}
int q;
signed main(){
cin>>n>>q>>r;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
add(u,v);add(v,u);
}
dfs(r,0);
while(q--){
int opt,x,y;
cin>>opt>>x;
if(opt==1){
cin>>y;
update(in[x],y);
}else{
cout<<query(n)-query(in[x]-1)<<endl;
}
}
return 0;
}2.树链修改，单点查询
(再把图片搬过来)
树链是指两个节点中的简单路径，比如
树链怎么求呢，我们可以把它转化为4个子问题，举个F到H的例子
- 把F到根节点A的所有节点加x
- 把H到根节点A的所有节点加x
- LCA(F,H)=D,将两点的最近公共祖先到根节点的所有节点减x
- 将father(D)到根节点A的所有节点减x
如何理解这些，首先前面两点很好理解。这时候我们发现节点
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+10;
vector<int> edge[MAXN];
int s[2*MAXN];
int seq[2*MAXN];
int seq1[2*MAXN];
int depth[2*MAXN];
int first[MAXN];
int dp[2*MAXN][25];
int st[MAXN];
int ed[MAXN];
int parent[MAXN];
int cnt, num;
int Lowbit(int x){
return x & (-x);
}
void Add(int x, int val, int n){
if(x <= 0) return;
for(int i = x; i <= n; i += Lowbit(i)) {
s[i] += val;
}
}
int Sum(int x){
int res = 0;
for(int i = x; i > 0; i -= Lowbit(i)) {
res += s[i];
}
return res;
}
void Dfs(int u, int fa, int dep){
parent[u] = fa;
seq[++cnt] = u;
seq1[++num] = u;
first[u] = num;
depth[num] = dep;
st[u] = cnt;
int len = edge[u].size();
for(int i = 0; i < len; i++){
int v = edge[u][i];
if(v != fa) {
Dfs(v, u, dep+1);
seq1[++num] = u;
depth[num] = dep;
}
}
seq[++cnt] = u;
ed[u] = cnt;
}
void RMQ_Init(int n){
for(int i = 1; i <= n; i++) {
dp[i][0] = i;
}
for(int j = 1; (1 << j) <= n; j++) {
for(int i = 1; i + (1 << j) - 1 <= n; i++) {
int a = dp[i][j-1], b = dp[i + (1 << (j-1))][j-1];
dp[i][j] = depth[a] < depth[b] ? a : b;
}
}
}
int RMQ_Query(int l, int r){
int k = 0;
while((1 << (k + 1)) <= r - l + 1) k++;
int a = dp[l][k], b = dp[r-(1<<k)+1][k];
return depth[a] < depth[b] ? a : b;
}
int LCA(int u, int v){
int a = first[u], b = first[v];
if(a > b) a ^= b, b ^= a, a ^= b;
int res = RMQ_Query(a, b);
return seq1[res];
}
void Init(int n){
for(int i = 0; i <= n; i++) {
edge[i].clear();
}
memset(s, 0, sizeof(s));
}
int main(){
int n, op;
int u, v, w;
int cmd;
while(scanf("%d %d", &n, &op) != EOF) {
Init(n);
for(int i = 0; i < n-1; i++) {
scanf("%d %d", &u, &v);
edge[u].push_back(v);
edge[v].push_back(u);
}
cnt = 0, num = 0;
Dfs(1, -1, 0);
RMQ_Init(num);
while(op--) {
scanf("%d", &cmd);
if(cmd == 0) {
scanf("%d %d %d", &u, &v, &w);
int lca = LCA(u, v);
Add(st[u], w, cnt);
Add(st[v], w, cnt);
Add(lca, -w, cnt);
Add(parent[lca], -w, cnt);
}
else if(cmd == 1) {
scanf("%d", &u);
printf("%d\n", Sum(ed[u]) - Sum(st[u] - 1));
}
}
}
return 0;
}
非本人代码，代码是:Kousak的
https://www.cnblogs.com/kousak/p/9192094.html剩余的以后有时间再写