写在前面

我又又又又掉分了

为了追逐梦想，然后成功s在了路上

而且这次考试又和铁一中打。。。

又被虐了QWQ

考场安排

总体：今天考场上分配时间不太好，主要是因为一直在肝T3，然后放弃了一些题目的暴力分，最后T3的思路竟是我其中想的一种，只是我想了10min又给换掉了，人傻了
具体：

1. 8:00 – 8:15 做一些准备工作，打了板子，然后全部浏览了一遍题目，隐隐感觉到了一丝DP的味道，然后感觉到T1和T3比较好写，并且一眼看出来T4是一道状压DP，具体没有怎么看
2. 8:20 – 9:00 看T1，并且思考其做法，首先通读题面之后看了样例分析，最后发现了一个规律：一些线段放在一个集合里造成多个联通块(也就是题目中的复杂度不为1)的情况 当且仅当 这些线段至少有2个或2个以上的 线段没有重叠部分，在这时候想到了DP，设了一个状态式子：设 $f[i][j]$ 表示当前选了 $i$ 个线段产生了 $j$ 的复杂度，最后发现推不下去了。。。然后写了个不正确的贪心加了上去
3. 9:00 – 10:30 写T3，考后知道这是一道树上LIS的模板题，但我不会QWQ算是时间很长了，然后在后面的时间里又抽出了点时间又来写，我归结了下，用了几种方法来写，
   第一种：树形DP，设 $dp[i][2]$ 表示在 $i$ 节点选不选的情况，其中 $dp[i][0]$ 表示不选，$dp[i][1]$ 表示选 ，并且推了一个伪DP式：
   $$dp[i][0]+=子树内点权值<price[i]的dp和$$
   $$dp[i][1]+=子树内点权值>price[i]的dp和$$

并且从叶子结点向父亲节点回溯，把值赋在儿子上，然后每次只需要对其儿子赋值就行了

但是很快我就证明出这是不对的：当这个节点选的时候，其儿子不大于的这个节点权值的节点根据定义不可能选，但是这个儿子的子树中大于这个节点的权值的点可以选！
如下图：

可以直观地看到，2号节点要想更新1号节点，只能用$dp[2][0]$更新，但是 3号节点的值是比1号节点大的，用3号节点更新2号节点时，是用 $dp[3][1]$ 更新 $dp[2][1]$，但是转移到了1节点，便是$dp[2][0]$。相当于1号节点最终不会统计3号节点的值！！！

这时候，我想到了一个 $O(n^2)$ 的方法去找到每个节点的子树内比他大的值，但是没有去实现，因为这时候我惊奇的发现一个节点选和不选，和其左子树和右子树选不选没有任何影响(因为权值严格大于和严格小于这个限制条件只在两点有祖先关系是才会出现)，第一时间我想到的是改进后的lca，如果两个数的lca是两个数的其中一个，那么说明有祖先关系，这时候特判加入，如果没有，就直接两个加入到最大集合中。

这时候脑子里划过了前几天学的启发式合并上去，如果可以选择，那么在根节点上加入这些数，否则直接删除(这就是正解啊QWQ)，但是由于满脑子都是lca，自然忘掉了这个方法，考后看到题解差点哭了，码了lca后仍然不知道要怎么去推，然后发现码了lca反而会让时间复杂度增大 $log(n)$（可能不对吧，但是我当时在演草纸上写的就是这样），之后就是无穷的自闭。。
考完，看到了题解
人直接傻掉。。。

4. 11:00 – 12:00
   进入了无效思考时间，然后码了T2的暴力也码炸了，T4几乎没有去读题

自己和正解的区别 + 赛后反思

T3

重点说下T3，当时在演草本上写下了用vector记录每个节点所选的节点，然后没有去实现，而且写lca的时候想到了启发式合并，然而没有去实现，题解的一种就是启发式合并 + multiset记录节点(因为其自带从小到大的排序，由于要求从大到小最多的节点个数，可以再multiset里将每个节点的权值 $\ast -1$，就能实现启发式合并倒序排序，答案就是根节点1的size大小)，所以导致了这次掉分的原因，以后在深入思考的时候，不要放过每个思路，如果证明出这个思路是错误的话，一定要懂得取舍，去试下一种思路，不能一直在想着一个思路下去，否则最后只能在追逐梦想的道路上s去 其实归根到底还是我太菜了QWQ
其余题目正在订正中…

---

前方施工，停止通行