讲解 CF1943C Tree Compass。

考虑对于树的直径长度分类讨论构造答案。

思路：

考虑往直径方向想，设直径的长度为 \(d\)。

首先可以注意到一个性质：

<li>每次操作最多只会覆盖住直径的 \(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<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#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<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

ll T,n,x,y,id,sum,cnt;

ll a[N],d[N],fa[N];

vector<ll> E[N];

void add(ll u,ll v){

E[u].push_back(v);

E[v].push_back(u);

}

void dfs(ll u,ll f){

for(auto v:E[u]){

if(v==f)

continue;

fa[v]=u;

d[v]=d[u]+1;

dfs(v,u);

}

}

void solve(){

cnt=0;

n=read();

for(int u,v,i=1;i<n;i++){

u=read(),v=read();

add(u,v);

}

fa[1]=d[1]=sum=0;

dfs(1,1);

for(int i=1;i<=n;i++){

if(d[i]>=sum){

sum=d[i];

id=i;

}

}

//cerr<<id<<'\n';

fa[id]=d[id]=sum=0;

dfs(id,id);

for(int i=1;i<=n;i++){

if(d[i]>=sum){

sum=d[i];

id=i;

}

// cerr<<d[i]<<' ';

}

// cerr<<'\n';

while(id){

a[++cnt]=id;

id=fa[id];

}

if(cnt&1ll){

x=a[(cnt+1)>>1ll];

write((cnt+1)>>1ll);

putchar('\n');

for(int i=0;i<((cnt+1)>>1ll);i++){

write(x);

putchar(' ');

write(i);

putchar('\n');

}

}

else{

x=a[cnt>>1ll],y=a[(cnt>>1ll)+1];

if(cnt&3ll){

write((cnt>>1ll)+1);

putchar('\n');

for(int i=0;i<=(cnt>>1ll);i++){

write(x);

putchar(' ');

write(i);

putchar('\n');

}

}

else{

write(cnt>>1ll);

putchar('\n');

for(int i=1;i<(cnt>>1ll);i+=2){

write(x);

putchar(' ');

write(i);

putchar('\n');

write(y);

putchar(' ');

write(i);

putchar('\n');

}

}

}

for(int i=1;i<=n;i++)

E[i].clear();

}

bool End;

int main(){

T=read();

while(T--)

solve();

cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}