edit
這是我在 5 月 21 日開(kāi)的一篇文案。)___(
暫時(shí)重要的就寫(xiě)這裏了：
多測(cè)清空，特判特殊情況

做個(gè)備份

• 構(gòu)成樹(shù)考慮每個(gè)節(jié)點(diǎn)的父親的選擇方法。

• 區(qū)間移動(dòng)一個(gè)，考慮滑動(dòng)窗口，即使單調(diào)隊(duì)列。

• 點(diǎn)分治每個(gè)子樹(shù)的處理按照從小到大來(lái)。

• 有顏色的貢獻(xiàn)，按照排序處理，因爲(wèi)每個(gè)前面只有可能一種相同顔色。

• 有固定的出現(xiàn)次數(shù)，思慮鴿巢原理。處理最簡(jiǎn)情況。

• 弄成將成爲(wèi)以後必選的形式（題別讀錯(cuò)）。

• 博弈的選擇可能是一段連續(xù)的區(qū)間，可能區(qū)間的最值為答案（都遇見(jiàn) \(2\) 次了）

• 差分約束的轉(zhuǎn)換關(guān)係通常爲(wèi)：有不等關(guān)係，至少、至多；區(qū)間信息的這種關(guān)係，最優(yōu)先考慮前綴和構(gòu)造相減。

• 差分約束，跑最短路求最大值；最長(zhǎng)路求最小值。

• 差分約束還應(yīng)考慮每一個(gè)單點(diǎn)的限制是什么。

• 可以從後往前做 DP，就有預(yù)知性。

• 求平均數(shù)、中位數(shù)二分答案，值域稍微大點(diǎn)

• 區(qū)間的權(quán)值極差問(wèn)題，考慮尺取法。

一般是求解最小值， 由於中間取值不管，先排序， r 指針一直跳，判斷解，l 指針跳。（因爲(wèi)前面小的取不到最小值，後面的話就會(huì)更大）

• 偏序問(wèn)題先排序確認(rèn)某一維的合法。

• 括號(hào)的匹配，有如下合法限制：
  \(sum_r-sum_{l-1}=0,\forall sum_i-sum_{l-1}\geq0\)

• 有兩端點(diǎn)這類問(wèn)題可以枚舉一個(gè)端點(diǎn)，然後另一個(gè)端點(diǎn)隨之移動(dòng)，并判斷。（好像也是遇見(jiàn)了多次）

• 唐死了，有時(shí)候真的補(bǔ)補(bǔ) dp

• \(\max\min\{f_i,f_j\}\)，盡可能使 \(f_i,f_j\) 接近，因爲(wèi)這樣使得取最小值不會(huì)太小，就保證最大值更大

• 你發(fā)現(xiàn) dp 答案不會(huì)太大時(shí)，可以把答案作爲(wèi)一個(gè)狀態(tài)

• 遍歷一個(gè)點(diǎn)的相鄰坐標(biāo)，直接使用循環(huán)展開(kāi)。（在可能充不過(guò)的情況下）

• dp 狀態(tài)設(shè)計(jì)考慮所有的情況（0/1 選不選、在 A/B 裏面……）

• 求極差的最小值，且可以支持修改（只會(huì)是使一個(gè)數(shù)增大），從大的入手（他被別的更改指揮使極差更大？所以用它更新小的），判斷他的周圍，更新後丟進(jìn)隊(duì)列裏面，重複即可

• 帶有操縱的 dp，把操縱次數(shù)設(shè)入狀態(tài)

• 既然帶有操縱兒子，那麼可能還要設(shè)計(jì)這個(gè)與父親的是否操縱的狀態(tài)（\(f_{u,i,0/1}\) 表示 \(u\) 的子樹(shù)切斷了 \(i\) 條邊切不切父親）

• 多個(gè) \(a_i=a_{a_i}\) 的限制需要滿足，就把下標(biāo)連邊 \(i\rightarrow a_i\)

• 固定了左端點(diǎn)，向右遷越區(qū)間 \(\gcd\) 減少較快，減少 \(\log V\) 次就為 \(1\) 了，而且只有 \(\log V\) 種 \(\gcd\) 值

• 序列選數(shù)、有限制，求最值，就有時(shí)候可以 dp

• 模數(shù) \(p\) 為質(zhì)數(shù)，那麼 \(a^b \equiv a^{b~\text{mod}~{p-1}}~(\text{mod}~p)\)，就是用來(lái)降冪的

• 矩陣的階：若 \(d\) 為階，且最小，滿足 \(A^d=I~(\text{mod}~p)\)，所以有 \(A^b\equiv A^{b~\text{mod}~d}~(\text{mod}~p)\)，感覺(jué)絕大多數(shù)的情況降冪是用模數(shù) \(p-1\)，但任要考慮到 \(p\) 為模數(shù)的情況

• 每個(gè) \(i\) 可以給 \(j\) 加貢獻(xiàn)，考慮每個(gè) \(i\) 最終得到的貢獻(xiàn)

• 選不選的，選那些，使用 dp 背包

• 組合數(shù)的一般遞推：\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)

• \(C_n^m~\text{mod}~2=1\) 當(dāng)且僅當(dāng)二進(jìn)制下 \(m\) 是 \(n\) 的子集，\(m~\text{bitand}~n=m\)

• \(n\times 2^{n-1}=\sum_{i=1}^n i\times C_n^i\)

• 計(jì)數(shù)把每一位的貢獻(xiàn)算出，所有位再乘起來(lái)

• 又做到了小狀壓的題目，區(qū)間節(jié)點(diǎn)是一個(gè)二進(jìn)制數(shù)，表示一些訊息，區(qū)間的合併如果是求並集、交集，使用 \(\text{bitset}\) 較為容易做基礎(chǔ)，可用 \(\text{ST}\) 表，線段樹(shù)。

• 區(qū)間 \(\text{mex}\) 有 \(O(Q(\sqrt N+\sqrt V))\) 做法，莫隊(duì)離線下來(lái)，值域分塊維護(hù)

• 莫隊(duì)塊長(zhǎng)至少為 \(1\)，不然除以塊長(zhǎng)為 \(0\) 可能會(huì)\(\text{\color{#9933FF} RE}\)

• 區(qū)間貢獻(xiàn)考慮轉(zhuǎn)換成前綴貢獻(xiàn)，維護(hù)這個(gè)前綴貢獻(xiàn)

• 循環(huán)序列複製成雙倍

• 後綴數(shù)組的 \(\text{height}\) 運(yùn)用，\(\text{lcp}(sa_i,sa_j)=\min\{\text{height}_{i+1,..,j}\}\)

• 求字符串的不同子串個(gè)數(shù)，是總個(gè)數(shù) \(\frac{n(n+1)}{2}\) 減去重的 \(\sum_{i=2}^n \text{height}_i\)

• AC 自動(dòng)機(jī)上 dp 的套路狀態(tài)是：設(shè) \(f_{i,j}\) 表示在自動(dòng)機(jī)上走了 \(i\) 步，在 \(j\) 節(jié)點(diǎn)

• \(\text{dep}[\text{lca(u, v)}]\) 可以表示為將 \(u\) 到根的路徑都 \(+1\)，然後求 \(v\) 到根的路徑和

• 樹(shù)有了 \(\text{dfn}\) 序，就變得有萬(wàn)能了，支持一些數(shù)據(jù)結(jié)構(gòu)

• 區(qū)間處理有可能離線

• 樹(shù)加邊詢問(wèn)操作，將加邊都執(zhí)行，離線按照詢問(wèn)處理

• 線段樹(shù)合併，合併玩的點(diǎn)要現(xiàn)場(chǎng)使用，不然參與父節(jié)點(diǎn)的合併可能會(huì)被覆蓋一些節(jié)點(diǎn)

• 哎不是，重心的一些性質(zhì)：如果 \(u\) 是 \(\text{root}\) 子樹(shù)的中心，則：\(u\) 在 \(\text{root}\) 的重鏈上，且最深，滿足 \(2\times sz_u>sz_{\text{root}}\)（除 \(\text{root}\) 為葉子節(jié)點(diǎn)），一般來(lái)説就是因爲(wèi)重鏈上可以求 \(dfn\) 序，且是連續(xù)的，所以還可以二分求答案

• 以樹(shù)的重心為根時(shí)，所有子樹(shù)的大小都不超過(guò)整棵樹(shù)大小的一半

• 樹(shù)鍊剖分的點(diǎn)權(quán)維護(hù)邊權(quán)，在詢問(wèn)兩點(diǎn)路徑時(shí)，會(huì)把它們 \(\text{lca}\) 的點(diǎn)所對(duì)應(yīng)邊改動(dòng)或查詢到，所以要特殊處理

• 斐波那契的維護(hù)多爲(wèi)矩陣轉(zhuǎn)移

• \(\text{Dsu~on~Tree}\) 具體步驟是：遞歸所有輕兒子，答案貢獻(xiàn)更新後要?jiǎng)h除；遞歸重兒子，保留答案貢獻(xiàn)；兒子遍歷完，重新計(jì)算自己和輕兒子子樹(shù)的貢獻(xiàn)；如果是父節(jié)點(diǎn)的輕兒子，則刪除此子樹(shù)的所有貢獻(xiàn)，回溯

• \(\text{Dsu~on~Tree}\) 適合用於求子樹(shù)的信息

• \(k\) 個(gè)點(diǎn)的最短路的最小值求法把一些點(diǎn)分別放進(jìn) \(S,T\) 集合，邊權(quán)為 \(0\)，那麼從 \(S\) 到 \(T\) 的最短路就是有可能是兩個(gè)點(diǎn)的最短路最小值
  如何分配點(diǎn)進(jìn)入 \(S,T\) 集合，考慮枚舉 \(n\) 的二進(jìn)制位 \(i\)，以 \(k_j\) 的二進(jìn)制第 \(i\) 位是否為 \(1\) 放入集合。
  那麼如果 \(x,y\) 是答案的話，則它們?cè)诓煌希M(jìn)制有一位不同，就統(tǒng)計(jì)到了。
  如若不是，則有滿足上述的條件的其他點(diǎn)成為答案

• 樹(shù)鍊的點(diǎn)或邊是否能構(gòu)成回文，記 \(dis_u\) 為從根到 \(u\) 的字母構(gòu)成的集合，用一個(gè)二進(jìn)制數(shù)表示，二進(jìn)制位 \(i\) 是 \(1\) 表示第 \(i\) 位是出現(xiàn)奇數(shù)次，所以 \(dis_u\oplus dis_v\) 為 \(0\) 或 二進(jìn)制位只有一個(gè) \(1\) 就是能構(gòu)成回文，對(duì) \(u\) 的子樹(shù)，先求解，再加成貢獻(xiàn)，因?yàn)椴蝗豢赡芗拥阶约鹤訕?shù)的值

• 邊聯(lián)通分量可以通過(guò)重定向每一條邊使它變成一個(gè)強(qiáng)連通分量

• 圖進(jìn)行了tarjan操作，就變成樹(shù)，便於操作

• 選最優(yōu)情況的題型有可能用優(yōu)先隊(duì)列

• 這幾天做樹(shù)上問(wèn)題，遇見(jiàn)了重心相關(guān)的，就又要掌握一些性質(zhì)

選一個(gè)點(diǎn)，然後讓其餘點(diǎn)走到它，要求總距離最短，那這點(diǎn)就選重心

• 還是有個(gè)經(jīng)典的東西：求 \(\forall i~\text{dis}[\text{lca(u, i)}]\)，帶權(quán)值的，求法一樣，是如果 \(w_i\leftarrow w_i+v\)，就把 \(i\) 到根的權(quán)值 \(+v\)，再詢問(wèn) \(u\) 到根的路徑和。

• 又如果是 \(\sum_i w_i\times dis_{lca(u,i)}\) 呢？也是差不多，做差分，要額外維護(hù) \(\sum_i dis_i-dis_{fa_i}\)，原因是 \(i\) 加到根就會(huì)是它本身的 \(dis_i\)，這樣就把一個(gè)點(diǎn)的信息變成了區(qū)間信息，方便用線段樹(shù)維護(hù)。

• 帶權(quán)重心維護(hù)、尋找方法：\(\text{size}_u\geq \lceil\frac{\text{size}_{\text{root}}}{2}\rceil\) 且 \(u\) 最深。維護(hù)區(qū)間最大 \(\text{size}\)，然後 \(dfs\) 序大的深度也大，如果滿足右子樹(shù)最大值 \(\geq\) 就繼續(xù)往右跳，否則往左。

• 樹(shù)上比如說(shuō)求路徑長(zhǎng)度在 \([L,R]\) 且邊權(quán)和最大的問(wèn)題，求法：就考慮點(diǎn)分質(zhì)，當(dāng)前要算經(jīng)過(guò)重心的答案，當(dāng)前的深度是 \(i\)，那麼就要找前面子樹(shù)深度在 \([L-i,R-i]\) 最大的邊權(quán)和，那之後如果深度變?yōu)?\(i+1\) 的時(shí)候，就要找前面子樹(shù)深度在 \([L-i-1,R-i-1]\) 最大的邊權(quán)和，所以本質(zhì)上就是在區(qū)間的滑動(dòng)窗口（每次先刪掉超出 \(R-i\) 的部分，再加入 \(L-i\) 的部分），所以使用單調(diào)隊(duì)列解決（如果 \(L-i<0\)，就只有刪掉超出 \(R-i\) 的部分，而不是啥也不執(zhí)行，這一點(diǎn)坑人）?，F(xiàn)在又考慮新的貢獻(xiàn)如何加入進(jìn)隊(duì)列裡面？考慮一個(gè)簡(jiǎn)單的情況，清空隊(duì)列，遍歷這個(gè)子樹(shù)，就加入，但清空隊(duì)列的最壞複雜度 \(O(\max_{i\in\text{pretree}}\text{size}_i)\)，容易卡成 \(O(n)\)，有一個(gè)優(yōu)化，我在處理 \(\text{root}\) 為根的樹(shù)的時(shí)候，把它的子樹(shù)按照最大深度排序就行了，正確性顯然，這樣就是遍歷子樹(shù)正確的時(shí)間了，我們排序多了個(gè) \(\log n\)，那這算法的起始複雜度就是 \(O(n\log^2n)\) 的。

• 二進(jìn)制表示狀態(tài)有想過(guò)嗎？

• 點(diǎn)分治再搞錯(cuò)重心求解以導(dǎo)致的 TLE 真該悔改。

• 換根 dp 可以設(shè)置 \(u\) 子樹(shù)外的點(diǎn)集的狀態(tài)。

• 狀壓裏面的子集枚舉：for(int T = S; T; T = (T - 1) & S)，時(shí)間複雜度是 \(O(3^n)\)。

• 瞎幾把寫(xiě)，今天玩到個(gè)（逆）康托展開(kāi)，求全排列的排名，和排名為 \(k\) 的全排列。好像那個(gè)題，知道這玩意，也要觀察數(shù)據(jù)範(fàn)圍。好吧，算法的思想就是：從左往右考慮 \(a_i\)，他左邊有 \(x_i\) 個(gè) \(<\) 它，他的排名就是 \(1+\sum_{i=1}^n (a_i-x_i-1)\times (n-i)!\)，反過(guò)來(lái)求排名為 \(x\) 的，就應(yīng)該是如下：把 \(x-1\)，代表有 \(x\) 個(gè)排列 \(<\) 它，每次有一個(gè)數(shù) \(y=x ~ \text{/} ~ (n-i)!\)，再然後 \(x\leftarrow x ~ \text{mod}~ (n-i)!\)，就是第 \(y\) 個(gè)沒(méi)被標(biāo)記的數(shù)就是第 \(i\) 的值。

• 好像 STL 的 size 類型是 size_t，也就是 unsigned 的，所以用到了 size 一定要轉(zhuǎn)換成 int 型。

• 對(duì)數(shù)據(jù)範(fàn)圍要有探討，想到數(shù)據(jù)範(fàn)圍的性質(zhì)。

• 樹(shù)上路徑求值，能轉(zhuǎn)化成差分形式。