c310. PE:蘋果之塔
標籤 :
通過比率 : 34人/40人 ( 85% ) [非即時]
評分方式:
Tolerant

最近更新 : 2017-11-23 20:29

內容

終於脫離了神經病的操控,小風來到了第二座塔。這座塔似乎被蘋果樹所包圍著,不過小風還是毫不遲疑地進入了塔里。
塔裡面只有一個奇怪的老巫婆,並詢問小風前來的目的
「那邊那位年輕人,為何闖入這座塔?」
「痾...不好意思,我的女朋友被抓住了,我只是想要救她,卻不知道他被關在哪一座塔。」
「喔所以你就是那位闖遍世界各地的冒險者囉?我知道那位綁架你女朋友的人,我可以幫助你找到他,不過你得先幫我一件事。」
「好的,沒問題。」
「塔周圍的蘋果樹看到沒?你看這個樹我每次可以指定一個生長點x,如果他上面有蘋果,我們就把他一起吃掉,反之如果沒有,經過我的魔法後,他就會自己長出蘋果。」
「哇嗚~好神奇喔。」
「所以我現在想要請你幫我做一件事,每次我問你某個生長點x往上一共有多少顆蘋果,你要立刻能夠回答出來。」
「嗚...這有點困難ㄟ」
所以小風只好再次尋求各位的幫忙了...

輸入說明
輸入第一行有一個正整數n代表這顆蘋果樹上一共有n個生長點,編號為1~n且根部的生長點編號為1
接下來有n-1行,每一行有兩個正整數x,y代表編號x,y的生長點是連在一起的,
並且x,y中編號小的生長點必定距離根部比編號大的生長點近
接下來一行有一個正整數q代表以下有q次詢問或指定
接下來q行每一行均有兩個正整數c,x代表著:
c=1:指定生長點x做題目所敘述的事情
c=2:巫婆想詢問你生長點x以上共有幾顆蘋果(包含生長點x的蘋果如果有的話)
測資點1(20%)滿足n,q<=1000
測資點2(20%)滿足n,q<=50000 且所有c=1必定發生於c=2之前
測資點3(60%)滿足n,q<=50000
輸出說明

對於每個c=2請輸出共有幾顆蘋果在x之上

範例輸入 #1
3
1 2
1 3
3
2 1
1 2
2 1
範例輸出 #1
3
2
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (20%): 0.5s , <1M
不公開 測資點#1 (20%): 0.5s , <1M
不公開 測資點#2 (60%): 1.0s , <1M
提示 :

2017/11/23

測資已加強,感謝yp155136指導

標籤:
出處:
2017高雄市高師大附中資訊學科能力 [管理者: ltf0501 (ltfsjl) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
13734 054025 (東翰) c310
換個方法
959 2018-04-15 22:44