TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

34.7% (35/101)

Tags

Description

Farmer John、Farmer Jiang 還有Loli Farmer 是三位辛勤的農夫。

原本他們各有各自的農場,種著各自喜歡的作物。

一天,他們都想種一棵果樹但景氣不佳,三人資金不足,所以只好合資種一顆果樹。

雖然是合種的,但是每個人還是有自己想要種的作物

  Farmer John 想要種他最喜歡的 牛奶果實(Milk Fruits),好討好奶牛Bessie

  Farmer Jiang 想要種 上面有 H 字樣的 H 果實(Heuristic Fruits),好換得啟發式遊戲光碟。

  Loli Farmer 想要種 棒棒糖蕃薯(Lolipop Yams),好取得小女孩的歡心

為了滿足所有人的需求,

他們透過基因改造,研發出一株能讓三人滿意的MHP Tree(Max H Power Tree or Milk & Heuristic & loliPop Tree)

這株樹跟其他品種不一樣,相當的特別。

MHP Tree由 n 個節點(由 1 編號到 n),所構成的樹,而且根一定是編號為 1 的節點,每個節點上都可以長出各種不同的作物。

值得一提的是,棒棒糖蕃薯不能長在葉子上,牛奶果實 以及 H 果實則不能長在根上

而MHP Tree採收的方式也很特別,農夫們會選定一個節點,然後把那個節點以上(包括該節點)的所有作物全部採收

現在三位農夫聘請你當他們的顧問,

在一連串的生長與掉落過程中,

你必須找出某一時刻,從某個節點採收,共可以採收到多少作物。

Input Format

本題只有一筆測試資料。

第一行有一個數字 n ,代表MHP Tree的節點數 (1 <= n <= 106)

接下來有 n-1 行,每行有兩個數字a,b代表在MHP Tree中節點 a 與節點 b 相連(我們保證它是一棵樹)
第 n 行有一個數字 m ,代表接下來有 m 個時間點(包括生長掉落以及採收)(1 <= a,b <= n)

接下來 m 行,會有一個字串s

若字串s為"Grow"(不含雙引號)後面則跟著三個數字 w,k,c,代表在節點 w 上長出了 c 個 k 作物(k=0:牛奶果實,k=1:H果實,k=2:棒棒糖蕃薯)

若字串s為"Drop"(不含雙引號),後面則跟著三個數字 w,k,c,代表在節點 w 上掉落了 c 個 k 作物(k=0:牛奶果實,k=1:H果實,k=2:棒棒糖蕃薯)

若字串s為"Query" (不含雙引號),後面則跟著一個數字 w,代表我們要查詢現在如果從節點 w 採收,共可以採收到多少作物。

(PS.一開始樹上沒有任何作物。)

Output Format

對於每筆操作:

若操作為"Grow"或是"Drop",請在錯誤操作時輸出一行"Error"並當做無事件發生,否則按照事件產生生長或掉落動作。

若操作為"Query",則輸出一行三個由空白字元隔開的三個整數a,b,c,代表從節點w可以採收到a個牛奶果實,b個H果實以及c個棒棒糖蕃薯。

Sample Input 1

3
1 2
1 3
7
Grow 1 1 1
Drop 2 1 1
Query 1
Grow 2 0 2
Grow 3 1 3
Grow 1 2 4
Query 1

Sample Output 1

Error
Error
0 0 0
2 3 4

Hints

Grow 1 1 1
-> 根節點只能種植棒棒糖蕃薯 輸出 "Error"

Drop 2 1 1
-> 目前節點2尚沒有任何作物,輸出"Error"

Query 1
-> 1(0,0,0) + 2(0,0,0) + 3(0,0,0) = (0,0,0)

Grow 2 0 2
-> 2(2,0,0)

Grow 3 1 3
-> 3(0,3,0)

Grow 1 2 4
-> 1(0,0,4)

Query 1
-> 1(0,0,4) + 2(2,0,0) + 3(0,3,0) = (2,3,4)

Problem Source

原TIOJ1493 / 建中校內培訓第六次模擬考試。
Problem Setter:hallogameboy、peter50216
(Adapt From:POJ Monthly)

Subtasks

No. Testdata Range Score
1 0 9
2 1 9
3 2 9
4 3 9
5 4 9
6 5 9
7 6 9
8 7 9
9 8 9
10 9 9
11 10 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 131072 262144 1
1 10000 131072 262144 2
2 10000 131072 262144 3
3 10000 131072 262144 4
4 10000 131072 262144 5
5 10000 131072 262144 6
6 10000 131072 262144 7
7 10000 131072 262144 8
8 10000 131072 262144 9
9 10000 131072 262144 10
10 10000 131072 262144 11