edit
做個備份
- 構成樹考慮每個節點的父親的選擇方法。
- 區間移動一個，考慮滑動窗口，即使單調隊列。
- 點分治每個子樹的處理按照從小到大來。
- 有顏色的貢獻，按照排序處理，因爲每個前面只有可能一種相同顔色。
- 有固定的出現次數，思慮鴿巢原理。處理最簡情況。
- 弄成將成爲以後必選的形式（題別讀錯）。
- 博弈的選擇可能是一段連續的區間，可能區間的最值為答案（都遇見 \(2\) 次了）
- 差分約束的轉換關係通常爲：有不等關係，至少、至多；區間信息的這種關係，最優先考慮前綴和構造相減。
- 差分約束，跑最短路求最大值；最長路求最小值。
- 差分约束还应考虑每一个单点的限制是什么。
- 可以從後往前做 DP，就有預知性。
- 求平均數、中位數二分答案，值域稍微大點
- 區間的權值極差問題，考慮尺取法。
一般是求解最小值， 由於中間取值不管，先排序， r 指針一直跳，判斷解，l 指針跳。（因爲前面小的取不到最小值，後面的話就會更大）
- 偏序問題先排序確認某一維的合法。
- 括號的匹配，有如下合法限制：
\(sum_r-sum_{l-1}=0,\forall sum_i-sum_{l-1}\geq0\) - 有兩端點這類問題可以枚舉一個端點，然後另一個端點隨之移動，并判斷。（好像也是遇見了多次）
- 唐死了，有時候真的補補 dp
- \(\max\min\{f_i,f_j\}\)，盡可能使 \(f_i,f_j\) 接近，因爲這樣使得取最小值不會太小，就保證最大值更大
- 你發現 dp 答案不會太大時，可以把答案作爲一個狀態
- 遍歷一個點的相鄰坐標，直接使用循環展開。（在可能充不過的情況下）
- dp 狀態設計考慮所有的情況（0/1 選不選、在 A/B 裏面……）
- 求極差的最小值，且可以支持修改（只會是使一個數增大），從大的入手（他被別的更改指揮使極差更大？所以用它更新小的），判斷他的周圍，更新後丟進隊列裏面，重複即可
- 帶有操縱的 dp，把操縱次數設入狀態
- 既然帶有操縱兒子，那麽可能還要設計這個與父親的是否操縱的狀態（\(f_{u,i,0/1}\) 表示 \(u\) 的子樹切斷了 \(i\) 條邊切不切父親）
- 多個 \(a_i=a_{a_i}\) 的限制需要滿足，就把下標連邊 \(i\rightarrow a_i\)
- 固定了左端點，向右遷越區間 \(\gcd\) 減少較快，減少 \(\log V\) 次就為 \(1\) 了，而且只有 \(\log V\) 種 \(\gcd\) 值
- 序列選數、有限制，求最值，就有時候可以 dp
- 模數 \(p\) 為質數，那麽 \(a^b \equiv a^{b~\text{mod}~{p-1}}~(\text{mod}~p)\)，就是用來降冪的
- 矩陣的階：若 \(d\) 為階，且最小，滿足 \(A^d=I~(\text{mod}~p)\)，所以有 \(A^b\equiv A^{b~\text{mod}~d}~(\text{mod}~p)\)，感覺絕大多數的情況降冪是用模數 \(p-1\)，但任要考慮到 \(p\) 為模數的情況
- 每個 \(i\) 可以給 \(j\) 加貢獻，考慮每個 \(i\) 最終得到的貢獻
- 選不選的，選那些，使用 dp 背包
- 組合數的一般遞推：\(C_n^m=C_{n-1}^m+C_{n-1}^{m-1}\)
- \(C_n^m~\text{mod}~2=1\) 當且僅當二進制下 \(m\) 是 \(n\) 的子集，\(m~\text{bitand}~n=m\)
- \(n\times 2^{n-1}=\sum_{i=1}^n i\times C_n^i\)
- 計數把每一位的貢獻算出，所有位再乘起來
- 又做到了小狀壓的題目，區間節點是一個二進制數，表示一些訊息，區間的合併如果是求並集、交集，使用 \(\text{bitset}\) 較為容易做基礎，可用 \(\text{ST}\) 表，線段樹。
- 區間 \(\text{mex}\) 有 \(O(Q(\sqrt N+\sqrt V))\) 做法，莫隊離線下來，值域分塊維護
- 莫隊塊長至少為 \(1\)，不然除以塊長為 \(0\) 可能會\(\text{\color{#9933FF} RE}\)
- 區間貢獻考慮轉換成前綴貢獻，維護這個前綴貢獻
- 循環序列複製成雙倍
- 後綴數組的 \(\text{height}\) 運用，\(\text{lcp}(sa_i,sa_j)=\min\{\text{height}_{i+1,..,j}\}\)
- 求字符串的不同子串個數，是總個數 \(\frac{n(n+1)}{2}\) 減去重的 \(\sum_{i=2}^n \text{height}_i\)
- AC 自動機上 dp 的套路狀態是：設 \(f_{i,j}\) 表示在自動機上走了 \(i\) 步，在 \(j\) 節點
- \(\text{dep}[\text{lca(u, v)}]\) 可以表示為將 \(u\) 到根的路徑都 \(+1\)，然後求 \(v\) 到根的路徑和
- 樹有了 \(\text{dfn}\) 序，就變得有萬能了，支持一些數據結構
- 區間處理有可能離線
- 樹加邊詢問操作，將加邊都執行，離線按照詢問處理
- 線段樹合併，合併玩的點要現場使用，不然參與父節點的合併可能會被覆蓋一些節點
- 哎不是，重心的一些性質：如果 \(u\) 是 \(\text{root}\) 子樹的中心，則：\(u\) 在 \(\text{root}\) 的重鏈上，且最深，滿足 \(2\times sz_u>sz_{\text{root}}\)（除 \(\text{root}\) 為葉子節點），一般來説就是因爲重鏈上可以求 \(dfn\) 序，且是連續的，所以還可以二分求答案
- 以樹的重心為根時，所有子樹的大小都不超過整棵樹大小的一半
- 樹鍊剖分的點權維護邊權，在詢問兩點路徑時，會把它們 \(\text{lca}\) 的點所對應邊改動或查詢到，所以要特殊處理
- 斐波那契的維護多爲矩陣轉移
- \(\text{Dsu~on~Tree}\) 具體步驟是：遞歸所有輕兒子，答案貢獻更新後要刪除；遞歸重兒子，保留答案貢獻；兒子遍歷完，重新計算自己和輕兒子子樹的貢獻；如果是父節點的輕兒子，則刪除此子樹的所有貢獻，回溯
- \(\text{Dsu~on~Tree}\) 適合用於求子樹的信息
- \(k\) 個點的最短路的最小值求法把一些點分別放進 \(S,T\) 集合，邊權為 \(0\)，那麼從 \(S\) 到 \(T\) 的最短路就是有可能是兩個點的最短路最小值
如何分配點進入 \(S,T\) 集合，考慮枚舉 \(n\) 的二進制位 \(i\)，以 \(k_j\) 的二進制第 \(i\) 位是否為 \(1\) 放入集合。
那麼如果 \(x,y\) 是答案的話，則它們在不同集合，二進制有一位不同，就統計到了。
如若不是，則有滿足上述的條件的其他點成為答案 - 樹鍊的點或邊是否能構成回文，記 \(dis_u\) 為從根到 \(u\) 的字母構成的集合，用一個二進制數表示，二進制位 \(i\) 是 \(1\) 表示第 \(i\) 位是出現奇數次，所以 \(dis_u\oplus dis_v\) 為 \(0\) 或 二進制位只有一個 \(1\) 就是能構成回文，對 \(u\) 的子樹，先求解，再加成貢獻，因為不然可能加到自己子樹的值
- 邊聯通分量可以通過重定向每一條邊使它變成一個強連通分量
- 圖進行了
tarjan操作，就變成樹，便於操作 - 選最優情況的題型有可能用優先隊列