考虑一棵无根树的生成方式：需要决定一个好的顺序从而达到不重不漏地生成所有 $n$ 个点的无根树。
类似有向无环图的拓扑排序，可以定义一种无根树的“拓扑排序”：每一轮将当前的叶子删去。这样可以很容易算出直径。设删除的轮数为 $r$，则当最终剩余一个孤点时，直径 $d=2r$，否则直径 $d=2r-1$。为了生成无根树，我们考虑进行逆操作，在当前的树上加叶子。在此之前，为了不重不漏地对无根树进行表示，我们考虑如下的唯一表示方法：设 $\text{dis}(x)$ 为节点 $x$ 在添加叶子过程中第几轮被添加上树的。对于$S=\{x\mid \text{dis}(x)=\text{const}\}$（也即同一层的节点），显然两棵有标号无根树同构但标号不同，当且仅当每个上述节点$x$的叶子节点的标号集合不同。我们总是将 $x$ 标号小的先行添加为其儿子。这样就不会出现因“两棵树本身同构，子节点编号集合相同导致重复计数的问题”。同时，为了方便、准确地计算，我们严格规定，新加入的 $k$ 个叶子节点在新树上就是全部的叶子节点。也即在旧树上的所有叶子节点在新树上至少有一个儿子。 （更多…）
有集合$S$，$|S|=n$，则有$$\sum\limits_{T \subseteq S}2^{|T|}=\sum\limits_{k=0}^{n}2^k\dbinom{n}{k}=3^n$$。因此，若我们枚举集合，枚举集合的子集的子集做状压DP时，可以得到正确的复杂度$\mathrm{O}(3^n)$而非错误的$\mathrm{O}(2^n\times 2^n)=\mathrm{O}(4^n)$。参见AtCoder ABC 187 F – Close Group。
可以这样证明：考虑某个子集的子集$P \subseteq T \subseteq S$，则$S$中的每个元素有三种状态：$a\in P$，$a \notin P, a \in T$，$a \notin T, a \in S$。显然这样可以唯一表示$S$，$T$以及$P$，对应了所有子集的拆分方案。故原式成立。
看来脑瓜子还是不够灵活啊。以前看到“matching”、“bipartite”一类的标签，试图二分图时只晓得将题目中同一类的元素转化为点，将相对关系转化为边。但实际上，二分图也可以表示其他的二元逻辑关系，例如包含、排除。
例如[NOIP2010 提高组] 关押罪犯，一个经典做法是将罪犯转化为点集，将冲突关系符合一定条件的相互连边，然后二分答案作二分图匹配。（扩展域并查集实质上也是在贪心的基础上，运用“二分图匹配”的思想检查方案合法性……对吧？）
再例如AtCoder ABC 228 G – Digits on Grid，计数DP的转移也是在行、列元素分别作为左部、右部，以方格中的元素作为边权的二分图上进行的。
这道题则非常精妙——CF1634E – Fair Share。看到“要将所有元素分成两个相等的可重集”时，我认为应当用可重集作为二分图的左部和右部。但是这样一来，如何进行匹配呢？正解则是将数组$i$包含元素$a_i$的逻辑关系转化为边——左部为各个数组，右部为相同的元素。可以发现，能够有解的充分必要条件是“每个元素均统共出现了偶数次”，同时“每个数组含有偶数个元素”，那么该图中每个节点的度数均为偶。记得小学奥数的一笔画问题么？它有一个更专业的术语，曰欧拉回路。事实上，一张无向图存在欧拉回路，当且仅当不存在度数为奇的节点。所以，我们直接求解一条欧拉回路，将从左部到右部遍历的边记作$L$，从右部到左部遍历的边记作$R$，就是一个正确的解。
昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。
由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。
今天查看题解，发现有几个重要的，从未考虑过的trick：
是的，又是一道考试时想出正解没有打出来的题目
根据题意，我们很容易想到一个朴素的类区间DP——令$dp(i, j)$表示现在将第$i$件货物划分到第$j$箱中，且作为箱内的最后一件货物，所需最小花费。容易写出转移：$$dp(i, j) = \min\limits_{k \in [0, i) \land \sum\limits_{p=k+1}^{i} a_p \leq W } dp(k, j-1) + \sum\limits_{p=k+1}^{i} a_p + \textrm{极差}\{a_t \mid t \in [k + 1, i]\}$$，初值有$dp(0, 0) = 0$，应求得$\min\limits_{j \in [1, n]} dp(n, j)$。
Problem D – Codeforces Round #127 (Div. 1)
多模式串匹配，是不是又是AC自动机啊？
显然，每个文本串中，模式串的排列构成的子序列的逆序对数量只和模式串有关。所以我们可以对模式串建立Trie树，每扫入一个文本串的单词就进行匹配。可以做到$\mathrm{O}(K)$，K为文本串总长（虽然单个字符串的长度极小可以$\mathrm{O}(NK)暴跳$）。这样就构建出一个由$1$到$n$构建的数列。
枚举$15!$的全排列然后暴搜显然不可行。我们注意到，如果钦定一个数$x$，只要知晓当前的排列中前$j$位分别是哪些数，就可以立刻算出$x$加入排列后新增的逆序对数量。则我们考虑状压DP。 （更多…）
设 $f(i,j,0/1/2)$ 表示第 $i$ 天持有 $j$ 支股票，并且当天进行了 持有 / 买 / 卖 操作，所能获得的最大的收益。很容易想到以下转移：
$$\begin{aligned}&f(i,j,0) = \max \{f(k,j,t) \mid k < i,t\in\{0,1,2\}\}; \\
&f(i,j,1)= \max \{f(k,p,t) \mid k < i-w, p \leq j,t\in\{0,1,2\}\}; \\
&f(i,j,2)= \max \{f(k,p,t) \mid k < i-w, p \geq j,t\in\{0,1,2\}\} \end{aligned}$$