e004: 樹形避難所 II
Tags : Link/Cut Tree 啟發式合併
Accepted rate : 6人/6人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-01-13 15:50

Content

前情提要

在一個樹形避難所中有 $N$ 個房間,待在充滿監視器房間的你,透過監視器的顯示發現存在一些未知的入侵者出現在某些房間。為了保護同伴,你可以選擇開啟或關閉房間之間的通道,而你也會收到來自於某個房間的同伴求救訊號,此時給予所有可能遇見的入侵者數量,以便同伴做好萬全的作戰準備。然而,操縱通道的控制器已不受限制,你只能眼睜睜地看著同伴與入侵者對抗,現在的你 ... 做好準備了嗎?

問題描述

由於上一個樹形避難所已經不再安全,全員轉移到下一個避難所,新的地方將不再是先前的平面構造,新的避難所建構在地下水層中,每一個房間可以在水中移動,並且打通到上一層的某一個房間。不幸地,新的入侵者更加地難纏,想保護大家的你,想藉由破壞某一個房間,將其相連的下層房間的入侵者一同殲滅,情局不斷地變化,哪一個才是最好的破壞手段呢 ...

 

 

Input

 

輸入有多組側資,每組第一行有兩個整數 $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$
  • 保證每個操作皆為合法,維持樹的條件
Output

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

Sample Input
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
Sample Output
0
1
1
1
0
3
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
Hint :
Tags:
Link/Cut Tree 啟發式合併
出處:
工作幻想 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」