P8315

題面

教訓，先看數據范圍。

考慮直接容斥，枚舉不合法的方案數。對于一種選擇，其答案是 \(k^{n-c}\) 其中 \(c\) 是邊數，然后容斥就完了。

P3732

題面

數據隨機是這題的突破口，考慮只維護前后 \(40\) 位的值。我們習慣性離線下來，按照 \(r\) 排序，然后掃描線。考慮在走 trie 的時候刷新這個深度的最后達成時間，判斷就直接判斷這個桶就好了。

細節：用后綴 \(\max\) 處理一下桶，這樣就是最優的。

P9575

題面 原作者: 喵仔牛奶

這是一道構造，考慮分類討論。

• \(n\) 為偶數，取 \(x=1\)，對半分即可。
• \(n\) 不為偶數，且有奇數個偶數。取 \(x=2\)，貪心拿偶數，然后拿奇數湊到一半即可。
• \(n\) 不為偶數，且有偶數個偶數。不論取什么 \(x\) 都有奇數個奇數，無解。

P5522

題面

用了一個復雜度不優但是很簡單的做法。

考慮從數據范圍下手，我們可以直接給每個位置開 \(3\) 棵線段樹，然后就是區間求和。

具體來說：

1. 如果又有 \(0\) 和 \(1\)，那么無解。
2. 否則如果所有位置都是 ?，那么答案 \(\times 2\)。

修改就是單點修改。

用樹狀數組，加兩個 inline 就能過了。

P4395

題面

挺好一道題。

這是一個構造，考慮在出現 \(x\) 下的最優最少點的樹是多少,設這個函數為 \(f(x)\) .

考慮構造一排兒子，要把這一排加上，那么就要用之前的所有樹放上去，那么就有：

所以所需要的顏色就是 \(\log_2n+1\) 的，直接 dp即可。

P2860

題面

最開始以為有向邊，以為不可做 ??

首先縮個環，然后考慮樹上的答案。

考慮一會后，我們發現葉子兩兩連就可以了，所以 \(ans=\frac{(leaf+1)}{2}\).

P4312

題面

發現是一道假在線題，考慮離線。

發現這個東西最終一定形成森林，所以直接樹剖 \(+\) dsu 就好了。

P9808

題面

拆 \(dis\) 貢獻板子。考慮這樣：

那么原來的式子在每個點需要添加的東西就是：

考慮快速計算中間這玩意，我們有個 trick 來源于這里。

具體來說就是直接跳到根，其中每一個點貢獻次數 \(+w_{edge_i}\)，然后這玩意的答案就是到根鏈上和。

P9555

題面

這種東西屬于抽象數據合并。考慮怎么合并兩個區間。我們發現籃子里的數量種類很少，而且起始方案確定，最終方案也就確定了，而且這個東西直接就能合并，所以直接維護前后籃子狀態的線段樹判斷就好了。

放到樹上有很多細節：

1. 路徑上你要先樹剖找到所有區間然后再合并。
2. 你要用兩個棧維護正反兩種東西，最后合并。

挺難寫的。

P6805

題面

又tm讀錯題了，要保證所有道路掃完。

考慮思考每條邊的貢獻。如果這條邊需要走多少遍。

1. 只有奇數個個兒子，那就走一遍。
2. 只有偶數個兒子，那就走兩遍。

考慮修改帶來的變化，就是鏈上奇偶翻轉，考慮樹剖維護。用一個重鏈前綴數組維護和就好了（具體實現可以只用一個數組）。時間復雜度可以做到 \(O(n\log n)\) 不知道為啥都寫的雙 \(\log\) 的。