標(biāo)題：套娃


? ? 作為 drd 送的生日禮物，atm 最近得到了一個(gè)俄羅斯娃娃。他對(duì)這個(gè)俄羅斯娃娃的構(gòu)造很感興趣。


? ? 俄羅斯娃娃是一層一層套起來的。假設(shè)：一個(gè)大小為 x 的俄羅斯娃娃里面可能會(huì)放任意多個(gè)大小小于 x 的俄羅斯娃娃（而市場(chǎng)上的套娃一般大娃里只能放一個(gè)小娃）。


? ? drd 告訴 atm ，這個(gè)俄羅斯娃娃是由 n 個(gè)小娃娃組成的，它們的大小各不相同。 ? ?我們把這些小娃娃的大小從小到大依次記為 1 到 n 。


? ? 如果 atm 想觀賞大小為 k 的小娃娃，他會(huì)先看這個(gè)小娃娃是否已經(jīng)在桌子上了。 ? ?如果已經(jīng)在桌子上，那么他就可以觀賞了。否則他就打開桌子上某一個(gè)俄羅斯娃娃，將它套住的所有的小娃娃拿出來，擺在桌子上。
? ? 一開始桌子上只有 drd 送的大小為 n 的娃娃。注意，他只會(huì)將其中所有小娃娃拿出來，如果小娃娃里面還套著另外的小娃娃，他是不會(huì)將這些更里層的這些小娃娃拿出來的。
? ? 而且 atm 天生具有最優(yōu)化的強(qiáng)迫癥。他會(huì)最小化他所需要打開的娃娃的數(shù)目。


? ? atm 是一個(gè)怪人。有時(shí)候他只想知道觀看大小為 x 的娃娃時(shí)需要打開多少個(gè)娃娃（但并不去打開）；有時(shí)候聽 drd 說某個(gè)娃娃特別漂亮，于是他會(huì)打開看。現(xiàn)在請(qǐng)你輸出他每次需要打開多少個(gè)娃娃。


【輸入格式】
第一行兩個(gè)數(shù) n m ，表示娃娃的數(shù)目以及 atm 想看的娃娃的數(shù)目。
接下來 n - 1 行，每行兩個(gè)數(shù) u v，表示大小為 u 的娃娃里面套著一個(gè)大小為 v 的娃娃。保證 u > v 。
接下來 m 行，每行形如：
? P x ：表示 atm 一定要看到大小為 x 的娃娃；
? Q x ：表示 atm 只想知道為了看大小為 x 的娃娃，他需要打開多少個(gè)娃娃，但實(shí)際上并不打開他們。


【輸出格式】
輸出 m 行。對(duì)應(yīng)輸入中P操作或Q操作需要打開（或假想打開）多少個(gè)俄羅斯娃娃。


【樣例輸入】
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


【數(shù)據(jù)范圍】
對(duì)于 30% 的數(shù)據(jù)：n, m <= 1000
對(duì)于 100% 的數(shù)據(jù)：n, m <= 100000




資源約定：
峰值內(nèi)存消耗 < 256M

CPU消耗 ?< 1000ms

#include "cstdio" #include "cstring" #include "iostream" bool book[100020]; int node[100020]; using namespace std; int main(){int big=-99999999;int n,m,i,j,a,b;scanf("%d%d",&n,&m);memset(book,0,sizeof(book));for(i=0;i<n-1;i++){scanf("%d%d",&a,&b);node[b]=a;if(big<a)big=a;if(big<b)big=b;}node[big]=big+1;book[big+1]=1;int goal;char c;for(i=0;i<m;i++){ //scanf("%c%d",&c,&goal);cin>>c>>goal;int time=0;if(c=='Q'){int tmp=node[goal];while(book[tmp]!=1){tmp=node[tmp];time++;}printf("%d\n",time);}else if(c=='P'){int tmp=node[goal];while(book[tmp]!=1){book[tmp]=1;tmp=node[tmp]; time++;}printf("%d\n",time);}}return 0; }
//剛開始用了很多方法從上到下，后來發(fā)現(xiàn)用一維數(shù)組記錄上一個(gè)挺方便的 ，因?yàn)樯弦粋€(gè)節(jié)點(diǎn)只有一個(gè)，然后標(biāo)記一下。

//寫的很渣 ?也沒有記憶，希望有錯(cuò)的地方大神能指出來。

總結(jié)

以上是生活随笔為你收集整理的2014 C专科C组第五题 套娃的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。