T2 是个很典的题，先 2^k 枚举选哪些乡镇（可能是叫这个名字吧），然后把边拿出来跑最小生成树是 O(2^k (m+nk) \log (m+nk)) 的，但显然只有最小生成树上的边有用，于是去掉其他边，变为 O(2^k nk \log nk + m \log m)，发现边可以先提前排序，再顺次拿出来（这是很多分块题的套路），然后就做完了，O(2^k nk + m \log m)。
T3 看到是字符串，心态直接要炸了。仔细想想发现可以分为三段，我对 s 的前两段存下来，然后分出 t 的三段，枚举 t 的中间段的前面一段，然后在对应的 s 中枚举，check 一下第三段是否存在。然后复杂度是 O(len \log n + nq) 的，但是把大样例艹过去了。