T1 保险丝(fuse)
题面怎么这么长。
首先有 \(dist(S1,S2)=\min_{u\in S1} dist(u,S2)\)，因此预处理出每个点 \(u\) 的 \(c_u=dist(u,S2)\) 后从根往下做一次前缀 \(min\) 得到 \(d_u\)，条件转化为 \(dep_v-dep_u \le d_v\)。且因为是前缀 \(min\)，\(d\) 的值从根往下是单调不增的。
而 \(dep_v\) 从根往下是单调增的，\(dep_u\) 为常数，则 \(dep_v-dep_u-d_v\) 也是单调增的，符合条件的点是一个与 \(u\) 相连的连通块。若固定 \(v\)，也有满足条件的 \(u\) 是 \(path(1,v)\) 的一段后缀。
维护出对于每个 \(v\) ，深度最大的祖先 \(s_v\) 使得 \(v \notin U_{s_v}\) ，从上往下扫一遍，用树剖之类的东西维护一下那个 \(\prod\) 就好了吧。气笑了逆元怎么还不是质数。哦不对貌似不用回退，因为修改的东西不会影响到后面的答案。
哦然后观察一下，没有二度点时 \(\sum c\) 是 \(O(n)\) 的，所以把二度点缩起来直接写就是 \(O(n\log n)\) 的。
T2 矩阵(matrix)
key observation: 对于 “从多个中只能有一个” 的限制，可以转化为匹配
喜欢出 \(ad-hoc\) 的出题人们你们好啊。
把矩阵视作一个网格，每个格子有权值。
考虑对于 \(i+j\) 为奇数的格子，将其左上格点与右下格点连边权为 \(A_{i,j}\) 的边。对于 \(i+j\) 为偶数的格子，将其左下格点与右上格点连边权为 \(A_{i,j}\) 的边。
可以注意到，对于任意两个不能同时被选的格子，代表其的边一定存在一个公共格点。
所以现在问题相当于选一些边，使得选择的边的端点不重复，最大化选择的边的边权最大值。
发现建出来的图也是一个网格图，所以也是是一个二分图，把偶数行点放入左部点，奇数行点放入右部点。直接费用流跑二分图最大匹配即可。
复杂度 \(O((nm)^3)\)，常数极小。
做法二：先把所有限制条件画出来，形如：\((n-1)*(m-1)\) 大小的网格，其中在 \(i+j\) 为奇数的格子上有形如 \(X\) 型的限制，也就是周围四个点只能选一个。
发现只需要把网格扩大至 \((n+1)*(m+1)\)，并把边界上补上一些斜线限制，则只需要保留斜线的限制（X形代表的四个点只能选一个）即可。于是把 \(X\) 形的中心的点看成点（即所有满足 \(i+j\) 为奇数的格子重心），两个相邻的中心点连一条边，则限制为每个点相邻的边只能选一条。因此令边权为这条边经过的格点的权值，则合法矩阵就是一组匹配。容易发现这是一个网格图，费用流即可。