我今天摆了一天捏。
晚上写点什么证明不是一整天捏。
P8499 [NOI2022] 挑战 NPC Ⅱ
我会树哈希吗？？
我们发现包里匹配就行了，因为他们讲根节点是一样的。所以从根节点开始匹配就是如果哈希值一样的节点，那直接匹配上不亏。如果不一样的数量很多，那一定不行。如果在 \(K\) 以内，我们可以 \(K!\) 枚举怎么匹配的，然后直接递归就行。
不过好像不知道怎么分析复杂度的，大概是 \(O(n K!)\) 的。
P8304 [CoE R4 D] 01 串
令 \(1\) 换成 \(1\)，\(0\) 换成 \(-1\)。
我们考虑正常的删除方式就是从前往后，删掉前缀和为前缀最小值的位置（因为变化量是 \(1\)，第一个前缀最小值是 \(-1\)，第二个是 \(-2\) ，删掉第一个，后面的整体加一。）然后再从后前，在新的序列上这么删一遍。
设 原来的前缀和 \(pre_i\)，总数为 \(pre_{tot}\)，后缀和为 \(suf'_{i}\)，总数为 \(suf_{tot}\)，答案就是 \(pre_{tot}+suf_{tot}\)，发现就是前缀和和后缀和的最小值的相反数。
然后我们考虑求 \(suf'_{i}\)
\(suf'_{i}=suf_i-后面被删掉的数\)
\(=suf_{i}+ \min_{j<i} pre_j -pre_{tot}\)
我们要求的是这两个的和。
然后就是求的 \(-\min _{i<j}{pre_i+suf_j}\)，就是最大子段和。
P8990 [北大集训 2021] 小明的树
树上 trick：点数-边数=联通块数。
我们可以维护点数-联通块数，最小值为 \(1\) 时是可以统计的。
然后答案就是被点亮的点-两端点都被点亮的边。这个也可以统计。
我们考虑在时间轴上去维护答案，然后对于每条边都维护在什么时候开始贡献答案，什么时候结束。当树边改变时直接修改。
P7737 [NOI2021] 庆典
\(O(nq)\) 我们考虑从起点和终点分别走，终点是反向边，走出来两个点集，点集的交集就是可能走到的点。
\(k=0\)，我们观察到缩点之后拓扑排序是一棵树，所以直接求树上点权和就行。
\(k=1\)，可以乱分类讨论。
\(k=2\)，分类讨论有点困难，考虑直接把所有用到的点（起点，终点，加边的点）拎出来建虚树，点权是原点权，边权是两点之间的点的点权。然后像 \(O(nq)\) 一样，找点和边的交集，这样就能直接做了。