树的 \(DFS\) 序
简意:将树上问题转化为线性问题。
例题:
- MEG-Megalopolis
有一棵节点数为 \(n\) 的树,给定 \(m + n - 1\) 组询问,每组询问有两种操作。
-
A x y
,将 \(x\) 节点和 \(y\) 节点间的边权改为 \(0\),每条边会被修改恰好一次。(每次只修改一条边) -
W x
,求 \(1\) 号点到 \(x\) 号点路径上的边权和。
初始所有边权值都为 \(1\)。
我们可以先 \(dfs\) 一遍找出这棵树的 \(dfs\) 序,其长度为 \(2n\) :
void dfs(int pos,int fa){
l[pos] = idx;
idx++;
for(int to : tree[pos]){
if(to != fa){
dfs(to,pos);
}
}
r[pos] = idx;idx++;
}
其中 \(l\) 数组为记录某一节点在 \(dfs\) 序中第一次出现的位置,而 \(r\) 数组为记录某一节点在 \(dfs\) 序中第二次出现的位置。
而每个节点会且仅会出现两次。
我们对于节点 \(2 - n\) ,建一颗线段树或树状数组,将 \(l[x]\) 位置上的值加1,将 \(r[x]\) 的值减1,查询 \(1 - x\) 路径上的边权和时就查询 \(1 - l[x]\) 的前缀和就行了.
\(code\):
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXN = 250005;
int n,m;
vector<int> tree[MAXN];
int l[MAXN],r[MAXN];
int idx = 1;
struct TREE{
int l,r;
int val;
}seg[MAXN << 4];
void build(int pos,int l,int r){
seg[pos].l = l;
seg[pos].r = r;
if(l == r){
return;
}
int mid = (l + r) / 2;
int ls = pos * 2;
int rs = pos * 2 + 1;
build(ls,l,mid);
build(rs,mid + 1,r);
}
void fix(int pos,int x,int val){
int l = seg[pos].l;
int r = seg[pos].r;
if(l == r && l == x){
seg[pos].val += val;
return;
}
int mid = (l + r) / 2;
int ls = pos * 2;
int rs = pos * 2 + 1;
if(mid >= x) fix(ls,x,val);
if(mid < x) fix(rs,x,val);
seg[pos].val = seg[ls].val + seg[rs].val;
}
int query(int pos,int nl,int nr){
int l = seg[pos].l;
int r = seg[pos].r;
if(l >= nl && r <= nr){
return seg[pos].val;
}
int ans = 0;
int mid = (l + r) / 2;
int ls = pos * 2;
int rs = pos * 2 + 1;
if(mid >= nl) ans += query(ls,nl,nr);
if(mid < nr) ans += query(rs,nl,nr);
return ans;
}
void dfs(int pos,int fa){
l[pos] = idx;
idx++;
for(int to : tree[pos]){
if(to != fa){
dfs(to,pos);
}
}
r[pos] = idx;idx++;
}
int main(){
scanf("%d", &n);
build(1,1,3 * n);
for(int i = 1;i < n;i++){
int x,y;
scanf("%d%d", &x, &y);
tree[x].push_back(y);
tree[y].push_back(x);
}
dfs(1,0);
for(int i = 2;i <= n;i++){
fix(1,l[i],1);
fix(1,r[i],-1);
}
scanf("%d", &m);
for(int i = 1;i <= m + n - 1;i++){
char op;
cin>>op;
int x,y;
if(op == 'A'){
scanf("%d%d", &x, &y);
if(l[x] < l[y]){
swap(x,y);
}
fix(1,l[x],-1);
fix(1,r[x],1);
}else{
scanf("%d", &x);
printf("%d\n",query(1,1,l[x]));
}
}
return 0;
}
标签:val,idx,int,pos,dfs,seg,DFS
From: https://www.cnblogs.com/wyl123ly/p/18406934