考虑一棵无根树的生成方式：需要决定一个好的顺序从而达到不重不漏地生成所有 $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$，对应了所有子集的拆分方案。故原式成立。
UPD 02.15：更新了区间操作部分。
约莫半月前练习专题时，发现几道解法多样的题目，其中需要运用一些中高级数据结构。苦于之前没有学习过平衡树，便挑选了一种易于上手、实现简单的平衡树学习，也即FHQ Treap。由11年国家队队员范浩强发明。
为书写方便，文章中可能将直接使用$p$代指某节点的随机权值，$\text{val}$代指节点关键码（即记录的数值），$h$代指树高，$\text{siz}$代指子树大小，$\text{cnt}$代指节点副本数（相同关键码的节点），$\text{rt}$存储根节点编号。
定义：任何形如$f_i=f_{i-1}+f_{i-2}, f_1=x,f_2=y$的数列，称为广义斐波那契数列。
$$F_n=\dfrac{1}{\sqrt{5}}\left[\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n\right]$$
证明方法多样，可惜我都不会。知乎 – 斐波那契通项公式是怎样推导出来的？
下文中以$F_n$代指斐波那契数列的第$n$项，$f_n$代表广义斐波那契数列的第$n$项。
看来脑瓜子还是不够灵活啊。以前看到“matching”、“bipartite”一类的标签，试图二分图时只晓得将题目中同一类的元素转化为点，将相对关系转化为边。但实际上，二分图也可以表示其他的二元逻辑关系，例如包含、排除。
例如[NOIP2010 提高组] 关押罪犯，一个经典做法是将罪犯转化为点集，将冲突关系符合一定条件的相互连边，然后二分答案作二分图匹配。（扩展域并查集实质上也是在贪心的基础上，运用“二分图匹配”的思想检查方案合法性……对吧？）
再例如AtCoder ABC 228 G – Digits on Grid，计数DP的转移也是在行、列元素分别作为左部、右部，以方格中的元素作为边权的二分图上进行的。
这道题则非常精妙——CF1634E – Fair Share。看到“要将所有元素分成两个相等的可重集”时，我认为应当用可重集作为二分图的左部和右部。但是这样一来，如何进行匹配呢？正解则是将数组$i$包含元素$a_i$的逻辑关系转化为边——左部为各个数组，右部为相同的元素。可以发现，能够有解的充分必要条件是“每个元素均统共出现了偶数次”，同时“每个数组含有偶数个元素”，那么该图中每个节点的度数均为偶。记得小学奥数的一笔画问题么？它有一个更专业的术语，曰欧拉回路。事实上，一张无向图存在欧拉回路，当且仅当不存在度数为奇的节点。所以，我们直接求解一条欧拉回路，将从左部到右部遍历的边记作$L$，从右部到左部遍历的边记作$R$，就是一个正确的解。
给大家表演一个一场下青
CodeForces Round 770 Div.2 Problem D – Finding Zero
一道非常有意思的交互和构造题。
考虑能否固定两个数$x, y$，通过它们的相对大小关系，确定其他数中是否存在$0$或最大值$a_{\text{max}}$。
经过一番推导，我们发现，设$x \geq y$的情况下，对于三元组$(a_i=x, a_j=y, a_k=z)$，有$$g(i, j, k)\newline
=\max(a_i, a_j, a_k) – \min(a_i, a_j, a_k)=
\begin{cases}z-y, & z > x \\
x-y, & z \in [y, x]\\
x-z, & z < y\end{cases}$$。所以，设$x=6, y=4$以上式结果为因变量，$z$为自变量，应有以下图像：
在没有或存在一定限制条件的情况下，以DFS遍历经过的节点顺序构成的序列。记$\mathrm{dfn}(x)$为第一次访问该节点的时间戳，$\mathrm{seq}(t)$为访问序为$t$的节点。
容易发现，节点$x$的子树节点的$\mathrm{dfn}$一定是一段连续的区间。故我们可以使用数据结构方便地维护子树的信息。
AtCoder ARC 134 C – The Majority
如此ruzhi的一道题目竟花去两小时有余，比赛结束也没写出来，实在惭愧。
拿到题目，很快想到一种DP：令$f(i, j, k)$表示“考虑到第$i$个盒子，第$1$种小球用去$j$个，第$2, 3, \dots, n$种小球用去$k$个”的方案数。容易转移。
然后发现$a_i$是$10^9$级别。同时题目告诉我们，相同类别小球无法区分，所以要是上述做法正确，为什么要分别给出$a_2, a_3, \dots$呢？如何在转移时确保每一种小球的使用次数正确？立刻想到正解与$\mathrm{O}(a_i)$基本无关。
昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。
由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。
今天查看题解，发现有几个重要的，从未考虑过的trick：