[SDOI 2017] 蘋果樹

一些閑話：前排真的超級熱熱熱熱熱熱熱熱熱熱熱熱熱熱熱熱熱熱。要熱死了要熱死了要熱死了 ?????????。

神奇背包。

可以發(fā)現(xiàn) \(t-h\leqslant k\) 是一個非常辣手的限制，有了它至少需要記錄選取的最深深度和 \(t\)，這就直接有 \(n^2\) 的空間復(fù)雜度了。所以考慮用一些奇怪的手段把它優(yōu)化掉。

考察樹形依賴限制，可以發(fā)現(xiàn)在一個點取蘋果后，至少要在它到根的路徑上每一個點中取一個蘋果，這就和深度掛上了鉤。那么題意實際上轉(zhuǎn)化成了欽定一個點作為選取點中深度最深的點，它向上到根的鏈所包含的點必選且 選一次 不計入蘋果個數(shù)，其它的點（當(dāng)然也包含鏈上的點，只是個數(shù) \(a_i'=a_i-1\)）不能選超過 \(k\) 個。

另外也可以發(fā)現(xiàn)，欽定的點一定是葉子節(jié)點，因為向下延伸可以無花費地增加一個蘋果。

以這條鏈為分界線，可以將這棵樹分為三部分：鏈左側(cè)，鏈上，鏈右側(cè)。事實上可以用 \(\rm dfs\) 序來考慮這個問題，算出鏈左側(cè)與鏈右側(cè)的 \(\mathtt{dp}\) 值，再枚舉葉子節(jié)點把它們拼在一起。

這里以鏈左側(cè)為例 —— 令 \(dp(i,j)\) 為按 \(\rm dfs\) 序考慮到 \(i\)，體積為 \(j\) 的最大收益，并假定 \(i\) 到根的鏈就是最終選擇的鏈。所以對于 \(u\rightarrow v\) 的父子關(guān)系，首先將 \(u\) 的 \(\mathtt{dp}\) 值傳給 \(v\)，然后 \(v\) 加入 \(a_v-1\) 個 \(v\) 上的蘋果；等 \(\mathtt{dp}\) 完 \(v\) 這棵子樹后進(jìn)行回傳，加入 \(1\) 個 \(v\) 上的蘋果，因為此時 \(v\) 一定不在鏈上了，這里 需要注意的是，這一個蘋果是強制加入的，為了滿足樹形依賴限制。前一個 \(\mathtt{dp}\) 可以單調(diào)隊列優(yōu)化，所以復(fù)雜度是 \(\mathcal O(k)\) 的。

對于鏈右側(cè)，需要先將之前的邊倒序遍歷。其次需要在回退的時候才加入 \(a_u-1\) 個 \(u\) 上的蘋果，這樣才能和鏈右側(cè)恰好拼起來。

P6326 Shopping

一些閑話：依稀記得之前做過一道類似的題，但是怎么都找不到了 ??。

\(\text{Update}\)：找到那篇博客了（就是這道題），竟然還是 \(2\) 年前寫的。那時候還在 \(\rm csdn\) 上呢。

首先題目限制實際上可以轉(zhuǎn)化為選一個連通塊，于是有一個 \(\mathcal{O}(nm^2)\) 的 \(\tt dp\)：令 \(dp(i,j)\) 為以 \(i\) 為子樹（必選 \(i\)），花費為 \(j\) 的最大價值。每個連通塊都在它深度最淺的點上計數(shù)了。可以發(fā)現(xiàn)，背包的瓶頸在于兩個背包的合并是 \(\mathcal O(m^2)\) 的。

插入一個元素可以用單調(diào)隊列做到 \(\mathcal O(m)\)，所以我們嘗試用 dfs 序考慮這個問題。但是用 dfs 序也就意味著只能考慮 dfs 序為 \([1,i]\) 或 \([i,n]\) 的一段區(qū)間，不妨就考慮 \([1,i]\) 區(qū)間，我們無法求出某一個子樹的貢獻(xiàn)，只能算出根節(jié)點（也就是 dfs 序為 \(1\)）的貢獻(xiàn)，且時間復(fù)雜度為 \(\mathcal O(nm)\).

于是可以想到點分治。復(fù)雜度降到 \(\mathcal O(nm\log n)\).

CF1286E Fedya the Potter Strikes Back

一些閑話：???????? 講的 \(\text{q-}\)模擬根本聽不懂啊……自閉了。

首先考慮將區(qū)間右端點移動到 \(r\) 對可疑度之和的增量，實際上就是做一個 \(\tt{kmp}\)，從 \(r\) 開始不斷跳 \(\rm nxt\) 進(jìn)行統(tǒng)計，不過這樣做肯定是會 TLE 的。考慮維護(hù)當(dāng)前末尾不斷跳 \(\rm nxt\) 形成的集合 \(S\)，同時維護(hù)這個集合的可疑度之和 \(w\)。把集合中的元素編號成 \(s_1,s_2,\dots, s_k\)，將右指針移到 \(r\) 時，對集合做出如下操作：

• 如果 \(\bold{str}(s_i+1)\ne \bold{str}(r)\)，需要從集合中刪除此元素，同時還需要維護(hù) \(w\)；
• 如果 \(\bold{str}(1)=\bold{str}(r)\)，可以向集合中加入元素。

最后，需要把在集合中的元素的可疑度與 \(w_r\) 取 \(\min\).

如何快速刪除元素呢？維護(hù) \(\text{dif}(u)\) 表示離 \(u\) 最近的 \(\tt kmp\) 樹上的 祖先 \(v\)，滿足 \(\bold{str}(u+1)\ne \bold{str}(v+1)\)，這個函數(shù)可以在拓展到 \(i+1\) 時遞推第 \(i\) 項。利用 \(\text{dif}(u)\) 進(jìn)行跳躍，每次復(fù)雜度就是后一位與 \(\bold{str}(r)\) 不同的集合元素個數(shù)，而且它們被遍歷后就會被刪除。同時，由于每次至多增加一個集合元素，所以均攤復(fù)雜度是 \(\mathcal{O}(n)\) 的。

維護(hù) \(w\) 是經(jīng)典的，可以做一個單調(diào)棧 + 二分來定位當(dāng)右指針為 \(r\) 時，區(qū)間 \([i,r]\) 的可疑度。

如何與 \(w_r\) 取 \(\min\) 呢？直接用 map/set 維護(hù) \((\)可疑度\(\text{, }\)元素個數(shù)\()\)，暴力修改即可。因為每種權(quán)值只有可能被取 \(\min\) 一次，所以復(fù)雜度是對的。總復(fù)雜度 \(\mathcal O(n\log n)\).