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 \leq N \leq 30000$
$1 \leq M \leq 100000$
$1 \leq u, v \leq N$
$0 \leq w \leq 32$
保證每個操作皆為合法，維持樹的條件

輸出說明

對於每個操作 4 輸出一行整數。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (12%): 1.0s , <1K
公開測資點#1 (12%): 1.0s , <1M
公開測資點#2 (12%): 1.0s , <1M
公開測資點#3 (12%): 1.0s , <1M
公開測資點#4 (13%): 1.0s , <10M
公開測資點#5 (13%): 1.0s , <10M
公開測資點#6 (13%): 1.0s , <1M
公開測資點#7 (13%): 1.0s , <10M

提示：

標籤:

Link/Cut Tree 啟發式合併

出處:

工作幻想 [管理者： morris821028@gmail.com

morris1028 (碼畜) ]

編號	身分	題目	主題	人氣	發表日期
36501	fire5386 (becaidorz)	e004		225	2023-07-19 22:20