A – The Cow Gathering
首先，如果没有限制的话，其实从叶子结点来抽是一定有解的，可以考虑思考一颗以最后出口为根结点的外向树来理解这个逻辑关系。现在有 \(m\) 个有向边，初步思考可以把每个点都作为最后一个节点，然后来看新的图有没有环，这样是 \(\Theta(n^2)\)。
首先，如果没有限制的话，其实从叶子结点来抽是一定有解的，可以考虑思考一颗以最后出口为根结点的外向树来理解这个逻辑关系。现在有 \(m\) 个有向边，初步思考可以把每个点都作为最后一个节点，然后来看新的图有没有环，这样是 \(\Theta(n^2)\)。
先可以想到把所有的包含的区间给去掉，然后来关注如何进行 DP。我们可以考虑设置 \(dp[i][j]\) 为前 \(i\) 个区间里删掉了 \(j\) 个区间的最优答案。正常我们做「选择 \(j\) 个区间」的问题会比较简单，然而 \(k \leq 200\) 就很麻烦。
这题细节真他妈多。
首先，看到 SCC 大小少于 \(100\) 就可以知道是 DAG DP + Tarjan + 高斯消元了，比较显然。然而实现起来非常麻烦。我们在反图上做 DP 的时候，从 queue 拿出顶点后先高斯消元一波，把环内的、SCC 之间的（也就是之前求出的 \(dp[u]\)）一起放到方程组里进行消元即可。细节看代码吧，真的呕了。
因为是从 yyb 博客上抓的题，所以知道可以用线段树做。大概想了想，初步的想法就是用线段树来维护不同高度(?)的最长子序列长度。其实这样是可以的，输入高度时就先塞到每个点的动态开点线段树里，然后就可以把儿子的进行合并。合并儿子的时候，维护至少为 \(x\) 时能得到的最长子序列长度，所以我们可以用差分的方式来做一做（当然也可以做标记永久化的区间加）：从 \(w_u\) 的位置开始加上一个一，然后把上一次的 \(1\) 给删掉。
首先发现两端并不会影响，所以可以直接做分段的线性 DP。正常思考暴力，发现每次都需要枚举颜色，非常麻烦。但是我们可以发现一个特别好的性质：每一次区间的颜色都取决于这个区间的最后一个元素，因为意识到选其他颜色时，我们大可把这个区间的右端点进行调整，使得下一个区间不会更劣。