T1
简单的最短路
到终点时不用等红灯，不然会挂40pt
T2
记 \(f(i,j)\) 表示跳到 \((i,j)\) 最少使用的体力。 那么转移就是枚举上一个位置然后加上曼哈顿距离求最小值。
考虑优化，我们注意到如果转移都在左上的话坐标正负的贡献是固定的, 所以可以使用数据结构维护。先按照一维扫描线，另一维可以使用线段树或者树状数组维护前缀/后缀最小值。
对于四个象限分别计算一次即可。
时间复杂度 \(O(n^2 \log n)\)
T3
树上莫队
这是欧拉序
代码：
出栈的 \(u\) 和入栈的 \(v\) 中间去除重复两次的点加上 \(\operatorname{lca} (u,v)\) 就是 \(u\) 到 \(v\) 路径上节点集合（\(u,v\) 无祖先关系）
就变成了序列上莫队
已经出现过 \(v\) ：\(\operatorname{add} \rightarrow \operatorname{remove}\)
T4
首先我们注意到任意两个秘密据点的路径中点是重要的，为了让这个中点不出现在边上一个常见的技巧就是在每条边上新建一个点。
然后我们先考虑在扩建了树之后每个 \(M\) 值的改变，原先树上的点 \(M\) 值会变成两倍。 考虑原图中的边 \((u,v)\) 中间新建的点 \(x\) 那么首先必须有 \(|M_u-M_v|\le 2\) 如果 \(|M_u-M_v|=2\) 那么 \(M_x=(M_u+M_v)/2\). 如果 \(M_u=M_v\) 这时候这条边中点 \(x\) 一定是某两个秘密据点的中点，也就是说这种边最多只有3个。这些 \(M_x=M_u \pm 1\), 可以直接暴力枚举。
接着我们考虑 \(u_1,u_2,u_3\) 的位置关系，它们三个点一定有一个中心 \(u\), 不妨记 \(D_i=d(u,u_i)\), 并且假设 \(D_1\le D_2\le D_3\).
我们按照 \(M\) 值从大到小给边定向, 如果一个点没有出度则称为汇点。 通过观察: 当 \(D_1<D_2\le D_3\) 的时候有且只有两个汇点。 当 \(D_1=D_2\le D_3\) 的时候有且只有一个汇点。计算出汇点的个数分类讨论。
一个汇点的情况: 此时汇点一定是三个点的中心, 设汇点为 \(r\), 且 \(D_1=D_2=M_r,D_3>M_r\) 我们只需要通过简单的背包的\(dp\) 计数即可。
两个汇点的情况: 设两个汇点为 \(r_1,r_2\). 我们会发现 \(u_1,u_2,u_3\) 的点到 \(r_1,r_2\) 的距离已经全部确定了，只要分别独立的满足这些距离, 将方案数相乘即可，两次 dfs 即可。
最终时间复杂度 \(O(n)\)
CF1654E
KD-Tree
P5471
