BZOJ 1103 [POI2007]大都市meg(树状数组+dfs序)

时间:2021-09-16 15:13:51

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1103

【题目大意】

  给出一棵树,每条边的经过代价为1,现在告诉你有些路不需要代价了, 以A x y形式给出,表示x到y的路不再需要代价,同时还有查询操作W x, 查询1到x的路径需要多少代价。

【题解】

  我们对树做一遍dfs,保存得到的dfs序,我们发现如果对dfs序列进行操作,

  对同一个点在进入位置设置1,出点位置设置-1, 那么查询1到x的代价就是dfs序到x入点位置的前缀和。 而对于取消代价的操作只要在出点位置+1,进入位置-1即可。

  单点修改,前缀查询可以用树状数组维护。

【代码】

#include <cstdio>
#include <vector>
using namespace std;
const int N=500005;
int x,y,T,n,m,top,c[N],st[N],f[N],l[N],r[N];
vector<int> v[N];
char op[10];
void update(int x,int val){while(x<=n+n)c[x]+=val,x+=x&-x;}
int query(int x){int res=-1;while(x)res+=c[x],x-=x&-x;return res;}
void dfs(){
st[++top]=1;
while(top){
int x=st[top],fx=f[top--];
if(!l[x]){
l[x]=++T;
st[++top]=x;
for(int i=0;i<v[x].size();i++){
if(v[x][i]==fx)continue;
st[++top]=v[x][i];
f[top]=x;
}
}else r[x]=++T;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}dfs();
for(int i=1;i<=n;i++){update(l[i],1);update(r[i],-1);}
scanf("%d",&m);
for(int i=1;i<n+m;i++){
scanf("%s",op);
if(op[0]=='A'){
scanf("%d%d",&x,&y);
update(l[y],-1);update(r[y],1);
}else{
scanf("%d",&x);
printf("%d\n",query(l[x]));
}
}return 0;
}