#21 P9755

題目傳送門

首先，看上去這個(gè)題直接不是很友好，我們考慮二分轉(zhuǎn)為判斷性問(wèn)題。

然后一個(gè)這類在樹上 topo 遍歷每一個(gè)節(jié)點(diǎn)的最優(yōu)方案類問(wèn)題有一個(gè) Trick：我們找出當(dāng)前最優(yōu)的節(jié)點(diǎn)，將其與其父親合并。

具體地，在確定一個(gè)答案 \(T\) 之后，我們可以在 \(O(1)\) 的時(shí)間內(nèi)求出或通過(guò)二分在 \(O(\log n)\) 的時(shí)間內(nèi)每一個(gè)點(diǎn)的最晚訪問(wèn)時(shí)間 \(t_i\)。具體地，我們可以先預(yù)處理每一個(gè)節(jié)點(diǎn)的一次函數(shù)值什么時(shí)候小于 \(1\)，優(yōu)先統(tǒng)計(jì) \(1\) 的貢獻(xiàn)，然后對(duì)剩余部分我們就考慮對(duì) \(b_i\) 和 \(c_ix\) 分別求和。

然后我們只需要考慮兩個(gè)問(wèn)題：

• 怎么判斷一個(gè)節(jié)點(diǎn)是否比另一個(gè)節(jié)點(diǎn)更優(yōu)（確定排序規(guī)則）；

• 怎么合并一個(gè)節(jié)點(diǎn)和其父親；

我們優(yōu)先思考第二個(gè)問(wèn)題。我們?cè)诤喜⑼暌粋€(gè)節(jié)點(diǎn)后，這個(gè)新節(jié)點(diǎn)的最晚的訪問(wèn)時(shí)為 \(t_i-1\)。因?yàn)?\(t_i\) 是合并前的最小時(shí)間點(diǎn)，所以 \(t_i-1\) 也一定是合并后的最小時(shí)間點(diǎn)。

因此我們發(fā)現(xiàn)可以簡(jiǎn)化上述流程：直接找到當(dāng)前時(shí)間點(diǎn)最小的點(diǎn)，然后直接把它到根的所有未訪問(wèn)點(diǎn)訪問(wèn)。

時(shí)間復(fù)雜度為 \(O(n \log V \log n)\)，可以通過(guò)數(shù)學(xué)推導(dǎo)優(yōu)化到 \(O(n \log V)\)。

#22 P8817

題目傳送門

看到 \(n \le 2500\)，且邊權(quán)為 \(1\)。我們就知道可以在 \(O(n^2)\) 的時(shí)間內(nèi)用 bfs 預(yù)處理出任意兩點(diǎn)間的距離。

然后我們考慮一個(gè)問(wèn)題，假如我們確定了 \(b,c\)，那么我們希望取到 \(b\) 可達(dá)的點(diǎn)中，權(quán)值最大的點(diǎn)，和 \(c\) 可達(dá)的點(diǎn)中，權(quán)值最大的點(diǎn)。

但是這兩個(gè)點(diǎn)可能相同，或者與 \(b,c\) 相同，但是可以確定的是，我們只需要枚舉前 \(3\) 大的節(jié)點(diǎn)即可。

時(shí)間復(fù)雜度為 \(O(n^2)\)。

#23 AGC036F

題目傳送門

注意到限制的形式類似于圓的標(biāo)準(zhǔn)方程，于是我們將其轉(zhuǎn)化為：“在第一象限，以原點(diǎn)為圓心，半徑分別為 \(n\) 和 \(2n\) 畫兩個(gè) \(1/4\) 圓，然后圓環(huán)部分放 \(2n-1\) 個(gè)車，使得它們不能互相攻擊”。

其中排列轉(zhuǎn)化為放車是經(jīng)典Trick。

這是一個(gè)每一個(gè)元素有上下界的問(wèn)題，我們考慮將其轉(zhuǎn)化為無(wú)下界，然后容斥的問(wèn)題。（想到這一步是因?yàn)槊恳粋€(gè)非法方案也是一個(gè)前綴）

根據(jù)幾何知識(shí)，第 \(i\) 個(gè)元素的上下界 \([L_i,R_i]\)，為 \(L_i=\lceil\sqrt{n^2-i^2}\rceil,R_i=\lfloor\sqrt {4n^2-i^2}\rfloor\)，這里你應(yīng)該也看出來(lái)了，只有 \([0,n)\) 的元素是有下界的。

我們先考慮求出沒有限制的答案。我們按上界從小到大來(lái)考慮每一個(gè)元素的決策，因?yàn)檫@樣可以保證每一次當(dāng)前決策一定會(huì)影響后面。我們假設(shè)升序排序后的 \(R\) 為 \(r\)，那么答案為 \(\prod \limits_{i=0}^{2n-1}r_i-i+1\)。

那么我們考慮類似上述方法容斥。

顯然的，假設(shè)有 \(k\) 個(gè)元素的上界為 \(L_i-1\) 的貢獻(xiàn)為 \(f_k\)，那么對(duì)答案的貢獻(xiàn)就是 \((-1)^kf_k\) 。

類似上述做法，我們考慮維護(hù)按上界排序，其中 \([0,n)\) 的元素按 \(L_i-1\) 排序，\([n,2n)\) 的元素按 \(R_i\) 排序。（顯然，為了保證前面一定影響后面，你需要另一端設(shè)為第二關(guān)鍵字）

我們考慮對(duì)每一個(gè) \(k\) 單獨(dú) dp 一次。我們?cè)O(shè) \(f_{i,j}\) 為考慮了前 \(i\) 個(gè)元素，且有 \(j\) 個(gè)元素的上界為 \(L_i-1\) 的合法方案數(shù)。顯然，存在初始狀態(tài) \(f_{0,0}=1\)。接下來(lái)討論轉(zhuǎn)移：

如果該元素在 \([n,2n)\) 內(nèi)：

• 那么它原本有 \(R_i+1\) 個(gè)選取方案；

• 因?yàn)榕判颍运懊孢x \(L_i-1\) 為下界的元素和沒有下界的元素都會(huì)限制它的選取，這里的總數(shù)為 \(j+c_0\)，其中 \(c_0\) 為前面沒有下界的元素，這個(gè)在轉(zhuǎn)移時(shí)直接統(tǒng)計(jì)即可。

• 那么這個(gè)轉(zhuǎn)移為 \(f_{i+1,j} \leftarrow f_{i,j} \times(R_i+1-j-c_0)\)

如果該元素在 \([0,n)\) 內(nèi)，且選擇 \(L_i-1\) 為上界：

• 這里的討論類似上文，不再贅述；
• 轉(zhuǎn)移為 \(f_{i+1,j+1} \leftarrow f_{i,j} \times (L_i-j-c_0)\)。

如果該元素在 \([0,n)\) 內(nèi)，且不選擇 \(L_i-1\) 為上界：

• 它原本有 \(R_i+1\) 個(gè)選取方案；

• 因?yàn)?\(L_i\) 最大為 \(n\)，在 \([0，n)\) 內(nèi) \(R\) 最小為 \(\sqrt 3n\)，所以每一個(gè)選取上界為 \(L_i-1\) 的元素都會(huì)限制它的選取，這類限制個(gè)數(shù)為 \(k\)。

• 因?yàn)榇藭r(shí) \(R_i\) 一定大于 \([n,2n)\) 內(nèi)的每一個(gè) \(R_i\)，因此這類限制個(gè)數(shù)為 \(n\)。

• 如果之前有下界的元素選取 \(R\) 作為上界，因?yàn)榕判颍@類元素也會(huì)對(duì) \(i\) 有限制，這類限制的個(gè)數(shù)為 \(c_1-j\)，其中 \(c_1\) 為之前有下界的元素個(gè)數(shù)。

• 轉(zhuǎn)移為 \(f_{i+1,j} \leftarrow f_{i,j} \times(R_i+1-k-n-c_1+j)\)。

時(shí)間復(fù)雜度為 \(O(n^3)\)。

#24 P8819

題目傳送門

下位紫，看懂題目是最大難點(diǎn)。

首先我們考慮形式化題意：

給定一個(gè) \(n\) 個(gè)點(diǎn) \(m\) 條邊的有向圖連通圖，你需要支持：

• 禁用（啟用）一條邊；

• 禁用（啟用）到達(dá)一個(gè)點(diǎn)的所有邊；

每一次操作后詢問(wèn)圖上是否每一個(gè)點(diǎn)的出度都為 \(1\)，且每一個(gè)點(diǎn)沿著邊走都可以達(dá)到一個(gè)環(huán)。

顯然，“每一個(gè)點(diǎn)出度為 \(1\)” 是 "每一個(gè)點(diǎn)沿著邊走可以到達(dá)一個(gè)環(huán)" 的充分條件，所以我們只需要判斷每一個(gè)點(diǎn)的出度是否為一即可。

這個(gè)限制很弱，我們直接隨機(jī)賦值然后 Hash 判斷即可，支持操作也是簡(jiǎn)單的。

#25 P4719

題目傳送門

動(dòng)態(tài) dp 就是把轉(zhuǎn)移寫成廣義矩乘的形式，然后利用數(shù)據(jù)結(jié)構(gòu)維護(hù)每一個(gè)位置的轉(zhuǎn)移矩陣和區(qū)間的矩陣值，實(shí)現(xiàn)快速更新 dp 值。

本題中，如果沒有修改，我們會(huì)設(shè) \(f_{i,0/1}\) 表示 \(i\) 點(diǎn)不取/取時(shí)的最大權(quán)獨(dú)立集權(quán)值。顯然有f

接下來(lái)，為了實(shí)現(xiàn)修改，我們給這棵樹套上一個(gè)樹剖，然后把 dp 改成我們常見的樹剖形式。具體地，我們定義 \(f_{u,0/1}\) 表示 \(i\) 點(diǎn)不取/取時(shí)的最大權(quán)獨(dú)立集權(quán)值，\(g_{u,0}\) 表示 \(u\) 的輕兒子都不取且 \(u\) 取的最大權(quán)；\(g_{u,1}\) 表示 \(u\) 不取時(shí)在輕子樹內(nèi)取到的最大權(quán)。我們令 \(son_u\) 為 \(u\) 的重兒子，那么有：

那么我們可以看出來(lái)這是從 \(son_u\) 轉(zhuǎn)移到 \(u\)。因?yàn)榧臃▽?duì) \(\max\) 運(yùn)算具有結(jié)合率，所以我們可以套廣義矩乘。然后因?yàn)樵诰€段樹上，乘法的順序是由鏈頂?shù)芥溛驳模簿褪钦f(shuō)我們是左乘上一個(gè)矩陣，然后我們可以設(shè)計(jì)出轉(zhuǎn)移：

然后我們考慮一下我們?cè)谛薷臅r(shí)，除了修改當(dāng)前點(diǎn)的矩陣，我們還要跳鏈，在鏈頂處修改父親的 \(g\) 值。

時(shí)間復(fù)雜度為 \(O(Mn\log^2 n)\)，其中 \(M\) 是矩陣乘法的時(shí)間復(fù)雜度，為 \(8\)。

#26 P8820

題目傳送門

多次詢問(wèn)，考慮 ddp。因?yàn)闊o(wú)修，所以我們可以預(yù)處理每一個(gè)節(jié)點(diǎn)的矩陣，然后倍增預(yù)處理向上跳 \(2^k\) 步后得到的矩陣積和逆序后的矩陣積。

因?yàn)?\(k \in \{1,2,3\}\)，所以讓我們分類討論。

如果 \(k=1\)：那么就直接是路徑上的點(diǎn)權(quán)和；

如果 \(k=2\)：注意到此時(shí)我們只會(huì)經(jīng)過(guò)路徑上的點(diǎn)，然后直接 dp 即可；

如果 \(k=3\)：那么此時(shí)我們用 \(f_{i,j}\) 表示到路徑上第 \(i\) 個(gè)點(diǎn)，且轉(zhuǎn)移時(shí)從距離 \(i\) 為 \(j\) 的位置轉(zhuǎn)移過(guò)來(lái)的最小權(quán)值和。

轉(zhuǎn)移是簡(jiǎn)單的，寫成矩陣形式后預(yù)處理即可。

#27 P8860

題目傳送門

首先，我們注意到：一條邊只可能在第一次被詢問(wèn)到時(shí)被刪除。

這是顯然的，因?yàn)槿绻谝淮卧儐?wèn)沒有被刪除，那么說(shuō)明它已經(jīng)在 \(1 \rightarrow n\) 的必經(jīng)之路上，那么在之后這個(gè)性質(zhì)不會(huì)消失，所以之后的詢問(wèn)不可能刪除它。

我們定義 \(t_i\) 為第 \(i\) 條邊可能被刪除的時(shí)間，如果第 \(i\) 條邊沒有被詢問(wèn)過(guò)，那么 \(t_i=q+i\)。這樣我們 \(t\) 就有很好的性質(zhì)：\(t_i\) 互不相同。

然后題目其實(shí)就是要求一條路徑，使得路徑上所有邊的 \(t_i\) 升序排序后形成的序列的字典序盡可能大。

然后我們有一個(gè)很自然的貪心：從大到小的加入每一條邊，如果在某一次加邊時(shí) \(1\) 和 \(n\) 連通了，那么此時(shí)的方案就是字典序最大方案。

那么怎么構(gòu)造方案呢，我們這么想：從 \(1\) 出發(fā)，我們可以沿著 \(1\) 的每一條出邊到若干個(gè)點(diǎn)，那么在這些點(diǎn)之中，經(jīng)過(guò)邊 \(t_i\) 最大的點(diǎn)一定是最優(yōu)的，于是我們從這個(gè)點(diǎn)繼續(xù)擴(kuò)展，然后又得到一些新點(diǎn)。那么這個(gè)時(shí)候我們應(yīng)該擴(kuò)展哪一個(gè)點(diǎn)呢？

答案不太顯然：擴(kuò)展到這個(gè)點(diǎn)的邊 \(t_i\) 最小的點(diǎn)。

為什么？因?yàn)樽值湫虻拇笮∈紫仁且茸钚≡氐拇笮。覀兞钌鲜鳇c(diǎn)為 \(u\)，擴(kuò)展到 \(u\) 的點(diǎn)為 \(pre_u\)，如果去擴(kuò)展一個(gè)其他的點(diǎn) \(v\)，那么因?yàn)?\(t_u>t_v\)，所以至少?gòu)默F(xiàn)在來(lái)看，\(v\) 是劣于 \(u\) 的。

可能有人會(huì)問(wèn)：那萬(wàn)一 \(1\) 到 \(u\) 路徑上的最小值小于 \(1\) 到 \(v\) 路徑上的最小值呢？其實(shí)這并不影響。因?yàn)?\(v\) 能和 \(u\) 進(jìn)行比較而不是直接擴(kuò)展 \(v\)，說(shuō)明 \(1\) 到 \(pre_u\) 路徑上的最小值也大于 \(pre_v \rightarrow v\) 的 \(t\)。

綜上，我們只需要每一次擴(kuò)展經(jīng)過(guò) \(t\) 最大的點(diǎn)即可。

#28 ARC186D

題目傳送門

題目有點(diǎn)唬人。

我們觀察合法序列的構(gòu)造，發(fā)現(xiàn)這東西有點(diǎn)像樹。具體地，我們把 \(A_i=0\) 看做葉子，然后 \(A_i=x\) 表示他有 \(x\) 個(gè)兒子。

那么我們可以有以下推論：

• \(\forall_{1 \le x \le n-1} \sum \limits_{i=1}^x A_i \ge x\)：如果不滿足這一條件，說(shuō)明前 \(x\) 個(gè)點(diǎn)內(nèi)的邊數(shù)少于點(diǎn)數(shù)，那么就說(shuō)明前面無(wú)法構(gòu)成一顆樹；

• \(\sum \limits_{i=1}^n A_i=n-1\)：一顆樹有 \(n-1\) 條邊。

條件一對(duì)每一個(gè) \(x\) 都有限制且限制值的變化量一定，那么我們可以把這個(gè)東西轉(zhuǎn)化為格路問(wèn)題。

我們可以把條件一轉(zhuǎn)化為不能觸碰 \(\forall_{x\in[1,n-1]}(x,x)\)，然后出發(fā)點(diǎn)為 \((0,1)\)。在橫坐標(biāo)為 \(i\) 時(shí)：先向上走 \(A_i\) 格，然后再向右走 \(1\) 格。最終要走到 \((n,n)\)。問(wèn)題轉(zhuǎn)化為統(tǒng)計(jì)從出發(fā)點(diǎn)走到終點(diǎn)的合法路徑數(shù)。

那么我們現(xiàn)在先考慮一下字典序的限制。類似數(shù)位 dp，我們枚舉 \(A\) 的前綴，對(duì)每一個(gè)前綴 \(i\) 統(tǒng)計(jì) \(B=[A_1,A_2,A_3,\cdots,A_{i-1},b](0 \le b <A_i)\) 的合法序列 \(B\) 的個(gè)數(shù)。

也就是說(shuō)我們從 \((i,\sum \limits_{j=1}^{i-1}A_i+b)\) 出發(fā)，到 \((n,n)\) 的合法路徑數(shù)。這個(gè)直接求不是很好求，我們考慮容斥。

我們定義 \(f(x_1,y_1,x_2,y_2)\) 表示從 \((x_1,y_1)\) 到 \((x_2,y_2)\) 不考慮限制的路徑數(shù)，等于在長(zhǎng)度為 \(x_2-x_1+y_2-y_1\) 的操作序列上選取 \(x_2-x_1\) 個(gè)向右操作，為 \(\large \binom{x_2-x_1+y_2-y_1}{x_2-x_1}\)。

那么由反射容斥的思想可以得到合法的路徑數(shù)為 \(f(x_1,y_1,n-1,n)-f(y_1,x_1,n-1,n)\)。（這里是 \((n-1,n)\) 的原因是如果選 \((n,n)\) 的話減去的路徑不全是非法的）

#29 CF1039D

題目傳送門

首先，看到這類題，我們要先想對(duì)于一個(gè)確定的 \(k\)，怎么求它的答案。

我們看到一個(gè)子樹內(nèi)，如果它有兩個(gè)以上的兒子，并且可以構(gòu)成一個(gè)長(zhǎng)度大于等于 \(k\) 的鏈，那么我們就直接在子樹內(nèi)合并成鏈；如果沒有，那么就傳遞到父親。這樣就有時(shí)間復(fù)雜度為 \(O(n)\) 的算法。

然后，看到 \(10^5\) 的數(shù)據(jù)范圍和 \(7s\) 的時(shí)間限制，引導(dǎo)我們往根號(hào)級(jí)算法上靠。

對(duì)于這一道題，我們發(fā)現(xiàn)對(duì)于一個(gè) \(k\)，它的答案不大于 \(\dfrac{n}{k}\)，這引導(dǎo)我們考慮根號(hào)分治。

我們?cè)O(shè)閘值 \(T\)，那么當(dāng) \(k \le T\) 時(shí)，我們可以直接暴力求解，時(shí)間復(fù)雜度為 \(O(Tn)\)；當(dāng) \(T < k \le n\) 時(shí)，注意到此時(shí)答案不大于 \(\dfrac{n}{T}\)，二分查找每一個(gè)答案對(duì)應(yīng)的區(qū)間即可，時(shí)間復(fù)雜度為 \(O(\dfrac{n^2\log n}{T})\)；平衡一下復(fù)雜度，當(dāng) \(T=\sqrt {n \log n}\) 時(shí)，時(shí)間復(fù)雜度為 \(O(n\sqrt{n \log n})\)。

#30 P7565

題目傳送門

首先，如果我們已知 \(p\)，那么答案就是這個(gè) \(P\) 個(gè)點(diǎn)的帶權(quán)重心。那么如果 \(P\) 是奇數(shù)，那么答案顯然為 \(1\)，因?yàn)橹匦目梢詮?\(u\) 轉(zhuǎn)移到它相鄰的點(diǎn)，當(dāng)且僅當(dāng)它左右兩邊的兒子數(shù)量相同。

當(dāng) \(P\) 是偶數(shù)時(shí)，它的重心個(gè)數(shù)最大值就是 \(\max dis_{u,v}\)，其中 \(sz_u,sz_v \ge \dfrac{P}{2}\)，且 \(u,v\) 的子樹無(wú)交。

然后我們可以明確：這些重心都在一條鏈上，我們可以以此進(jìn)行分類討論：

• 如果 \(u,v\) 在同一條鏈上：那么貢獻(xiàn)的大小為 \(\min(n-sz_u+1,sz_v)\)；
• 如果 \(u,v\) 不在一條鏈上：那么貢獻(xiàn)的大小為 \(\min(sz_u,sz_v)\)。

我們考慮這兩種是可以互相轉(zhuǎn)化的：也就是換一個(gè)根的事。

然后我們注意到答案的統(tǒng)計(jì)對(duì)象是樹上所有路徑，因此我們直接套上一個(gè)點(diǎn)分治。

在處理當(dāng)前重心時(shí)：我們看到貢獻(xiàn)有一個(gè) \(\min\)，這很不好處理，于是我們考慮欽定最小值。我們按子樹答案從大到小進(jìn)行處理，每一次處理時(shí)我們找一個(gè)和當(dāng)前點(diǎn)不在當(dāng)前子樹的、長(zhǎng)度貢獻(xiàn)最大的節(jié)點(diǎn)，和它進(jìn)行貢獻(xiàn)。

但是直接這樣做我們會(huì)發(fā)現(xiàn)根節(jié)點(diǎn)的貢獻(xiàn)是統(tǒng)計(jì)不到的，所以我們還要再搜索一遍統(tǒng)計(jì)根節(jié)點(diǎn)的貢獻(xiàn)。

細(xì)節(jié)：你需要對(duì)答案取后綴最大值（顯然）。