A
平面上给出若干个点，求两两点之间曼哈顿距离比欧几里得距离的最大与最小值。
\(n\le 10^6\)。
不难发现最小值求的就是线段斜率最接近 \(0\) 的线段，最大值就把每个点绕源点旋转 \(45\) 度即可。
这个东西考虑按照 \(y\) 坐标排序，\(y\) 相同的按照 \(x\) 排序，有贡献的只有相邻点。
因为考虑一个三角形，其最高的点连向最低的点的斜率，一定不都比令两条边的斜率大。
可以说运用到了三角形的性质吧。
B
给定一棵树，边权为 \(1\)，你要对于每个 \(k\) 求大小为 \(m\) 点集的个数，使得其两两距离最大值 \(\le 2k\)。
\(n\le 5000\)。
首先这个 \(2k\) 非常的蹊跷，我们可以联想到直径中点。
那么考虑枚举直径中点，对于每个 \(k\)，选距离直径中点不超过 \(k\) 的点 \(m\) 个即可。
但是这样会算重复，一个方案不一定只会被一个直径中点算。
换句话说，我们枚举的“直径中点”不一定是点集直径的中点，而是只是满足距离不超过 \(k\) 而已。
注意到，一个方案被算到的点构成一个连通块，这启示我们用点边容斥，将贡献抵消。
点的贡献直接枚举中点即可，边的贡献呢就是两端点都满足条件的方案数。
C
给树染色，有 \(m\) 种颜色，询问同色点对距离的最小值 \(\in [l,r]\) 的答案。\(m\le 10^9,n\le 10^5\)。
首先将答案差分变为 \(\le r\) 的减去 \(\le l-1\) 的答案，设当前求的是 \(\le x\)。
那么可以转化为同色点对距离 \(>x\)，也就是一条距离 \(=x\) 的路径上没有颜色相同的点。
先考虑链怎么做，我们从上往下填，那么前 \(x-1\) 个点颜色肯定都不同，那么贡献是 \(m-x+1\) 的积。
考虑树怎么做，我们也考虑从深度低的填到高的，然后算每个点的贡献。
注意到，从深度低到高，距离当前点 \(\le x\) 的所有点，他们之间的距离也肯定 \(\le x\)。
原因是，我们所有点的计算都是同步浅到深，设当前到 \(y\)。
所以若 \(y\to O\to u\)，\(y\to O\to v\) 导致 \(dis_{u,v}>dis_{u,y}\) 的，那么 \(u,v\) 肯定比 \(y\) 深，这是不存在的。
关于计算树上一个点到其他点距离不超过 \(k\) 的点数量，考虑用点分树。
这个题可以类比其他染色/分组的方案数计算，就是要钦定顺序再逐一加入，每个点贡献独立。
要求每个新加入的点都能简单计算可以影响它的点的颜色的不同种类个数。类比 CF1111E，ARC148E
介绍点分树：“点分树就是点分治过程中每层重心连成的树，所以深度是 \(O(\log n)\)。
计算 \(x\) 距离不超过 \(k\) 的点，那么枚举其跨越了点分树上的哪几个父亲，即计算分治每一层的答案。
然后点分树上每个点维护一棵线段树代表当前子树距离当前点距离每种有多少个即可。 ”