来补题了昂。
D1T1 轻重边
对于原树进行重链剖分，使用一颗线段树维护每一条重边是否时“重边”，然后对于轻边，在父亲出维护最后一次通过 \(1\) 操作清空“重边”的时刻，在查询时只会遇到 \(O(\log n)\) 条轻边，直接查询这个轻边时“重边”的时刻是否晚于父亲清空的时刻即可。
D1T2 路径交点
LGV 引理板子题，记 \(e_{u,v}\) 表示从 \(u\) 走到 \(v\) 的方案数，则最终答案就是：
的值，直接求解即可。
D1T3 庆典
首先对图进行缩点，得到一张 DAG，我们原题需要维护的东西与连通性有关，所以考虑在不影响连通性的情况下改变这个图的结构。
考虑题设给出的性质：如果 \(x\to z\) 且 \(y\to z\)，则有 \(x\to y\) 或 \(y\to x\)。
不妨设为 \(x\to y\)，则删去边 \(x\to z\) 不影响图的连通性，由此，我们可以不断调整结构将原图变成一棵外向树。
现在考虑加入 \(k\) 条边后的问题，实际上被影响到的点只有那 \(2k+2\) 的点，对于这些点建立虚树，对正反边各跑一次管搜即可。
D2T1 量子通信
由于数据随机生成，所以可以认为单词是均匀分布的，由于被影响的位数 \(\le 15\)，所以将所有的单词 \(16\) 位一段，则至少有一段适合某个单词完全相同的。所以只需要查这些单词即可，考虑单次需要查询的个数：\(\dfrac{n}{2^{16}}\times 16=\dfrac{n}{4096}\) 个，使用 bitset 优化查询，时间复杂度为 \(\dfrac{nm}{16w}\)，可以通过。
D2T2 密码箱
通过推式子，发现 E 操作完全等价于维护后者，即
先给数列的最后一项减 \(1\)，接着在数列尾再加两项，两项的值都是 \(1\)。
则目前所有的操作均为对最后一项进行修改，发现可以实时维护后缀操作得到的分数 \(\dfrac{A}{B}\) 的 \(A\) 和 \(B\) 分别是多少。
具体的，这两个矩阵为 \(\begin{bmatrix}1&1\\0&1\end{bmatrix}\) 和 \(\begin{bmatrix}2&-1\\1&0\end{bmatrix}\)。
使用支持区间翻转的平衡树维护即可，时间复杂度 \(O(n\log n)\)。
D2T3 机器人游戏
考虑容斥，记 \(cnt(S)\) 为选择 \(S\) 这些位置为起点合法的纸条方案数，则最终答案为 \(\sum\limits_{S}(-1)^{|S|+1}cnt(S)\)。
对于一个机器人的操作，均可以被描述成四种：\(0\)，\(1\)，\(x\) 和 \(1-x\)，分别表示修改成 \(0\)，修改成 \(1\)，不改变和反转。
我们钦定 \(S\) 中最大的位置为 \(p\)，我们对于这个 \(p\) 的位置进行 DP，则 所有机器人的操作长度应 \(\le n-p+1\)，同时最多只有前 \(p\) 位可能被操作，所以实际上会影响到当前位的只有 \(\min(n-p+1,p)\le \dfrac{n}{2}\) 位，考虑设计状态 \(f_{i,S}\) 表示处理到了第 \(i\) 位，前若干位选择状态为 \(S\) 的带符号和。
发现如果同时出现 \(0\) 和 \(1\)，或者同时出现 \(x\) 和 \(1-x\) 这两对相互矛盾的，则只能选择空到空，有 \(1\) 种方案。
如果 \(0\)，\(1\) 与 \(x\)，\(1-x\) 各出现一个，如果不为空，则可能的状态就确定了，有 \(2\) 种方案。
其他情况下，每一个输入会对应唯一的输出，有 \(3\) 种方案。
只需要对所有满足操作长度 \(\le n-p+1\) 的统计出分别有多少个满足上述条件的方案即可，使用 bitset 优化，时间复杂度为 \(O(\dfrac{nm2^{\frac{n}{2}}}{w})\)。