DFS序

重要性质：

1.一个结点子树上的时间戳，一定大于这个节点的时间戳且连续 2.某些链上的时间戳也是连续的

应用：

把树强行搞成“连续的”，这样我们就可以套一个线段树，实现以下操作 1：把以x为节点的子树的所有节点都加上z（区间修改） 2：求以x为节点的子树的所有节点的和（区间求和） 预处理：生成线段树产生可依靠的数组xds[n];并且找出每一个节点的子树包含的子树（包含这个节点）。

int k=0,xds[n],sum[n]; int DFS(int n,int fa) { xds[++k]=n; if(head[n]==0)return 1; int su=0; for(int i=head[n];i;i=edge[i].next) { int v=edge[i].to; if(v==fa)continue; int temp=DFS(v,u); su+=temp; } sum[n]=su+1; return sum[n]; }

检验程序

#include<bits/stdc++.h> using namespace std; #define mod 1e9+7 #define N 100005 #define inf 0x3f3f3f3f const double PI = atan(1.0)*4.0; typedef long long ll; struct edge { int next,to; }E[N]; int head[N]; int num,n; void chushi() { for(int i=1;i<=n;i++) head[i]=-1; } void add(int u,int v) { E[num].next=head[u]; E[num].to=v; head[u]=num++; } int k,xds[N],sum[N]; int DFS(int x,int fa) { xds[++k]=x; if(head[x]==0)return 1; int su=0; for(int i=head[x];~i;i=E[i].next) { int v=E[i].to; if(v==fa)continue; int temp=DFS(v,x); su+=temp; } sum[x]=su+1; return sum[x]; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen("E:\\in.txt","r",stdin); cin>>n; chushi(); int x,y; for(int i=1;i<=n;i++) { cin>>x>>y; add(x,y); } DFS(1,0); for(int i=1;i<=n;i++) cout<<xds[i]<<" "; cout<<endl; for(int i=1;i<=n;i++) cout<<sum[i]<<" "; }

但是dfs序无法处理以下问题

1：从x结点到y结点最短路径上所有的节点的值都加上z 2：求x结点到y结点最短路径的所有节点的和 这时候我们就需要树链剖分