拿小号打了这场，然而做到这里时少看了条件，最后 10min 才发现，没有 AK，身败名裂……
赛后看就是 sb 题……
（好像这题也不值 2500 吧？）
首先注意到一条很重要的条件：对于每棵树，都存在一种 DFS 序使得叶子被访问到的顺序就是与它相连的用电器的编号。
这说明，对于每棵树的任意子树，里面所有叶子对应的用电器的编号是连续的。
既然连续就能方便 DP 了。
正着做不好设计状态。反过来，求最少能保留多少条边。
那么就是每个用电器对应的叶子到根上的边都要选。没有限制的全部能删掉。
然后由于用电器对应的叶子的 DFS 序递增，所以对于一个用电器集合 \(\{S\}(|S|\ge 2)\)，如果这里面每个用电器都和同一个根相连，那么 \(S\) 的花费 \(cost_S\) 是 \(cost_{S-x}+dep_x-dep_{lca(x,y)}\)，其中 \(x\) 是 \(S\) 中编号最大的用电器，\(y\) 是 \(S\) 中编号第二大的用电器。
上 DP。
先记 \(f_{i,j,0}(i<j)\) 表示第 \(i\) 个用电器和第 \(j\) 个用电器如果都选第 \(0\) 棵树时，\(dep_{x_i}-dep_{lca(x_i,x_j)}\) 的值。\(f_{i,j,1}\) 同理。
再记 \(fpre_{i,j,0}(i\le j)\) 表示第 \(i\) 个用电器到第 \(j\) 个用电器都选在第 \(0\) 棵树时的总花费。大概是个类似前缀和的东西。\(fpre_{i,j,1}\) 同理。
再记 \(dp_{i,j,0}(i>j)\) 表示只考虑前 \(i\) 个用电器，第 \(j\) 到第 \(i\) 个用电器都选在第 \(0\) 棵树，且第 \(j-1\) 个用电器选在第 \(1\) 棵树的最小花费。\(dp_{i,j,1}\) 同理。
转移，枚举第 \(k\) 到第 \(j-1\) 个用电器选在第 \(1\) 棵树（且 \(k-1\) 选在第 \(0\) 棵树）。\(dp_{i,j,0}=fpre_{j,i,0}+\min(dp_{j-1,k,1}+f_{k-1,j,0}-(dep_{x_j}[k\ne 1]))\)。
解释一下。
\(fpre_{j,i,0}\) 就是 \(j\) 到 \(i\) 的花费。
\(dp_{j-1,k,1}\) 就是 \(k\) 到 \(j-1\) 的最小花费。
\(f_{k-1,j,0}\) 是因为：考虑从小到大加入 \(j\) 到 \(i\)，按上文说的最大编号和次大编号计算贡献。所以加入 \(j\) 时，就会比原来的花费多 \(dep_{x_j}-dep_{lca(x_j,x_{k-1})}\)，也就是 \(f_{k-1,j,0}\)。
当 \(k\ne 1\) 时，由于 \(fpre\) 中算的贡献中 \(j\) 是要自力更生的，但是实际上此时 \(k-1\) 可以给 \(j\) 一些已经用过的边（这个费用就是上面的 \(f_{k-1,j,0}\)）。所以要把 \(dep_{x_j}\) 减掉。
这是个 \(O(n^3)\) 做法。
优化也很显然。设 \(mn_{i,0}=\min(dp_{i-1,j,1}+f_{j-1,i,0}-(dep_{x_i}[j\ne 1]))\)。\(mn_{i,1}\) 同理。
那么有 \(dp_{i,j,0}=fpre_{j,i,0}+mn_{j,0}\)。
时间复杂度 \(O(n^2)\)。
传说有 \(O(n)\) 做法，但我不会……
代码中略微有一点不一样，稍微注意。