思路：
考虑往直径方向想，设直径的长度为 \(d\)。
首先可以留意到一个性质：
- 每次操作最多只会覆盖住直径的 \(2\) 个点，那么答案的下界即为 \(\lceil \frac{d}{2} \rceil\)。
分类讨论一下。
若 \(d\) 为奇数，则存在唯一的一个直径中心 \(u\)：
- 那么答案为 \((u,0),(u,1),\cdots,(u,\lceil \frac{d-1}{2} \rceil)\)。
- 最优次数是 \(\lceil \frac{d}{2} \rceil\) 次。
若 \(d\) 为偶数，则存在两个直径中心 \(u,v\)：
- 若 \(d \bmod 4 = 0\) 时：
- 那么答案为 \((u,1),(v,1),(u,3),(v,3),\cdots,(u,\frac{d}{2}-1),(v,\frac{d}{2}-1)\)。
- 最优次数是 \(\frac{d}{2}\)。
- 如许是两者是完全错开的。
- 若 \(d \bmod 4 = 2\) 时：
- 那么答案为 \((u,0),(u,1),\cdots,(u,\frac{2}{d})\)。
- 最优次数是 \(\frac{d}{2}+1\)。
这里证明一下为什么当 \(d \bmod 4 = 0\) 时不能取到答案的下界。
留意到若 \(x,y\) 能被同时取到当且仅当 \(\operatorname{dis}(x,y)\) 为偶数。
设 \(L\) 为直径的一个端点，那么 \(\operatorname{dis}(L,x)+\operatorname{dis}(L,y)\) 的奇偶性等价于 \(2*(奇数/偶数)+偶数=偶数\)。
由于 \(d \bmod 4 = 2\)，所以 \(\sum \operatorname{dis}(L,i) = \frac{d \times (d-1)}{2} \bmod 4 = 1\)，则这个和式一定不是偶数，故无法到达下界。
时间复杂度为 \(O(TN)\)。
完备代码：
[code]#include#define Add(x,y) (x+y>=mod)?(x+y-mod) x+y)#define lowbit(x) x&(-x)#define pi pair#define pii pair#define iip pair#define ppii pair#define fi first#define se second#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x#define Full(a) memset(a,0,sizeof(a))#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);using namespace std;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;const ll N=2e3+10;inline ll read(){ ll x=0,f=1; char c=getchar(); while(c'9'){ if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c |
