e003: 樹形避難所 I
標籤 : Link/Cut Tree 啟發式合併
通過比率 : 3人/7人 ( 43% ) [非即時]
評分方式:
Tolerant

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

內容

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

輸入說明

輸入有多組側資,每組第一行有兩個整數 $N$, $M$,分別為房間數以及接下來的事件數量。接著會有一行 $N$ 個非負整數,表示每一個房間的入侵者數量。接下來的 $M$ 行會有以下 4 種操作:

  • 操作 1 $u$ $v$:將房間 $u$ 與 $v$ 的通道開啟
  • 操作 2 $u$ $v$:將房間 $u$ 與 $v$ 的通道關閉
  • 操作 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 輸出一行整數。

範例輸入
4 11
0 0 0 1 
1 1 2
4 1
1 3 4
4 3
1 2 3
4 1
2 1 2
4 2
4 1
3 3 2
4 2
範例輸出
0
1
1
1
0
3
測資資訊:
記憶體限制: 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 , <1M
公開 測資點#5 (13%): 1.0s , <1M
公開 測資點#6 (13%): 1.0s , <10M
公開 測資點#7 (13%): 1.0s , <1M
提示 :
標籤:
Link/Cut Tree 啟發式合併
出處:
工作幻想 [編輯:
morris1028 (碼畜)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」