做着玩的。因为倒着做的，所以倒着写。
F
10.1 tyy讲过套路。然后这场在他讲完之后。我愿称之为押题大师。不幸的是这场没打，不然上大分了。
先树上差分，然后对于每一个节点记一个他下面第 \(0\le i\le 20\) 层儿子加的标记，然后查询的时候直接向上跳最多 20 个父亲加起来即可。由于树上差分，要用树状数组维护前缀和计算子树内的和（这个维护dfs序即可）。然后问题就在于如何维护到路径距离是 \(d\) 的点。乍一看是点分治，但是tyy讲了这个套路，对于 \(u,v\) 路径上除了 \(LCA\) 的所有点，将其对应第 \(d\) 层儿子的标记修改，对于 \(LCA\) 开始往上的 \(d\) 层（他自己是第一层），第 \(i\) 层将其 \(d-i+1,d-i\) 这两层的标记修改（最上面一层只剩0）。
E
由于刚刚做完的 div.1 D 也是个最短路，故此题也不难发现最短路。
直接建立超级源汇点，然后连到第一列和最后一列（所有边权都是终点是否已经是仙人掌，超级汇点除外），中间只向左上右下左下右上（不要漏了左下右下，他给定的已经填的位置可能使这样变优）连边，然后跑最短路记录转移即可。注意当边的起点或者终点有一个周围有仙人掌就不能连这条边。
标签：Educational,左下,标记,短路,CF,然后,右下,138 From： https://www.cnblogs.com/infinities/p/16829866.html