dfs序和欧拉序

study from:

https://www.cnblogs.com/stxy-ferryman/p/7741970.html

如果侵权，请提醒我。

1.dfs序

l/r：该点作为根节点的子树中，节点的最小编号/最大编号(初进入，最后离开的当前编号)。其中初进入的编号，可认为是该节点的编号。

l~r：记录了该点作为根节点的子树的所有节点

可以判断一个点是否在另外一个点作为根节点的子树上

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <time.h>
 6 #include <string>
 7 #include <set>
 8 #include <map>
 9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <ext/rope>
15 #include <algorithm>
16 #include <iostream>
17 using namespace std;
18 #define ll long long
19 #define minv 1e-6
20 #define inf 1e9
21 #define pi 3.1415926536
22 #define E  2.7182818284
23 const ll mod=1e9+7;//998244353
24 const int maxn=1e5+10;
25 
26 int l[maxn]={0},r[maxn]={0},ti=0,tl[maxn],tr[maxn];
27 
28 void dfs(int d)
29 {
30     ti++;
31     tl[d]=ti;
32     if (l[d]!=0)
33         dfs(l[d]);
34     if (r[d]!=0)
35         dfs(r[d]);
36     tr[d]=ti;
37 }
38 
39 int main()
40 {
41     int n,root,x,y,z,i;
42     scanf("%d%d",&n,&root);
43     for (i=1;i<n;i++)
44     {
45         scanf("%d%d%d",&x,&y,&z);
46         if (z==0)
47             l[x]=y;
48         else
49             r[x]=y;
50     }
51     dfs(root);
52     for (i=1;i<=n;i++)
53         printf("%d %d
",tl[i],tr[i]);
54     return 0;
55 }
56 /*
57 8 1
58 1 2 0
59 1 3 1
60 2 4 0
61 2 5 1
62 3 6 1
63 5 7 0
64 6 8 0
65 */

例题：

http://acm.hdu.edu.cn/showproblem.php?pid=3887

对于每个节点，它的子树上标号比它小的点有多少个(by 其它博客)

求子树权值和+树状数组

  1 //用node而不释放内存会出现MLE；也许这里使用vector方便一点
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <cstring>
  6 #include <time.h>
  7 #include <string>
  8 #include <set>
  9 #include <map>
 10 #include <list>
 11 #include <stack>
 12 #include <queue>
 13 #include <vector>
 14 #include <bitset>
 15 #include <ext/rope>
 16 #include <algorithm>
 17 #include <iostream>
 18 using namespace std;
 19 #define ll long long
 20 #define minv 1e-6
 21 #define inf 1e9
 22 #define pi 3.1415926536
 23 #define E  2.7182818284
 24 const ll mod=1e9+7;//998244353
 25 const int maxn=1e5+10;
 26 
 27 struct node
 28 {
 29     int d;
 30     node *next;
 31 }*e[maxn];
 32 
 33 int f[maxn],v[maxn]={0},n;
 34 bool vis[maxn];
 35 
 36 void dfs(int d)
 37 {
 38     int j;
 39     node* p=e[d];
 40     vis[d]=1;
 41 
 42     j=d-1;
 43     while (j>0)
 44     {
 45         v[d]-=f[j];
 46         j-=(j & (-j));
 47     }
 48 
 49     while (p)
 50     {
 51         if (!vis[p->d])
 52             dfs(p->d);
 53         p=p->next;
 54     }
 55 
 56     j=d-1;
 57     while (j>0)
 58     {
 59         v[d]+=f[j];
 60         j-=(j & (-j));
 61     }
 62 
 63     j=d;
 64     while (j<=n)
 65     {
 66         f[j]++;
 67         j+=(j & (-j));
 68     }
 69 }
 70 
 71 int main()
 72 {
 73     node *p,*pp;
 74     int i,x,y,root;
 75     while (1)
 76     {
 77         memset(v,0,sizeof(v));
 78         memset(f,0,sizeof(f));
 79         memset(vis,0,sizeof(vis));
 80         scanf("%d%d",&n,&root);
 81         for (i=1;i<=n;i++)
 82             e[i]=NULL;
 83         if (n==0)
 84             break;
 85         for (i=1;i<n;i++)
 86         {
 87             scanf("%d%d",&x,&y);
 88             p=(node*) malloc (sizeof(node));
 89             p->d=y;
 90             p->next=e[x];
 91             e[x]=p;
 92 
 93             p=(node*) malloc (sizeof(node));
 94             p->d=x;
 95             p->next=e[y];
 96             e[y]=p;
 97         }
 98         dfs(root);
 99         for (i=1;i<=n;i++)
100         {
101             printf("%d",v[i]);
102             if (i!=n)
103                 printf(" ");
104             else
105                 printf("
");
106         }
107         for (i=1;i<=n;i++)
108         {
109             p=e[i];
110             while (p)
111             {
112                 pp=p;
113                 p=p->next;
114                 free(pp);
115             }
116         }
117     }
118     return 0;
119 }

2.欧拉序

遍历的编号。回溯时的点也要记录在内。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cmath>
 4 #include <cstring>
 5 #include <time.h>
 6 #include <string>
 7 #include <set>
 8 #include <map>
 9 #include <list>
10 #include <stack>
11 #include <queue>
12 #include <vector>
13 #include <bitset>
14 #include <ext/rope>
15 #include <algorithm>
16 #include <iostream>
17 using namespace std;
18 #define ll long long
19 #define minv 1e-6
20 #define inf 1e9
21 #define pi 3.1415926536
22 #define E  2.7182818284
23 const ll mod=1e9+7;//998244353
24 const int maxn=1e5+10;
25 
26 int l[maxn]={0},r[maxn]={0},ti=0,tl[maxn],tr[maxn];
27 
28 void dfs(int d)
29 {
30     ti++;
31     printf("%d ",d);
32     if (l[d]!=0)
33     {
34         dfs(l[d]);
35         ti++;
36         printf("%d ",d);
37     }
38     if (r[d]!=0)
39     {
40         dfs(r[d]);
41         ti++;
42         printf("%d ",d);
43     }
44 }
45 
46 int main()
47 {
48     int n,root,x,y,z,i;
49     scanf("%d%d",&n,&root);
50     for (i=1;i<n;i++)
51     {
52         scanf("%d%d%d",&x,&y,&z);
53         if (z==0)
54             l[x]=y;
55         else
56             r[x]=y;
57     }
58     dfs(root);
59     return 0;
60 }
61 /*
62 8 1
63 1 2 0
64 1 3 1
65 2 4 0
66 2 5 1
67 3 6 1
68 5 7 0
69 6 8 0
70 */

例题：

lca 模板题

https://www.luogu.org/problemnew/show/P3379

给你一棵树,告诉你每个点的点权,给你m个x和w,表示将子树x中每个点的权值和加w,然后再给你t个x,表示询问x子树中所有点的权值之和.

from https://www.cnblogs.com/stxy-ferryman/p/7741970.html

！子树，一个范围[x,y]，用线段树

若最后询问，用标记