【笔记】dfs序，欧拉序，LCA的RMQ解法 DFS序 欧拉

发表于

这是我参与11月更文挑战的第23天，活动详情查看：2021最后一次更文挑战.

DFS序

DFS序的定义

将树节点按dfs过程中的访问顺序排序，称为dfs序。

性质

一个节点和它的子树在一个连续的区间中。

时间戳

在dfs过程中，设访问一个新节点需要花费1s的时间，我们可以记录下每个节点的进入时间与退出时间，称为时间戳。显然进入时间是dfs序的反函数，即dfs序中的第i个点的进入时间是i。

1
2
3
4
5
6
7
8
9
cpp复制代码int st[M], ed[M];
void dfs(int now, int fa = 0)
{
	static int cnt = 0;
	st[now] = ++cnt;
	for(int i = fst[now]; i; i = nxt[i])
		if(pnt[i] != fa) dfs(pnt[i],now);
	ed[now] = cnt;
}

应用

1.判断节点的从属关系

如果st[x]<st[y]并且ed[x]>=ed[y]，那么x是y的祖先。

2.POJ 3321 Apple Tree

一棵树，操作一改变一个点的权值，操作二求以某个点为根的子树的权值和。

如果求出了这棵树的dfs序，就可以将问题从树转化为数字序列上的问题。
操作1：单点修改
操作2：区间求和，范围是st[x],ed[x]
使用树状数组维护即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
cpp复制代码#include <cstdio>
const int M = 100016;
int n;
/*链式前向星-开始*/
int fst[M*2], pnt[M*2], nxt[M*2];
void add(int x, int y)
{
	static int tot = 0;
	pnt[++tot] = y;
	nxt[tot] = fst[x];
	fst[x] = tot;
}
/*链式前向星-结束*/

/*dfs序-开始*/
int st[M], ed[M];
void dfs(int now, int fa = 0)
{
	static int cnt = 0;
	st[now] = ++cnt;
	for(int i = fst[now]; i; i = nxt[i])
		if(pnt[i] != fa) dfs(pnt[i],now);
	ed[now] = cnt;
}
/*dfs序-结束*/

/*树状数组-开始*/
int bit[M];
inline void modify(int p, int x)
{
	for(;p<=n;p+=p&-p) bit[p]+=x;
}
inline int sum(int p)
{
	int res = 0;
	for(;p;p-=p&-p) res += bit[p];
	return res;
}
inline int sum(int l, int r)
{
	return sum(r) - sum(l-1);
}
/*树状数组-结束*/
int main(void)
{
	scanf("%d",&n);
	for(int i=1,a,b;i<n;i++)
	{
		scanf("%d%d",&a,&b);
		add(a,b), add(b,a);
	}
	dfs(1);
	for(int i=1;i<=n;i++)
		modify(i,1);
	int q,node;
	char op[3];
	scanf("%d",&q);
	while(q--)
	{
		scanf("%s %d",op,&node);
		if(op[0]=='Q')
			printf("%d\n",sum(st[node],ed[node]) );
		else
			modify(st[node],sum(st[node],st[node])?-1:1);
	}

	return 0;
}

欧拉序

欧拉序的定义

树在dfs过程中的节点访问顺序称为欧拉序.

欧拉序有很多种，只要整体满足dfs顺序即算欧拉序，应当按实际需要选择适合的欧拉序。
欧拉序与dfs序不同地方在于，欧拉序中每个节点可以出现多次，比如进入一次退出一次，又比如每次回溯时记录一次。

1.每次访问一个节点时记录一次

应用：LCA归约为RMQ

这也是最经典的应用。

LCA（Lowest Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。
RMQ（Range Minimum/Maximum Query），即区间最值查询，是指在数列中求一段区间的最大或最小值。
ST表（Sprase Table），Tarjan发明，可以预处理复杂度O(nlogn)，查询复杂度O(1)地解决RMQ问题，不支持修改.
参见：RMQ问题与Sparse Table算法

假设现在需要求x和y的LCA，跑一遍欧拉序并记录时间戳st和ed后，st[x],st[y],ed[x],ed[y]的大小关系只有两种情况（交换后）：

  1. st[x]<st[y]<=ed[y]<=ed[x]，表示x是y的祖先。
    此时x与y的LCA就是x。
  2. st[x]<=ed[x]<st[y]<=ed[y]，表示x与y没有祖先-后裔关系。
    在ed[x]与st[y]之间的节点中深度最小的节点，就是x与y的LCA（不妨纸上画一画）

在实现时，先对欧拉序建立st表，比较规则是选择深度小的，查询只要查询min(deep[x],deep[y]),max(deep[x],deep[y])之间深度最小的节点即可。
实际上，可以不用额外统计深度，而把比较规则改为选择st[x]小的。（想一想，为什么）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
cpp复制代码int st[M], ed[M];
int euler[M*2],cnt;
void dfs(int now,int fa=0)
{
    euler[++cnt] = now;
    st[now] = cnt;
    for(auto nxt:edge[now]) if(nxt!=fa)
    {
        dfs(nxt,now);
        euler[++cnt] = now;
    }
    ed[now] = cnt;
}

SpraseTable stable;
void lca_init()
{
    dfs(root);
    stable = SpraseTable(euler,cnt,[](int a,int b){return st[a]<st[b]?a:b;});
}
int lca_query(int a, int b)
{
    int a = st[read()], b=st[read()];
    printf("%d\n",stable.query(min(a,b),max(a,b)));
}
Luogu P3379【模板】最近公共祖先（LCA）

模板题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
cpp复制代码#include <bits/stdc++.h>
using namespace std;
inline int read();
const int M = 1000016;
int n,m,s;
vector<int> edge[M];

/*欧拉序-开始*/
int st[M], ed[M],deep[M];
int euler[M*2],cnt;
void dfs(int now,int fa=0)
{
	euler[++cnt] = now;
	st[now] = cnt;
	deep[now] = deep[fa]+1;
	for(auto nxt:edge[now]) if(nxt!=fa)
	{
		dfs(nxt,now);
		euler[++cnt] = now;
	}
	ed[now] = cnt;
}
/*欧拉序-结束*/

/*ST表-开始*/
class SpraseTable
{
    static int lg[M];
    int n;
    function<int(int,int)> cmp;
    vector<vector<int>> table; //table[i][j]表示长度为2^i的以j开头的数组最值
public:
    SpraseTable(int *arr, int _n, 
        function<int(int,int)> _cmp = [](int a,int b){return a<b?a:b;}
    ) : n(_n), cmp(_cmp)
    {
        if(!lg[0]) {lg[0]=-1;for(int i=1;i<M;i++)lg[i]=lg[i/2]+1;}
        table = vector<vector<int>>(lg[n] + 1, vector<int>(n + 1));
        for(int i = 1; i <= n; i++)
            table[0][i] = arr[i];
        for(int i = 1; i <= lg[n]; i++)
            for(int j = 1; j <= n; j++)
                if(j + (1 << i) - 1 <= n)
                    table[i][j] = cmp(table[i-1][j], table[i-1][j+(1<<(i-1))]);
    }
    inline int query(int x, int y)
    {
        int t = lg[y - x + 1];
        return cmp(table[t][x], table[t][y - (1 << t) + 1]);
    }
};int SpraseTable::lg[M];

/*ST表-结束*/

int main(void)
{
	//freopen("in.txt","r",stdin);
	n=read(),m=read(),s=read();
	for(int i=1,a,b;i<n;i++)
	{
		a=read(),b=read();
		edge[a].push_back(b);
		edge[b].push_back(a);
	}
	dfs(s);
	SpraseTable stable(euler,cnt,[](int a,int b){return st[a]<st[b]?a:b;});

	while(m--)
	{
		int a = st[read()], b=st[read()];
		if(a>b) swap(a,b);
		printf("%d\n",stable.query(a,b));
	}

	return 0;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
HDU - 2586 How far away ？

给一棵带边权的无根树，若干次询问，每次询问两个节点的最短距离。

以任意一点为根建立欧拉序，同时dfs出所有节点到根节点的距离，询问a,b的答案就是dis[a]+dis[b]-2*dis[lca(a,b)]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
cpp复制代码/* LittleFall : Hello! */
#include <bits/stdc++.h>
using namespace std; typedef long long ll;
inline int read(); inline void write(int x);
const int M = 100016, MOD = 1000000007;

int n,q;
ll dis[M]; //距原点的距离
/*ChainForwardStar*/
int pnt[M], nxt[M], fst[M], pri[M], tot;
void add(int a, int b, int p)
{
	pnt[++tot] = b;
	pri[tot] = p;
	nxt[tot] = fst[a];
	fst[a] = tot;
}
/**/

/*欧拉序*/
int st[M],ed[M],euler[M],cnt;
void dfs(int now, int fa = 0)
{
	euler[++cnt] = now;
	st[now] = cnt;
	for(int e=fst[now],son=pnt[e];e;e=nxt[e],son=pnt[e]) if(son!=fa)
	{
		dis[son] = dis[now] + pri[e];
		dfs(son,now);
		euler[++cnt] = now;
	}
	ed[now] = cnt;
}
/**/
class SpraseTable
{
    static int lg[M];
    int n;
    function<int(int,int)> cmp;
    vector<vector<int>> table; //table[i][j]表示长度为2^i的以j开头的数组最值
public:
    SpraseTable(int *arr, int _n, 
        function<int(int,int)> _cmp = [](int a,int b){return a<b?a:b;}
    ) : n(_n), cmp(_cmp)
    {
        if(!lg[0]) {lg[0]=-1;for(int i=1;i<M;i++)lg[i]=lg[i/2]+1;}
        table = vector<vector<int>>(lg[n] + 1, vector<int>(n + 1));
        for(int i = 1; i <= n; i++)
            table[0][i] = arr[i];
        for(int i = 1; i <= lg[n]; i++)
            for(int j = 1; j <= n; j++)
                if(j + (1 << i) - 1 <= n)
                    table[i][j] = cmp(table[i-1][j], table[i-1][j+(1<<(i-1))]);
    }
    inline int query(int x, int y)
    {
        int t = lg[y - x + 1];
        return cmp(table[t][x], table[t][y - (1 << t) + 1]);
    }
};int SpraseTable::lg[M];

int main(void)
{
	#ifdef _LITTLEFALL_
	freopen("in.txt","r",stdin);
    #endif

	int T = read();
	while(T--)
	{
		memset(dis,0,sizeof(dis));
		memset(pnt,0,sizeof(pnt));
		memset(nxt,0,sizeof(nxt));
		memset(fst,0,sizeof(fst));
		memset(pri,0,sizeof(pri));
		memset(st,0,sizeof(st));
		memset(ed,0,sizeof(ed));
		memset(euler,0,sizeof(euler));
		tot = cnt = 0;
		n=read(), q=read();
		for(int i=1,a,b,p;i<n;i++)
		{
			a=read(),b=read(),p=read();
			add(a,b,p);
			add(b,a,p);
		}
		dfs(1);
		SpraseTable stable(euler,cnt,[](int a,int b){return st[a]<st[b]?a:b;});
		while(q--)
		{
			int a = read(), b=read();
			int lca = stable.query(min(st[a],st[b]),max(st[a],st[b]));
			printf("%I64d\n",dis[a]+dis[b]-dis[lca]-dis[lca] );
		}
	}

    return 0;
}


inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline void write(int x)
{
     if(x<0) putchar('-'),x=-x;
     if(x>9) write(x/10);
     putchar(x%10+'0');
}

终于学到这里了，可以回去补那个该死的cf1051F了QAQ

2. 欧拉序：进入记录一次，退出记录一次

dfs序与欧拉序的花式用法：DFS序详解-比特飞流
这边的方法好像和树链剖分有很大关系，以后学树剖的时候再看看。

BZOJ4034 树上操作

有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个
操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。

这道题，普通做法是树链剖分+数据结构，文艺做法是欧拉序+线段树，玄学做法是欧拉序+树状数组。
好了，因为我不会树链剖分与线段树，使用了玄学做法，参考自(blog.csdn.net/youhavepeop…).

首先求欧拉序，进入记录一次正点权，退出记录一次负点权。
三个操作转化为：

  1. 两个单点修改
  2. 区间修改，正的加，负的减
  3. 区间求和

一个正常的树状数组是做不到第二个操作的，于是用三个树状数组c0,c1,c2维护这个东西。
c0维护原始序列，当有操作1时，c0[st[x]]+=a,c0[ed[x]]−=ac0[st[x]]+=a,c0[ed[x]]-=ac0[st[x]]+=a,c0[ed[x]]−=a
c1记录区间修改，当有操作2时，c1[st[x]]+=a,c1[st[x]]−=ac1[st[x]]+=a,c1[st[x]]-=ac1[st[x]]+=a,c1[st[x]]−=a
c2记录区间修改乘以高度，当有操作2时，c2[st[x]]+=a∗deep[x],c2[ed[x]]−=a∗deep[x]c2[st[x]]+=a*deep[x],c2[ed[x]]-=a*deep[x]c2[st[x]]+=a∗deep[x],c2[ed[x]]−=a∗deep[x]

操作3：ans=sum0(st[x])+sum1(st[x])∗(deep[x]+1)−sum2(st[x])ans = sum_0(st[x])+sum_1(st[x])*(deep[x]+1)-sum_2(st[x])ans=sum0​(st[x])+sum1​(st[x])∗(deep[x]+1)−sum2​(st[x])

多个树状数组的组合，真的很玄学。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
cpp复制代码#include <bits/stdc++.h>
const int M = 1000016;
typedef long long ll;
inline int read();
int n,m;
int prior[M];
/*链式前向星*/
int fst[M],nxt[M],pnt[M];
void addEdge(int x, int y)
{
	static int tot = 0;
	pnt[++tot] = y;
	nxt[tot] = fst[x];
	fst[x] = tot;
}
/*欧拉序*/
int st[M], ed[M], deep[M], cnt;
void dfs(int now, int fa = 0)
{
	st[now] = ++cnt;
	for(int e = fst[now]; e; e = nxt[e]) if(pnt[e] != fa)
	{
		deep[pnt[e]] = deep[now] + 1;
	    dfs(pnt[e], now);
	}
	ed[now] = ++cnt;
}

/*树状数组*/
ll bit[3][M];
inline void modify(int id, int p, ll x)
{
	for(;p<=cnt;p+=p&-p) bit[id][p]+=x;
}
inline ll sum(int id, int p)
{
	ll res = 0;
	for(;p;p-=p&-p) res += bit[id][p];
	return res;
}


int main(void)
{
	//freopen("in.txt","r",stdin);
	n=read(), m=read();
	for(int i=1;i<=n;i++)
		prior[i] = read();
	for(int i=1,a,b;i<n;i++)
	{
		a = read(), b = read();
		addEdge(a,b);
		addEdge(b,a);
	}
	dfs(1);
	for(int i=1;i<=n;i++)
	{
		modify(0,st[i],prior[i]);
		modify(0,ed[i],-prior[i]);
	}
	while(m--)
	{
		ll op=read(),pos=read(),val;
		if(op==1)
		{
			val=read();
			modify(0, st[pos], val);
			modify(0, ed[pos], -val);
		}
		else if(op==2)
		{
			val=read();
			modify(1, st[pos], val);
			modify(1, ed[pos], -val);
			modify(2, st[pos], val*deep[pos]);
			modify(2, ed[pos], -val*deep[pos]);
		}
		else
		{
			ll ans = sum(0,st[pos])
			 	   + sum(1,st[pos]) * (deep[pos]+1) 
			 	   - sum(2,st[pos]);
			printf("%lld\n",ans );
		}

	}
	return 0;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%