看起来是 dfs 序，其实是数据结构。
什么是 dfs 序？就是从根节点出发的 dfs 访问顺序。dfs 序主要用于树。
先给出一棵树：
4
1 2
1 3
2 4
2 5
然后我们从 \(1\) 号点出发求出 dfs 序：1 2 4 5 3。我们惊奇地发现对于所有子树，其子树内所有节点在 dfs 序上都是连续的。有了这个性质，对于一些求子树和之类的问题，我们就可以把树拍成一个序列，用线段树等数据结构进行维护。
给出一个经典问题：
给定一棵 \(n\) 个节点的树，根节点为 \(1\)，每个点有点权 \(c \in \{0,1\}\)，有 \(m\) 次操作，操作 \(1\) 为子树，操作 \(2\) 为子树异或。\(n,m \le 2 \times 10^5\)。
太经典了，把树转换成 dfs 序后线段树维护即可。
代码：
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,m,i,j,ans,opt,x,a[N],d[N<<2],tag[N<<2];
//lf[i]表示以i为根的子树在dfs序上的左端点编号，rf[i]表示右端点编号
int cnt,lf[N],rf[N],id[N];
vector<int>G[N];
void dfs(int a,int lst){
lf[a]=++cnt,id[cnt]=a;
for(int y:G[a]) if(y!=lst) dfs(y,a);
rf[a]=cnt;
}
void pd(int l,int r,int mid,int poi){
if(tag[poi]==0) return;
d[poi<<1]=(mid-l+1)-d[poi<<1];
d[poi<<1|1]=(r-mid)-d[poi<<1|1];
tag[poi<<1]^=1,tag[poi<<1|1]^=1,tag[poi]=0;
return;
}
void build(int l,int r,int poi){
if(l==r){
d[poi]=a[id[l]];
return;
}
int mid=(l+r)>>1;
build(l,mid,poi<<1);
build(mid+1,r,poi<<1|1);
d[poi]=d[poi<<1]+d[poi<<1|1];
}
void upd(int l,int r,int poi,int s,int t){
if(l>=s && r<=t){
d[poi]=(r-l+1)-d[poi],tag[poi]^=1;
return;
}
int mid=(l+r)>>1;
pd(l,r,mid,poi);
if(mid>=s) upd(l,mid,poi<<1,s,t);
if(mid<t) upd(mid+1,r,poi<<1|1,s,t);
d[poi]=d[poi<<1]+d[poi<<1|1];
}
int qry(int l,int r,int poi,int s,int t){
if(l>=s && r<=t) return d[poi];
int mid=(l+r)>>1,sum=0;
pd(l,r,mid,poi);
if(mid>=s) sum+=qry(l,mid,poi<<1,s,t);
if(mid<t) sum+=qry(mid+1,r,poi<<1|1,s,t);
return sum;
}
int main(){
scanf("%d",&n);
for(i=1;i<n;i++){
scanf("%d",&x);
G[i+1].push_back(x),G[x].push_back(i+1);
}
for(i=1;i<=n;i++) scanf("%d",&a[i]);
dfs(1,0);
build(1,n,1);
scanf("%d",&m);
for(i=1;i<=m;i++){
scanf("%d%d",&opt,&x);
if(opt==1) printf("%d\n",qry(1,n,1,lf[x],rf[x]));
if(opt==2) upd(1,n,1,lf[x],rf[x]);
}
return 0;
}