TIOJ 2242

題意

給定一棵 $n$ 個點的樹，樹上每個節點會有一個數字 $a_v$ 代表該節點的存水量
有 $q$ 筆操作，每筆操作給定一個節點 $v$ ，請輸出點 $v$ 當前的存水量，並清空點 $v$ 的水
此外，其他點的水會往點 $v$ 的方向移動一格

subtask

subtask1： $n, q \leq 5000$ , Score: 7
subtask2：保證樹隨機生成，且每筆操作的答案皆非零, Score: 12
subtask3：樹是一條鏈, Score: 22
subtask4：無其他限制, Score: 59

對於 subtask 2, 3, 4， $n, q \leq 10^5$ ，對於所有測資， $0 \leq a_v \leq 10^9$

解法

subtask1

可以注意到每次操作以 $v$ 做 dfs 後， $u$ 的水會跑到他的父親
所以每次操作暴力做 dfs 就好，複雜度 $\mathcal{O}(nq)$

subtask2

考慮每次 dfs 只 dfs 有水的點，由於每次都是戳有水的點，所以每次 dfs 後樹的深度會減少 1
又由於樹是隨機生成的，感性上(?會認為這不會跑太多次，而事實上隨機生的情況下，樹的直徑期望值是 $O(\sqrt{n})$

所以一個不嚴謹的上界會是根號，這題官解有提到好像會是 $\mathcal{O}(nlogn)$ ，但我不太懂就是了

另外有一個小細節是如果有水的連通塊不連通的話可能會爛掉，解決方法是可以將每個點的初始水值加個 $10^{-9}$ ，double 有點討厭所以可以使用 pair<int, bool>，first 代表數值而 second 代表有沒有小數

subtask3

講個兩個做法

線段樹

考慮一個陣列 $p$ ，第 $i$ 項代表原本在第 $i$ 個節點的水現在在哪一個位置
那假如現在戳第 $i$ 個節點，那會需要：
(1) 把所有 $p_j < i$ 的 $p$ 值都 +1
(2) 把所有 $p_j = i$ 的水總和加起來輸出，並把這些水清空
(3) 把所有 $p_j > i$ 的 $p$ 值都 -1

注意到在過程中保證 $p$ 陣列會是非嚴格遞增的
所以可以在線段樹上二分搜更新完 $p$ 值與水量

Treap

用 Treap 就稍微無腦一些，如果戳到有水的點就直接把它 split 成三段然後硬更新完再 merge
戳到沒水的點就可以視為把所有點左移 1 或右移 1，以左移 1 來說，就是刪掉左邊一個 0，並在右邊加一個 0

由於後面的作法一定要用 Treap，所以還是寫一下，不然我比較喜歡線段樹的做法 >w<

subtask4

首先假設水是連通的，那如果我們把每個 degree = 2 的地方都連起來，然後用 subtask3 的作法維護

那假設現在有水的這個連通塊有 $x$ 個葉子，則此圖邊的數量最多只有 $2x - 2$ 條。那使用 subtask2 的想法：只 dfs 有水的地方，複雜度會是 $\mathcal{O}(xlogn)$ ，log 是因為需要處理鏈

再來我們觀察一下每次 dfs 完有水的點會發生甚麼事
首先如果戳的點不是葉子，有水的點會減少 $x$ 個，就算是葉子也會減少 $x - 1$ 個。
但如果戳的點是沒有水的點怎麼辦？仔細想想就會發現這也只會增加至多一個有水的點而已
因此每次戳完，至少會有 $max(x - 2, 0)$ 個點變成沒有水，也因此這樣分析下來複雜度均攤會是 $\mathcal{O}(nlogn + qlogn)$

而如果水不連通就使用 subtask2 的方法，用 pair<int, bool> 存水

另外如果戳到沒有水的點，會需要尋找與它距離最近的有水點，這樣(幾乎)可以視為對那個點抽水
而由於每次有水的點會形成一個連通塊，所以只需要樹壓平 + 線段樹，每次詢問的時候在原樹上二分搜即可

實作

想法講得很簡單，然而這題實作超級討厭，所以稍微打一下實作相關的事情
也感謝 HNO2 提供 code 給我參考 > <

這題一個很麻煩的點是動態更新鏈，隨時把 degree = 2 的點 merge 起來
原因是前面均攤分析是用葉子數量進行分析的，抽完水後要把可以合併的鏈合起來複雜度才會好
會爛掉的例子：

沒合併鏈的話反覆戳紅點和藍點複雜度就會噴到 $\mathcal{O}(nq)$ 了

首先從鏈開始講，存鏈的話我會這樣存：

由鏈端點(紅點)與一個 Treap 組成，Treap 用來維護端點之間的點，也就是藍色的點

可能會有多條鏈共用同個端點：

此外，我會先將這棵樹按照 1 為根做 dfs，且保證鏈的端點為祖先關係
至於為什麼要這樣做？首先這樣做不會讓複雜度爛掉，因為最多只會多一個鏈
再來重要的是這樣我可以使用一次倍增就詢問鏈上的第 $k$ 個點是誰，也可以直接用深度判斷一個點位在鏈上的第幾個位置，讓後面 merge 或 split 都變得比較方便

然後定義重要點為所有鏈端點的集合

而初始的話我設定有 $n - 1$ 條鏈，每條鏈都只有端點而中間的 Treap 是空的

再來來講每次戳一個點之後要怎麼好好維護，假設現在戳的點是點 $v$

首先需要先分三個 case：

點 $v$ 是重要點
點 $v$ 在某條鏈上
點 $v$ 不在鏈上 (可以保證他沒有水)

Case1 的話很簡單，甚麼事都不用做
再來跑過所有鏈，用兩點距離找出他是不是在某條鏈上
如果他在某條鏈上，那我會把它再拆成兩個鏈，如下圖：

如果不在的話，我會需要找到在鏈上、還有水且與 $v$ 最近的點 $u$ ，以及它的 parent

如果 $u$ 不是重要點，那我一樣要把鏈拆成兩段。此外並新增一個 $u$ 到前面求出的 parent 的鏈，如下圖：

最多只會多兩條鏈，所以前面均攤分析還是好的

再來是抽水的部分，雖然思考上是需要做 dfs，但由於鏈會一直 split 又 merge，如果要好好做 dfs 可能不好維護它的 adjacency list

然而會發現 dfs 其實是不必要的，只要

知道點 $v$ 到鏈的兩端的距離誰比較小，這樣就可以決定鏈上的水是往哪一邊拉
把鏈按照點 $v$ 到比較近的鏈端點距離排序好，照這樣的順序操作

即可不用 dfs

抽完水之後，會需要 delete 已經沒有水的鏈和 merge 兩條鏈，方法大概是：

建一張只有重要點的圖，兩點之間有邊 iff 存在一條鏈的端點是它們

這樣 delete 沒有水的鏈只需要檢查 degree = 1 的點連出去的鏈即可

而 merge 鏈可以按照到點 1 的距離大到小排好，跑過所有 degree = 2 的點再判一下如果是祖先關係就代表需要 merge 這兩條鏈

其他細節

首先是維護最近的點前面提到要樹壓平線段樹，要記得隨時更新有水點位置
每次抽水後更新的量會跟當前鏈的數量有關，總之好好更新複雜度就會是好的

再來 Treap 大概要做的事情有：

基本的 split-merge
二分搜出第一個或最後一個有水的點

大概需要維護水的總和、最小值、最大值、有水的節點數量與子樹 size

記得水要用 pair<int, bool> 代表

另外為了方便，當鏈上的點完全沒有水我才會把它刪掉，不會因為兩端沒有水而改變鏈的大小
反正複雜度也沒有差，還不用特判只有一個點有水的 case

其他想到再補

後話

這題我寫了四天，共 591 行，第一次寫那麼噁的題目寫出來還是有點開心的
但因為沒人要寫我好難過，就打了這篇

如果有人想要嘗試的話建議可以打打一部分就對拍驗一下
不然最後可能會 debug de 到中風

希望有人會來寫 QQ