[BZOJ]1103: [POI2007]大都市meg

Description

在经济全球化浪潮的影响下,习惯于漫步在清晨的乡间小路的邮递员Blue Mary也开始骑着摩托车传递邮件了。不过，她经常回忆起以前在乡间漫步的情景。昔日，乡下有依次编号为1..n的n个小村庄，某些村庄之间有一些双向的土路。从每个村庄都恰好有一条路径到达村庄1（即比特堡）。并且，对于每个村庄，它到比特堡的路径恰好只经过编号比它的编号小的村庄。另外，对于所有道路而言，它们都不在除村庄以外的其他地点相遇。在这个未开化的地方，从来没有过高架桥和地下铁道。随着时间的推移，越来越多的土路被改造成了公路。至今，Blue Mary还清晰地记得最后一条土路被改造为公路的情景。现在，这里已经没有土路了――所有的路都成为了公路，而昔日的村庄已经变成了一个大都市。 Blue Mary想起了在改造期间她送信的经历。她从比特堡出发，需要去某个村庄，并且在两次送信经历的间隔期间,有某些土路被改造成了公路.现在Blue Mary需要你的帮助：计算出每次送信她需要走过的土路数目。（对于公路，她可以骑摩托车；而对于土路，她就只好推车了。）

Input

第一行是一个数n(1 < = n < = 2 50000).
以下n-1行，每行两个整数a，b（1 < = a以下一行包含一个整数m（1 < = m < = 2 50000），表示Blue Mary曾经在改造期间送过m次信。
以下n+m-1行，每行有两种格式的若干信息，表示按时间先后发生过的n+m-1次事件:
若这行为 A a b(a若这行为 W a, 则表示Blue Mary曾经从比特堡送信到村庄a。

Output

有m行，每行包含一个整数，表示对应的某次送信时经过的土路数目。

Sample Input

Sample Output

HINT

这是我做的第二道有关DFS序，BFS序的题了。这种题说难不难，说简单不简单，重在对于看出问题的本质，分析出究竟改变了什么，怎么改变了，改变量有什么特点。

这题抽象一下，最先每个点的值存的是到1的距离，也就是深度，然后给出m个操作，操作有两种：1.询问一个点的值；2.将一个点及他的子树的值全部减1。

我们发现，我们每次操作，是想尽量快的更改他和他的子树，那么自然他和他的子树放在一起更好改，于是可以想到DFS序，对于一棵树的DFS序，一个节点的儿子一定是在一个区间内的，那么只要我们记下这个区间在哪儿，每次就可以想怎么搞怎么搞了。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; #define MAX_N 300000 int n,m; int tot; int fir[MAX_N*2],en[MAX_N*2],nex[MAX_N*2]; void ins(int a,int b){ nex[++tot]=fir[a]; fir[a]=tot; en[tot]=b; nex[++tot]=fir[b]; fir[b]=tot; en[tot]=a; } int top,sta[MAX_N*2]; int L[MAX_N],R[MAX_N],bel[MAX_N],dep[MAX_N]; void dfs(int now,int deep){ sta[++top]=now; bel[now]=top; dep[now]=deep; L[now]=top+1; for (int k=fir[now];k;k=nex[k]) if (!bel[en[k]]) dfs(en[k],deep+1); R[now]=top; if (R[now]
       
        y) swap(x,y); modify(1,1,n,bel[y],bel[y]); if (!(L[y]==0||R[y]==0))modify(1,1,n,L[y],R[y]); } } return 0; }