T1
因为不能有中间插入的颜色，所以我们可以把所有操作改为在当前已操作区间的左右两侧扩展。
于是用栈实现即可。
T2
Fun Fact：两个错误的暴力得到了一个正确的算法。
首先，我们用暴力算法打一下表，发现每一次选取的集合都是下一次的子集。于是我们只需要考虑怎么找到当前改变所属集合后权值增加得最少的的点即可。
然后我们考虑一个点由 \(B\) 集合转移到 \(A\) 集合会对答案的贡献是多少：就是其深度加上与目前在 \(A\) 中的点的贡献减去目前在 \(B\) 中的造成贡献，贡献是包括它统计别人和别人统计它两部分的。然后我们发现一个很有趣的事实：一个点移动后，除了与它有祖孙关系的且权值相同的点外，其他点的贡献都会加一。
于是我们只需要动态维护这东西即可。具体的，我们按颜色为第一关键字，dfn 序为第二关键字进行排序，然后树剖维护时二分查询操作区间即可。
时间复杂度为 \(O(n\log ^2 n)\)。
T3
先考虑在 DAG 上怎么做。
我们定义 \(f_u\) 表示在 \(u\) 点时的最小提示次数。特别地，如果 \(u\) 点无法到达 \(t\) 点，我们认为 \(f_u=+\infty\)。
我们认为在处理 \(u\) 点时 \(u\) 的每一个后继都已经被处理了。此时我们分类讨论：
-
如果不进行提示，那么会往最坏情况走：即 \(f_u \leftarrow \max \limits_vf_v\);
-
如果进行提示，那么会往最优情况走：即 \(f_u \rightarrow \min \limits_vf_v+1\)
综上就是：\(f_u \leftarrow \min(\min \limits_vf_v+1,\max \limits_vf_v)\)。
那么再考虑原问题。
因为 dp 过程具有后效性，且求的值是最小值，所以我们考虑迭代。具体地，我们从小到大枚举 \(x\)，然后只判断未确定值的状态能否取到 \(x\)。
那么我们考虑一个点 \(u\)，如果有 \(f_u=x\)，那么需要满足一下条件之一：
-
如果任意后继都已确定；
-
如果存在后继未确定，且存在 \(f_v<x\)；
我们可以通过这样直接操作：维护每一个点未被确定后继个数 \(c_u\)，当一个点被确定时，更新其前驱的 \(c\) 值，如果存在前驱的 \(c\) 值为 \(0\)，那么将其加入当前更新队列；否则将其加入下一次的更新队列。时间复杂度为 \(O(n(n+m))\)。
T4
神秘改题人。
首先，关于最短路相关问题，一半是要往最短路树上靠的。
考虑最坏情况下的断边，一定是断最短路树上的边。那么我们记 \(f_i\) 表示点 \(i\) 到 \(1\) 号点的最短距离，分类讨论：
-
若断 \(u\) 与其父亲之间的边，那么 \(f_u\) 就是去掉该边后的最短路长度，记为 \(dis_i\)；
-
若断 \(u\) 和 \(1\) 之间的其他边，那么 \(f_u\) 就是 \(u\) 枚举其下一步走到哪个点，转移为 \(f_u=\min \limits_v[(u,v) \in E](f_v+w_{(u,v)})\)
这样直接做时间复杂度为 \(O(nm\log m)\)，瓶颈在计算 \(dis_u\)。
