CF1943C Tree Compass

思路：

考虑往直径方向想，设直径的长度为 \(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)\)。

完整代码：

#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;
}

原文链接：CF1943C Tree Compass