感觉，题目挺好的，非常适合练习。auto写函数真好用，遍地拉屎。
T1
题意
给定 \(n\le 10^5\) 个点的树，每个节点被感染了1或没被感染0，一天后被感染的点会把其周围没被感染的点感染，给定最终状态，问 \(Q\le 20\) 次询问，每次询问给定一个天数 \(0\le k\le n\) ，问在开始时最少有几只牛被感染了，或判定无解。
题解
考虑全都是1的时候怎么做，直接把所有点按深度排序拿出来从大到小贪心选感染点就好，显然不劣。
考虑有了0的时候怎么做，0的限制实际上是把某些1给ban掉了，不能作为初始的感染的点，考虑还是用相同的思路，将所有被感染点按深度排序，从大到小考虑，但是选取的感染点变为能够感染到该点且与该点lca最高的那个点，这样子选是不劣的，因为lca越高那个感染点感染的其他额外点就越多。这部分可以用一次bfs处理出所有点子树内没有被ban的最近感染点是哪个快速求出。
可以证明每次选取的时候暴力跳父亲复杂度不会劣化，考虑往上跳了 \(k\) 步，那么显然被选取的点到该点之间有 \(k\) 个感染点被“处理”了，那么最多会跳 \(n/k\) 次就能"处理"完所有点，跳父亲的总次数为 \(n\) 。这部分的复杂度瓶颈为排序。
但是为了实现这个做法，我们需要有一种方法动态添加感染点，判断某一点是否已经被已选感染点覆盖，即为求任意点到动态点集的最近距离。考虑建点分树，每一个节点存这个点的点分区域中离它最近的感染点距离，那么配合 \(O(1)lca\) 就能做到插入查询 \(O(depth)=O(\log n)\) 的复杂度。这部分复杂度为 \(O(n\log n)\) 。
综上，总复杂度 \(O(n\log n)\) 。
T2
题意
给定一个 \(n\le 2\times 10^5\) 个点 \(m\le 4\times 10^5\) 条边的联通无向图，对每个点 \(i=1\to n\) 求出如下过程得出的哈希值：
- 初始集合 \(\{S\}=\{i\}\) ，哈希值 \(h=0\)
- while \(|S|<n\)
- 找出邻居边中标号最小的边 \(e\)
- 将 \(e\) 的终点加入 \(S\)
- \(h\gets 10h+e\)
- 输出 \(h\bmod 10^9+7\)
题解
显然最后的边集是固定的，为图的最小生成树上的边，考虑建Kruskal重构树，有个dp是，令 \(f_{x,y}\) 表示在Kruskal重构树上 \(x\) 点子树的叶子中以叶子 \(y\) 开始的该子树内的哈希值，这个东西显然是可以合并的，然后我们直接往上套个树上dp线段树合并就好，总复杂度 \(O(n\log n)\) 。
T3
题意
有两个车站 \(A\) 和 \(B\) ，有 \(n\le 5000\) 列火车在两个车站中行使，每个火车从 \(A/B\) 站以最早 \(t_i\le 10^{12}\) 时刻出发，经过 \(T\le 10^{12}\) 时间后到达，不能有两列火车同时往相反方向行使，但是可以有任意多列火车同时往相同方向行驶。记 \(a_i\) 表示第 \(i\) 列火车出发的时间，求一个满足条件的最优调度使得 \(\sum a_i-t_i\) 最小。
题解
赛时不会，只会 \(O(n^2\cdot玄学)\) 乱搞。
直接 \(f_{i,j,0/1}\) 表示已经处理完从 \(A\) 出发的第 \(i\) 列车与从 \(B\) 出发的第 \(j\) 列车，上一列车在 \(A/B\) 站出发时的所有可能的最后一列车出发时间 \(ti\) 与最小消耗 \(cost\) ，显然若 \(ti<ti'\land cost<cost'\) 则 \((ti',cost')\) 无用，做了这个优化后暴力转移即可拿到75pts，他性价比真的超高的好不好。
Codes
见仓库training\23fall\99usacoDecPt。