模拟18

T1

(N^2h)的(Dp)十分好想，然后用前缀后缀取(min)就能做到(nh)，观察数据可以发现，最后的状态中应该不能有高度，考虑如何去掉高度，如果要拔高某个地方，一定不会拔高(1,4,8)中(4)这种类型
的，因为虽然和(8)的距离减少了但是和另一个的距离增加了，相当于白白耗费，(1,8,4)中(8)这种显然也不会，所以拔高只有可能(4,1,8)中(1)这种，于是可以令(Dp_i)表示(i)高度不变的最小花费，每个(i)只能从不大于它的一段中转移过来，这样转移还是(N^2h)的，因为要枚举高度，不难看出，转移方程是一个二次函数，开口向上，于是就有了(N^2)做法。

继续思考，发现坑能填尽量填不会变劣，于是可以每次填一个大坑，维护一个高度单调递减的栈就可以实现。

T2

正解用三维树状数组，但是莫队可以骗到很多分，甚至可以A掉，所以以后能打还是打一个莫队，~~时间复杂度永远想不到~~

T3

题目中成功把树的直径说的比较高大上，于是题目的意思实际上是将一棵树删去一条边加入一条边重构，使得直径最小，暴力可以将一条边拆开，然后统计答案，考试的时候没想到怎么统计答案，所以没打出来，事实上很简单，新的直径端点一定是原来的四个端点之一，所以将边架在两个直径端点的中间一定是最优的。

那么正解呢？删去的这条边一定是直径上的某一条，如果有多条，那么就是它们的交集，如果没有交，那么答案一定是任意删除一条边均可。

既然这条删除的边在直径上，那实际上就不需要每次删边然后算子树直径了，直接从上到下DP一次然后翻过来一次就完了，方案输出可以暴力跳直径的一半。

T4

每次新加入一个点然后判断能不能缩，如果能就缩，合法了就更新答案。