或许是不知梦的缘故，流离之人追逐幻影。
ARC117D Miracle Tree
Anybody，who can tell me，这是个什么题，2115？闹麻了。
感觉思路完全没在道上。
注意到这个绝对值看着非常不舒服，考虑把他干掉，也就是说，考虑把所有点按 $E_i$ 排序，得到排列 $p_1,p_2,..,p_n$。
那么显然有 $\text{dis}(p_i,p_{i+1})\le E_{p_{i+1}}-E_{p_i}$。
我们发现，似乎只需要满足这个条件，整个第一个和第二个条件都能满足。
注意到对于 $i<j<k$，有 $\text{dis}(p_i,p_k)\le \text{dis}(p_i,p_j)+\text{dis}(p_j,p_k)$，注意到 $E_{p_k}-E_{p_i}=E_{p_k}-E_{p_j}+E_{p_j}-E_{p_i}$，发现只要满足最开始的条件，所有的不等式都成立，也就满足了题目中的 $1,2$ 条件。
考虑如何最小，即让 $E_{p_n}-E_{p_1}=\sum_{i=1}^{n-1} \text{dis}(p_i,p_{i+1})$ 最小。
我们并不知道如何惊人注意到 $\sum_{i=1}^{n-1} \text{dis}(p_i,p_{i+1})+\text{dis}(p_n,p_1)\ge 2n-2$，因为每条边至少经过两次，下界在 $\text{dfs}$ 序时取到。
至于如何最大化 $\text{dis}(p_n,p_1)$，显然之直径的两个端点。
感觉对于很多树的性质题还是很有启发意义的。
P1232 [NOI2013] 树的计数
人类智慧，我做不起一点。
看到 $\text{BFS}$ 序，自然想到按照 $\text{BFS}$ 序来分段。把 $b,d$ 按照 $\text{BFS}$ 序重新编号，即使得 $b_i=i$，$d_i$ 相应变化。
观察一下有了 $\text{DFS}$ 序和 $\text{BFS}$ 序后，每个节点的深度 $\text{dep}_i$ 需要满足什么限制。
- 根据 $\text{BFS}$ 序的限制，$\text{dep}_{b_i}\le \text{dep}_{b_{i+1}}$ 。
- 根据 $\text{DFS}$ 序的限制，$\text{dep}_{d_{i+1}}\le \text{dep}_{d_i}+1$ 。这是因为 $d_{i+1}$ 一定是 $d_i$ 到根之间的链上的某个节点的儿子。
发现需要计算的是深度，而深度恰好等于 $\text{BFS}$ 序中 $\text{dep}$ 相同取值的段数 $+1$。求平均数等价于求合法的树的深度的期望，根据期望的线性性，可以将每个点作为分段点的概率分开考虑。
考虑 $i$ 与 $i+1$ 之间什么时候一定会分段。
首先，$1$ 后面必定会分段（根只有一个）；若 $i,i+1$ 同深度，那么 $\text{DFS}$ 序中 $i$ 在 $i+1$ 前面。因此，$\text{DFS}$ 序中若 $i$ 在 $i+1$ 后面，则 $i$ 后一定要分段。
再考虑什么情况下 $i,i+1$ 之间不能分段。根据 $\text{dep}_{d_{i+1}}\le \text{dep}_{d_i}+1$，我们可以得到：当 $d_i<d_{i+1}$，则 $[d_i,d_{i+1})$ 之间至多一个分段点。
这是因为，当 $d_i<d_{i+1}$，就说明了 $\text{dep}_{d_i}\le \text{dep}_{d_{i+1}}$，又有 $\text{dep}_{d_{i+1}}\le \text{dep}_{d_i}+1$，所以 $\text{dep}_{d_i}\le \text{dep}_{d_{i+1}}\le \text{dep}_{d_i}+1$。
那么若 $[d_i,d_{i+1})$ 之间，有一个必须分段的点，那么区间中剩下的点都不能作为分段点了。
因此，可以通过差分的方法，求出每一个点是否能作为分段点。
- 若一个点必须成为分段点，则对答案的贡献为 $1$。
- 若一个点没有被限制，则可以是分段点，也可以不是。由于每个点是否分段独立，所以贡献是 $0.5$。
- 若一个点不能分段，则贡献为 $0$。
时间复杂度 $\mathcal{O}(n)$。
P3971 [TJOI2014] Alice and Bob
我感觉我的智商再次受到了严重的侮辱。也有可能是我太困了。
先抓住一些性质，发现对于 $a_i$ 相同的位置，他们对应的 $x$ 必然是单减的，否则就不会是最长上升子序列长度 $=a_i$。
考虑对于每一个 $a_i$，发现他一定是从最近的 $j\in[1,i-1],a_j=a_i-1$ 转移过来的，这个对应上面那个性质应该可以简单证明。
这样我们可以考虑通过 $i\to j$ 连边建出一颗树。（特别的 $a_i=1$ 时，我们建一个虚点 $0$，然后 $0\to i$）。
注意到同层的必然按照我们建边的顺序单调递减，这个是我们最开始的第一个性质。
有一个很显然的填写方式是填入儿子反过来的 $\text{BFS}$ 序。
注意到要让最长下降子序列的总和最大，所以这样肯定是不对的，我们希望层与层之间也要互相产生贡献。注意到最好的办法是填入儿子反过来的 $\text{DFS}$ 序，因为这样可以让前面的尽可能大，而不会按照层一个一个填进去，能够更多的产生下降子序列。
