e004.
樹形避難所 II
內容
前情提要
在一個樹形避難所中有 $N$ 個房間，待在充滿監視器房間的你，透過監視器的顯示發現存在一些未知的入侵者出現在某些房間。為了保護同伴，你可以選擇開啟或關閉房間之間的通道，而你也會收到來自於某個房間的同伴求救訊號，此時給予所有可能遇見的入侵者數量，以便同伴做好萬全的作戰準備。然而，操縱通道的控制器已不受限制，你只能眼睜睜地看著同伴與入侵者對抗，現在的你 ... 做好準備了嗎？
問題描述
由於上一個樹形避難所已經不再安全，全員轉移到下一個避難所，新的地方將不再是先前的平面構造，新的避難所建構在地下水層中，每一個房間可以在水中移動，並且打通到上一層的某一個房間。不幸地，新的入侵者更加地難纏，想保護大家的你，想藉由破壞某一個房間，將其相連的下層房間的入侵者一同殲滅，情局不斷地變化，哪一個才是最好的破壞手段呢 ...
輸入說明
輸入有多組側資，每組第一行有兩個整數 $N$, $M$，分別為房間數以及接下來的事件數量。接著會有一行 $N$ 個非負整數，表示每一個房間的入侵者數量。接下來的 $M$ 行會有以下 4 種操作：
- 操作 1 $u$ $v$：將房間 $u$ 與上層房間 $v$ 的通道開啟
- 操作 2 $u$：關閉房間 $u$ 與上層的通道
- 操作 3 $u$ $w$：更正房間 $u$ 為 $w$ 個入侵者
- 操作 4 $u$：估算摧毀房間 $u$，可以殲滅的入侵者個數
初始狀態所有通道皆為關閉。
條件限制
- $1 \le N \le 30000$
- $1 \le M \le 100000$
- $1 \le u, v \le N$
- $0 \le w \le 32$
- 保證每個操作皆為合法，維持樹的條件
輸出說明
對於每個操作 4 輸出一行整數。
範例輸入
#1
4 12 0 0 0 1 1 2 1 4 1 1 4 3 4 3 1 3 2 4 1 2 2 4 2 4 1 3 3 2 4 2 4 4
範例輸出
#1
0 1 1 1 0 3 1
測資資訊：
記憶體限制：
64
MB
提示 ：
標籤:
出處:
工作幻想
[管理者：
morris1028
(碼畜)
]