max(|x1-x2|,|y1-y2|)
=0.5*(|(x1-x2)+(y1-y2)|+|(x1-x2)-(y1-y2)|)
=|(x1+y1)/2-(x2+y2)/2|+|(x1-y1)/2-(x2-y2)/2|

啊喂 你们膜我这个咸鱼干什么(╯‵□′)╯︵┻━┻ 感受到了深深的嘲讽啊QAQ

答案是n^2+0e-233

我表示不能理解，明明树剖用堆线段树维护(id=299174)是O(nlon^3)而整体二分(id=376787)是O(nlogn^2)的，为什么反而整体二分慢？

高考难度的数学题。
woc一定要考虑n <= m的情况口牙不然会爆零的QaQ泪奔

吐槽一下：为什么这样一道模板题大家都要去交暴力？？（You must be kidding?）

回复 @riteme :
虽说ST可以做到O(nlongn)预处理，O(1)查lca，但是你整体二分肯定要配合树状数组或者线段树之类的吧，那样整体二分的复杂度就是O(nlongn^2)了，你的整体复杂度还是O(nlongn^2)的，而且你用的是树剖求lca，每次是O(logn)的，不过因为是离线，所以求出所有lca的复杂度还是O(nlongn)的。
这道题应该没有时间渐进复杂度低于O(nlongn^2)的做法了，（还是我太弱不会？）如果有，还请大神讲解。

回复 @小一米 :
e，身为常数狗(永远的大常数)表示几乎不敢用memset,一般都是用时间戳，不能用时间戳的就手动清零（比如我的费用流）

回复 @_Itachi :
作为出题人确实很难做到考虑全所有的错误做法，表示体谅
不过个人认为，既然作为线下练习，而不是比赛，更应该是让大家体会到题目性质与解题思路，而不是通过本不能AC的做法AC题目，这既不利于锻炼选手的思维能力和代码能力，也是对出题人的不尊重。
之前的评论仅代表个人建议，希望大家还是要认真思考，不要投机取巧

动态规划写不出来过来写道线段树裸题放松放松................

那就是瞭望塔必须建在山上咯= =。
所以说答案的坐标也必须大于等于0么……
“可以”表现的不应该是“可以”也可以"不可以"么
这是所谓的表面民主实际独裁么
————————————————
事实上貌似答案都必须要在山尖的坐标之间么
还是我太弱了……

到现在才知道错排公式是什么的辣鸡

回复 @小一米 :
en，你的诚实非常可贵
删提交好像是不可以的，至于数据。。你总不能让造数据的人考虑到所有错误写法怎么写然后专门写一个错误写法然后通过对拍得到数据吧。。（出题人怎么知道你怎么错的），所以要体谅一下出题人，尤其是当出题人是一个神犇的时候@Mike

跑得好慢啊

矩阵单位元是 $I_{i,j} = i == j ? 0 : \infty$

这第一组数据…m和说好的不一样啊！！！
我修了。

@FoolMike
题目挺好，但数据略水了，我写了个没清vis数组的匈牙利都A了
求添加这组数据把提交376453卡掉，或者把这次提交删掉
1
1 4 0
1
1 3 2 4

1A!

手抖发两层