大型挂分现场

预估：285—>实际：123

T1

传送门
简单观察发现答案似乎只与树的非叶子节点的奇偶性有关，于是就非常开心地水过了这题。
？
\text{\color{red}\texttt wrong answer on test 1}

forest1.in
1
2
1 2

forest1.out
villager

注意特判n=2的情况

T2

传送门
好像和奥运公交有点像？
先分别从起点按原图和终点反图Dijkstra，对于不是最短路上的边，O(1)查询，但最短路上的边和奥运公交不太一样，重新Dijkstra复杂度爆炸，由于只需将修改后的图和原图比较最短路，直接tanjan求割边就可以了。
幻想中：样例测的都对，而且样例不水，包过的。
实际上：由于我太懒，不想写两个Dijkstra，直接把Dijkstra有关的东西开了两维分别存正反图的信息，结果一个地方把两维写反了，样例过了，但只有20分。

T3

传送门
操作二的答案可以用组合数计算，但是计算的时候由于没有特判一些奇怪的负数被传入到手写的组合数函数里，于是得到了一堆RE。
正解：
相当于要在l~r的区间里放k-1个隔板，但有的地方必须放隔板，即前一个字母不小于后一个的情况，只要求出这些强制放隔板的数量即可用组合数计算。考虑操作一，发现操作区间内强制放隔板的数量基本不变只有左端为D时减一，右边为D时加一，可以用线段树维护左右端点字母及区间内强制放隔板的数量。

T4

传送门
赛事试图O(n^3)KMP写挂了
时间紧迫的情况下打了一个特殊点
然后成功爆零
赛后试图用map存字符串哈希然后MLE了
然后就没有然后了