都退役了，做個錘子。
CF1354E
題
首先 1 和 2 能連，2 和 3 能連，1 和 3 不能連。
先不管數量限制，看什麼時候無解。
隻要不是二分圖就無解。
現在可以考慮數量了，把每個連通塊跑個二分圖染色染成黑點和白點，先令每個連通塊都是黑點比白點少。
把所有黑點染 2，如果這樣 2 的數量還是太多就無解了。
對于中間的，我們把一些連通塊的黑白互換，就可以增加一定數量的黑點，還是把所有黑點染 2，相當于這樣會增加一定數量的，這好像就是個背包問題，然後還要記錄方案。
1 和 3 有差別嗎
CF643G
題
神仙題。
從這題推廣。
給出一堆數，令 (k= lfloorfrac{100}{p}
floor) 每次删除 (k+1) 個兩兩不同的數，删到不能删為止，可以保證對的數不會被删掉。
然後把兩堆删過的直接這樣合并也是可以的（把一堆裡的數一個個加入另一個）要考慮被加入的那堆裡是不是已經存在那個數了。
既然區間可合并于是就可以線段樹了...
區間指派就打 tag + 對應那堆改成隻剩一種數，次數是區間長度
存的時候存數值 + 處理後那堆還剩下這個數的出現次數
注意細節
P3527
題
整體二分，隻會兩個 log
CF1363E
題
父親節點操作的選擇權包含兒子的所有操作，是以兒子節點的操作代價如果比父親大，就等價到父親節點操作，于是把所有節點的操作代價改成它到根一路上代價的最小值，然後代價形成一個大根堆，這樣操作越深的節點越劃算了。
然後再觀察一個性質，就是 0->1 和 1->0 兩兩配對，很明顯 0->0 和 1->1 如果參與 shuffle 就是白給，反正那些 0->1 1->0 都至少要 shuffle 一次。
然後統計子樹裡 0->1 和 1->0 數量，自下而上的處理，這題就解決了。
CF1000F
題
有點像 HH 的項鍊
維護對每一個位置，這個位置上的數上一次出現的位置 (pre)，這是基本操作了。
離線右端點排序+線段樹，枚舉右端點 (r) ，儲存每一個位置的 (pre)，區間查詢 ([l,r]) 最小的 (pre) 是否能小于 (l)（直接改成 INF）記得每次更新把 (pre) 的 (pre) 移去，即對于 (i)，如果 ([i,r]) 中 (a_i) 出現兩次，那 (pre_i) 再小也不能被選到，這個每次移動右端點隻會修改對應的一個。
這題還可以莫隊硬上
CF639E
題
這個 (c) 明顯提示二分答案了
最優順序用鄰項交換排序求出
令開始做 (i,j) 中先做的那個時已經用去了 (x) 時間。
令先做 (i) 更優，則有：
[p_i imes (1-frac{c(x+t_i)}{T})+p_j imes (1-frac{c(x+t_i+t_j)}{T})>p_i imes (1-frac{c(x+t_i)}{T})+p_j imes (1-frac{c(x+t_i+t_j)}{T})
]
[xp_i+p_it_i+xp_j+p_jt_i+p_jt_j<xp_j+p_jt_j+xp_i+p_it_i+p_it_j
]
[p_jt_i<p_it_j
]
即 (frac{t_i}{p_i}<frac{t_j}{p_j})
對于 (frac{t_i}{p_i}) 相等的數可以随意交換，這樣可以求出每個數最早和最晚可以放在哪個時間做完，這些數形成連續的一段，且段與段之間位置關系确定，第 (i) 個問題最早完成時間為這一段的起始時間加 (t_i)，最晚就是這個段的結束時間，即這個段的起始時間加這個段中所有問題用時之和，起始時間為這個段之前所有段用時之和。
如果兩問題産生了 paradox，則同時滿足兩個條件：
(p_i<p_j)
(p_i imes(T-cx_i)>p_j imes(T-cx_j))
(x_i) 代表完成時間。
一定考慮最壞情況是否有 paradox，是以 (x_i) 取最小時間，(x_j) 取最大時間。
先按 (p_i) 排序，把第一個式子的影響去掉。然後儲存所有 (p_k<p_i) 的 (p_k imes(T-cx_k)) 的最大值，做比較，即可。注意 (p) 是嚴格小于。
做這步的時候可以看出答案是有單調性的..
如果兩問題處于同一段，也并不會有問題，因為在判斷是否有 paradox 時，兩數分别處于段的第一個和最後一個。
P3320
題
把所有點按 dfs 序排序後，答案就是所有相鄰兩點距離之和，再加上第一個和最後一個點的距離。
每次插入點的時候找出上一個點和下一個點（當然也可能不存在）
用樹狀數組 + 倍增做這個，也可以用 set
寫了一堆分類讨論（
P4099
題
(dp_{u,i}) 表示 (u) 的子樹中，(u) 的拓撲序排第 (i) 位的方案數。
然後 dp，相當于每一個點維護着一個序列，先枚舉 (u) 和子樹的序列中 (u) 和子樹的根的拓撲序，然後把子樹那個序列加入 (u) 的序列。
我們已知的隻有 (u) 已經被合并的所有子樹中對應那個序列中 (u) 的具體位置，并不知道序列裡具體每一個數是什麼，但是我們知道有多少種合法序列，對以 (v) 為根的子樹也是這樣。我們把兩個序列合并，可以看作先确定每個位置是前者還是後者，然後再确定整個序列的具體情況。
P3240
題
和上一題大概是一個套路
先把上來給了等于關系的并成一個元素，然後就是每一個子樹維護有多少種不同的序列，往上合并。
(dp_{u,i}) 表示 (u) 的子樹裡對應的序列有 (i) 的小于号的方案數。
CF587D
題
首先看無解，如果一個點連了三個同色邊肯定無解，如果有不止一種顔色有兩條邊連在這個點上，那麼也無解。
這樣每一個點最多存在一種顔色，有兩條邊連在了這個點上，把這個顔色找出來，用 2-SAT 兩個邊不同選加個限制。
然後一個點至多連一條邊，可以用 2-SAT 字首優化。
（xa_b 代表第 x_a 為 0/1，sa_b 代表前 a 個元素中是否有 1）
二分答案，有一些邊直接強制不能選，然後跑 2-SAT。
2-SAT 強制選一個數或不選：連一條邊 (
eg x o x) 或 (x o
eg x)。
CF587F
題
AC 自動機 fail 樹 dfs 序上建樹狀數組。
根号分治一下就好了。。
CF585F
題
把 (s) 的長度 (geq lfloor frac{d}{2}
floor) 的字串建出來，然後 AC 自動機上數位 dp。
找出第一次比對上的位置，乘上剩下沒填的位的方案數。最後加起來。
P4068
題
把能配對的數連邊，連出來一定是二分圖。
按數的 所有質因子 個數 之和 奇偶性 分成兩類點，同一類點之間不可能連邊，因為連邊的兩個點所有質因子個數之和相差 1.
然後就是二分圖比對問題了。
CF932E
題
懶得寫式子了。
(k) 很小，用第二類斯特林數的性質，把指數上的 (k) 拆下來，然後二項式定理。
P4609
題
首先最高的那個建築肯定看得到，我們任意選取一個方案：
把每個看得見建築和它擋住的建築分成一組，這樣最高的建築左邊有 A 組，右邊有 B 組。如果隻是分組就是第二類斯特林數了，但是一組内還是可以排，一個大小為 (n) 的組，方案數是 ((n-1)!)，這就是圓排列個數，可以想到枚舉最高建築的位置，然後用第一類斯特林數求解。
但這樣還過不掉，需要優化。直接把除了最高的建築以外的先分好組，然後在其中選擇 (A-1) 個組在左邊即可。預處理斯特林數群組合數，可以 (O(1)) 回答單組詢問。
CF666E
題
離線，字尾數組 + 線段樹合并（按 height 從小到大）
碼碼碼
CF575A
題
首先考慮一步一步遞推，當然會逾時。
用矩陣加速，線段樹維護矩陣區間乘積，從小到大依次處理每個特殊值，兩個特殊值之間的部分可以加速，分類讨論一下。還需要快速幂。
這題沒什麼意思，就是碼碼碼
P2868
題
看到平均值肯定是 0/1 分數規劃沒問題
對于有向邊 ((u,v)) 把邊權賦為 (T_{(u,v)} imes mid - F_u) 然後看有沒有負權環即可，有負權環代表答案 (geq mid)。
CF512D
題
有的點沒法删，把能删的點拿出來，會形成一些有根樹和無根樹。
有根樹意思是根節點連向了一個不能删除的節點。
設 (dp_{i,j}) 代表第 (i) 個樹删除 (j) 個點的方案數，最後的答案就是這些樹的答案合并起來。
對于有根樹，設 (dp_{i,j}) 表示 (i) 的子樹删 (j) 個數的方案數，自底向上轉移即可。
對于無根樹，每個點可以是先删完兒子節點再删的，也可以是删完 除了它子樹内點 之外的所有點之後，才删掉這個點。不僅要算上面的方案，還要額外計算第二種的方案，第二種其實就是對每個點 (u) 算一遍 子樹删點方案數 * 子樹外删點方案數，注意删除後一定要保留 (u)，也就是子樹不能全删，這樣就可以做到不重不漏了。
P5283
題
(k) 很小，一個個取就行了。
先求一遍異或字首和 (pre_i)，那麼 ([l,r]) 的區間異或和就是 (pre_r oplus pre_{l-1})。
先把對于每個 (r)，(pre_r oplus pre_{l-1}) 的最大值扔進堆裡，然後每次取出堆頂，删除堆頂，如果堆頂取出的 (r) 對應的第 (k) 大值，就把 (r) 對應的第 (k+1) 大值再扔進堆裡，這樣每次取出的一定是沒取過的區間中，最大的區間。
用 Trie 存下所有 (pre_i) 即可快速求出與 (x) 異或的第 (k) 大的數，但是這樣是沒法處理 (l>r) 的情況，也就是 (l>r) 也的方案會被算進去，解決方法也很簡單，(pre_r oplus pre_{l-1}=pre_{l-1} oplus pre_r)，同一對數會重複計算兩次，由于它們值一樣，肯定是連續取出來的，是以取最大的 (2k) 個數，最後答案再除以 (2)，就好了。
P2325
題
樹分塊闆子。
樹分塊不能像序列分塊一樣，必須通過使得一個點能夠包含在不止一個塊中，才能使得每個塊保證 ([B,3B]) 之間。
方法就是自下而上，對一個點，每次把子樹中所有點加入棧，如果目前棧中的點數大于等于 (B) 就和根組成一個塊，由于是遞歸操作，這個子樹很大子樹裡就會分好塊，進棧的點數不會超過 (B)，是以這樣一個塊不會大于 (2B)。
最後會剩下一些點不夠組成一個塊，就并進一個已有的塊，是以會出現一個大小上限 (3B) 的塊。
P2825
題
沒有
#
就是車放置，典型的二分圖最大比對問題。
這題
#
可以把一行或一列分成兩部分，把每行，每個連續段
.
段作為左邊的點，把每列，每個連續段
.
段作為又邊的點，相交的兩段連邊，跑最大比對就可以了。
P3888
題
狀壓 dp，沒什麼意思。
要存兩行的狀态。
P4251
題
這種第 (k) 大的最小值，看着就很像是二分答案。
二分答案以後發現就是隻允許選 (leq mid) 的數，能不能選出來 (n-k+1) 個，典型的二分圖最大比對模型。
P3705
題
0/1 分數規劃 + 二分圖帶權最大比對。
P3227
題
如果沒有限制，把每個 ((x,y)) 拆點，從上往下連，選每條邊代表選擇 (f(x,y)=z)，求最小割。
考慮怎麼把限制加上，就相當于有一些邊不能同時選了，而且如果把圖看作分層圖，這些邊一定滿足相差的層數 (> D)。
把紅邊加上去就可以了，這樣如果相鄰兩處切點相距太遠，中間一定會容下一條紅邊，導緻 S 與 T 仍然連通。
P4827
題
這個指數很小啊，那基本就是第二類斯特林數了？
(x^n=sum_{k=0}^n S(n,k) imes C(x,k) imes k!)
通常幂是沒法 dp 的，但是組合數可以 dp，這是轉成組合數的好處之一。
（這裡預設 (C(a,b)=0 (b>a))）
首先随便一個點當根，設 (dp_{u,i}=sum_{vin subtree(u)} C(dis_{u,v},i))。
先考慮一個點往父親轉移 (sum_{vin subtree(u)} C(dis_{fa_u,v},i)=sum_{vin subtree(u)} C(dis_{u,v}+1,i)=sum_{vin subtree(u)} C(dis_{u,v},i)+C(dis_{u,v},i-1)=dp_{u,i}+dp{u,i-1})。
那麼轉移方程就是 (dp_{u,i}=sum_{vin son(u)} dp_{v,i}+dp_{v,i-1})，自底向上轉移即可。
注意 (i=0) 的情況，就是 (dp_{u,0}=sum_{vin son(u)} dp_{v,0}+1)，要把 (u) 自己給加進去，(u) 到自己的距離顯然為 (0)。
剩下點的可以換根 dp 求出答案。
在每個點當根，計算最終答案的時候，枚舉 (dp) 第二維，乘上對應的斯特林數和階乘。
P5308
題
wqs 二分降維，去掉 (k) 的限制。
後面的 1D/1D dp 可以斜率優化。
CF571D
題
對兩種集合分别建一個并查集，利用按 size 合并控制樹高在 (log n) 級别，在 M 集每個點記錄以這個點為根最後一次被清空的時間，每次清空都要找到根。
同時每次合并的時候要記錄這個點是什麼時候合并的，可以看作是記錄在邊上，因為會有合并之前有清空而合并後沒有。
處理加操作更加複雜一點，需要每個點用一個 vector 記錄操作，裡面元素是按時間遞增的。然後查詢的時候先求出被查詢的數最後一次被删除的時間，然後它的每一個祖先節點上二分查找即可。事實上隻有一個點需要二分，比它更深的一定貢獻為 0，比它更淺的一定所有操作都未被清空（不要忘記處理合并時間，同上）。
這裡還會涉及到區間和，用字首和就可以了，每次加入元素的時候也更新字首和。
CF521E
題
顯然三條路徑在同一個邊雙聯通分量中。先把割邊都删掉，然後把每個連通塊分别處理。把 dfs 樹建出來。
最後有解肯定是長這個樣子的
S 和 T 代表起點和終點
自下而上處理，每個點維護自己所在子樹裡能達到的深度最淺的點以及對應的那條返祖邊（因為随着深度的上升，深度更深的點可能隻能到達自己了，不能到達祖先，這樣這條邊就沒用了，而最淺的那條邊是最優情況）如果一個點 (u) 有兩個或更多子樹有返祖邊可以到達這個點的祖先，則拿出來 (u) 和另外兩個邊連到的點（這兩個可以是同一個點），就是圖中的藍點了。
P3749
題
先不考慮 (mx^2+c)。
這題讀題有些困難，但是可以發現其實就是在一些 (d) 中讓你選取一些，并且有一些"選了 a 則必選 b"的限制，每個 (d) 都隻有被選或不被選兩種狀态，而不是可以被多次選擇，後面的花費也是如此，這基本可以排除 dp 的可能性，這題就是個網絡流題。
對于每個 (d_{i,j}) 建一個點，然後向它的所有子區間連邊，很明顯，這就是個最大權閉合子圖模型。
但這樣邊數太多，考慮優化，([i,j]) 隻連到 ([i+1,j]) 和 ([i,j-1]) 就可以達成目的了。
再考慮加入 (mx^2+c)。
對于每個代号單獨建一個點，注意到 (mx^2) 和這個代号選了幾種是無關的，隻和這個代号選或沒選有關。如果選擇了這個代号的壽司則必選這個代号對應的點，這是一個限制。
然後就相當于讓這個點是最大權閉合子圖模型中一個收益為 (-mx^2) 的點即可。
還有 (cx)，這個其實沒啥用，每個壽司單獨分開算就可以了，直接減到它的收益裡面就行了，但我為友善起見建了兩條邊。
剩下就是最大權閉合子圖了。
下圖中省略了代表區間的點和單點所連的邊
（也就是
1-3,1-2,2-3,1,2,3
的 (d) 産生的邊）
P3750
題
期望看起來無從下手，先嘗試尋找某個局面的最優解法，就是最少花多少步可以全變
。
首先觀察到一個性質，每個開關至多操作 (1) 次，因為操作 (2k) 次等于沒操作，操作 (2k+1) 次等于操作 (1) 次，這樣就把答案限制在了 (leq n)。
這是所有這種一個開關控制多個燈改變亮暗情況的點燈類型的題的共有性質。
但是這樣還是不能做，于是觀察開關 (i)，改變的是 (i) 的所有約數，有的燈可以被多個開關影響到，但是 (n) 号燈一定隻有 (n) 号開關能影響，因為 (n) 已經是最大的數了，不可能有它的倍數。
于是 (n) 号開關是操作還是不操作，直接就定下來了。
這樣以後 (n-1) 号開關是否操作，也能确定，以此類推，每個開關操作與否直接被确定。
大多數點燈題都是能找到這樣一個隻被一個開關控制的燈的切入點的。
然後我們發現，到這一步之後，問題被轉化了，有 (n) 個數，其中 (m) 個是 (0)，剩下的是 (1)，每次等機率随機選取一個數，将它變為另一個狀态，求使得所有數中 (1) 的個數小于等于 (k) 的期望步數。而且這隻和 (1) 的數量有關了，和哪幾個開關是 (1) 無關。
期望一般考慮倒推，設 (dp_i) 為目前有 (i) 個 (1) 時，期望還需要多少步才能變成全 (0)。
當 (ileq k) 時 (dp_i=i)
否則 (dp_i=frac{i}{n}dp_{i-1}+frac{n-i}{n}dp_{i+1}+1)
直接高斯消元不可行，但是這個式子看起來可以遞推。
[i imes dp_i+(n-i) imes dp_i=i imes dp_{i-1}+(n-i) imes dp_{i+1}+n
]
[i imes (dp_{i}-dp_{i-1})= (n-i) imes (dp_{i+1}-dp_{i})+n
]
[dp_{i}-dp_{i-1}=frac{n-i}{i} imes (dp_{i+1}-dp_{i})+frac{n}{i}
]
還需要一個邊界條件：(dp_{n}-dp_{n-1}=1)。
就可以遞推了。
最後 (dp_m) 就是答案。