模拟赛

T1

坏了怎么T1就不会了
树形DP，二次扫描（换根）。
第一次dfs时转移很好想，难在第二次dfs（换根）。
题解是对儿子节点表RMQ+二分，好像有点道理。

T2

树上倍增板子。
约等于把st表搬到树上。

T3

好久没打过这么纯粹的暴搜了。
我使用手花费了整整300000ms生成了这个程序。
n=7，m=7的情况都跑不过，居然还有30分
正解其实是网络流。
对于每一行，每一列都单开一个节点，从源点向每行的节点建一条流量为2，费用为0的边；从每列的节点向汇点建一条流量为2，费用为0的边。表示每行，每列至多选两个节点。然后从每行的节点向从每列的节点建一条流量为1，费用为-a[i][j]的边，表示每个格子只能选一次，选的费用为-a[i][j]，为什么要取反？因为我们跑的是最小费用最大流，最后最小费用取反回来就好了。（其实改spfa也是可以的）
然后WA了
发现我们跑的是最大流，但最优解不一定是最大流，及每行每列不一定恰好选两个，于是从每行的节点向从每列的节点多建一条流量为2，费用为0的边，在保证最大流的情况下费用最小。（相当于给选的格子不满2个的行/列多一个免费的通道保证流满）

T4

前几天的莫反发力blog（\LaTeX可能炸飞了，建议配合LaTeX公式编辑器食用）
这题基本上就是莫反的经典套路，线性筛筛到根号n再加数论分块就过了。