标题：套娃

作为 drd 送的生日礼物，atm 最近得到了一个俄罗斯娃娃。他对这个俄罗斯娃娃的构造很感兴趣。

俄罗斯娃娃是一层一层套起来的。假设：一个大小为 x 的俄罗斯娃娃里面可能会放任意多个大小小于 x 的俄罗斯娃娃（而市场上的套娃一般大娃里只能放一个小娃）。

drd 告诉 atm ，这个俄罗斯娃娃是由 n 个小娃娃组成的，它们的大小各不相同。 我们把这些小娃娃的大小从小到大依次记为 1 到 n 。

如果 atm 想观赏大小为 k 的小娃娃，他会先看这个小娃娃是否已经在桌子上了。 如果已经在桌子上，那么他就可以观赏了。否则他就打开桌子上某一个俄罗斯娃娃，将它套住的所有的小娃娃拿出来，摆在桌子上。

一开始桌子上只有 drd 送的大小为 n 的娃娃。注意，他只会将其中所有小娃娃拿出来，如果小娃娃里面还套着另外的小娃娃，他是不会将这些更里层的这些小娃娃拿出来的。

而且 atm 天生具有最优化的强迫症。他会最小化他所需要打开的娃娃的数目。

atm 是一个怪人。有时候他只想知道观看大小为 x 的娃娃时需要打开多少个娃娃（但并不去打开）；有时候听 drd 说某个娃娃特别漂亮，于是他会打开看。现在请你输出他每次需要打开多少个娃娃。

【输入格式】

第一行两个数 n m ，表示娃娃的数目以及 atm 想看的娃娃的数目。

接下来 n - 1 行，每行两个数 u v，表示大小为 u 的娃娃里面套着一个大小为 v 的娃娃。保证 u > v 。

接下来 m 行，每行形如：

P x ：表示 atm 一定要看到大小为 x 的娃娃；

Q x ：表示 atm 只想知道为了看大小为 x 的娃娃，他需要打开多少个娃娃，但实际上并不打开他们。

【输出格式】

输出 m 行。对应输入中P操作或Q操作需要打开（或假想打开）多少个俄罗斯娃娃。

【样例输入】

5 5

5 3

5 4

3 2

3 1

Q 1

Q 4

P 2

Q 1

Q 4

【样例输出】

2

1

2

0

0

【数据范围】

对于 30% 的数据：n, m <= 1000

对于 100% 的数据：n, m <= 100000

　　这题想到思路实现后提交一直不对，在搞到后台数据后发现数据出错了。不知道我打的程序对不对，不过思路我觉得应该就是这样，毕竟是和qducxk讨论出来的。

　　首先可以看出，数据建出来是一棵树，然后Q就是看这个节点的层数（默认根节点层数是0），然后P无非就是拆树，从x点开始往上找到最上面的节点，然后把它相连的边都拆掉，然后再向下更新子树，在更新子树这里如果每次都再跑一遍树的话，肯定会超时的，我们就想到了树上的区间修改，那就是记录下dfs序，然后拆掉这个点就是对子树的节点层数都-1，因为每条边只能被拆一次，更新又是nlogn，所以时间复杂度肯定是可以的。

1 #include
      
         2 #define L(x) (x<<1)  3 #define R(x) (x<<1|1)  4 #define M(x) ((T[x].l+T[x].r)>>1)  5 const int N=200118;  6 struct Side{  7     int v,ne;  8 }S[N];  9 struct Tree{ 10     int l,r,lazy,rank; 11 }T[N<<2]; 12 char op[3]; 13 int sn,tid,head[N],fa[N],num[N],in[N],out[N],nid[N]; 14 void init(int n) 15 { 16     sn=tid=0; 17     for(int i=0;i<=n;i++) 18         head[i]=-1; 19 } 20 void add(int u,int v) 21 { 22     S[sn].v=v; 23     S[sn].ne=head[u]; 24     head[u]=sn++; 25 } 26 void dfs(int u) 27 { 28     int v; 29     in[u]=++tid; 30     nid[tid]=u;//记录这个dfs序相应的编号  31     for(int i=head[u];~i;i=S[i].ne) 32     { 33         v=S[i].v; 34         fa[v]=u; 35         num[v]=num[u]+1; 36         dfs(v); 37     } 38     out[u]=tid; 39 } 40 void built(int id,int l,int r) 41 { 42     T[id].l=l,T[id].r=r; 43     T[id].lazy=0; 44     if(l==r) 45     { 46         T[id].rank=num[nid[l]];//初始的深度  47         return ;  48     } 49     built(L(id),l,M(id)); 50     built(R(id),M(id)+1,r); 51 } 52 void down(int id) 53 { 54     T[L(id)].lazy+=T[id].lazy; 55     T[R(id)].lazy+=T[id].lazy; 56     T[id].lazy=0; 57 } 58 void updata(int id,int l,int r)//区间懒标记更新  59 { 60     if(T[id].l>=l&&r>=T[id].r) 61     { 62         T[id].lazy++; 63         return ; 64     } 65     if(T[id].lazy) 66         down(id); 67     if(l<=M(id)) 68         updata(L(id),l,r); 69     if(r>M(id)) 70         updata(R(id),l,r); 71 } 72 int query(int id,int pos)//单点查询  73 { 74     if(T[id].l==pos&&T[id].r==pos) 75     { 76         T[id].rank-=T[id].lazy; 77         T[id].lazy=0;//记得清空标记  78         return T[id].rank; 79     }  80     if(T[id].lazy) 81         down(id); 82     if(pos<=M(id)) 83         return query(L(id),pos); 84     else  85         return query(R(id),pos); 86 } 87 void dfs1(int u) 88 { 89     if(fa[u]) 90         dfs1(fa[u]);//上面还有节点，继续往上  91     int v; 92     //往下拆边  93     for(int i=head[u];~i;i=S[i].ne) 94     { 95         v=S[i].v; 96         updata(1,in[v],out[v]);//整个子树的层数都减1  97     } 98     head[u]=-1; 99     out[u]=in[u]; 100 }101 int main()102 {103     int n,m,u,v,x;104     scanf("%d%d",&n,&m);105     init(n);106     for(int i=1;i