【题目链接】 

 

【题目大意】

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

 

【题解】

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

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

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

 

【代码】

#include 
     
      #include 
      
       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
       
         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