树的 序
简意:将树上问题转化为线性问题。
例题:
- MEG-Megalopolis
有一棵节点数为 的树,给定 组询问,每组询问有两种操作。
A x y,将 节点和 节点间的边权改为 ,每条边会被修改恰好一次。(每次只修改一条边)
W x,求 号点到 号点路径上的边权和。
初始所有边权值都为 。
我们可以先 一遍找出这棵树的 序,其长度为 :
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++;
}
其中 数组为记录某一节点在 序中第一次出现的位置,而 数组为记录某一节点在 序中第二次出现的位置。
而每个节点会且仅会出现两次。
我们对于节点 ,建一颗线段树或树状数组,将 位置上的值加1,将 的值减1,查询 路径上的边权和时就查询 的前缀和就行了.
:
#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;
}