1493 . 三個農夫
TopCoder
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
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
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 |