T1
送分题，我 10 分钟以内就打完了，我写的是 \(nm\log\) 的，但是可以做到 \(nm\)。
T2
观察样例发现判断两个集合相不相同就可以判有无解。
然后你每个点往目标点连边相当于跑欧拉回路。
显然你点集合相同所以入度等于出度那么一定存在欧拉回路。
最后判一下不用改和可以少改一次的情况。
T3
就是你会发现点对间的贡献只有 1 和 1/2。
那么你就上 ds 维护 1，换根维护 1/2。
那么就可以写了，但是这个比较难写，我考场上没写完。
T4
你会发现你会 \(O(2^{n^2})\)。
然后这个能过 n=9。
高级。