P7565 的理论线性解法

· · 题解

其他题解已经指出了事实上本题在 j 为奇数时必定 puts 1；而在 j 为偶数时等价于找一对点 u,v，以 u 为根时 v 子树大小 \ge j，以 v 为根时 u 子树大小 \ge j，输出最大的可能 dis(u,v)，这里 dis(u,v) 代表 u \to v 简单路径上点数。

考虑取重心为根，计算出每个点 p 此时的子树大小 siz_p 以及深度 dep_p。那么 u,v 的位置关系有两种：

进一步地，我们直接放弃掉 u,v 应没有祖先后代关系的限制，认为只要 \min(siz_u,siz_v) \ge j 就可以找到一组 dis(u,v) 的解。这样做对答案没有影响，因为此时以 u 为根 v 的子树大小一定 \ge \dfrac{n}{2} 而 siz_v \le \dfrac{n}{2}，相当于是加紧了限制。

于是把所有点按照 siz 从大到小排序，维护前缀点集直径即可对每个 j 算出 \min(siz_u,siz_v) \ge j 的点对 (u,v) 中 dis(u,v) 最大的一对。

而祖先点是 heavy 的 case 显然也容易 O(n) 处理。

理论上，使用 O(n)-O(1) LCA，本题可以做到线性。

在此给出使用 O(n \log n)-O(1) LCA 的代码：

#include <bits/stdc++.h>
#define rep(i,j,k) for(int i=(j);i<=(k);i++)
#define per(i,j,k) for(int i=(j);i>=(k);i--)
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mkp make_pair
#define eb emplace_back
#define SZ(S) (int)S.size()
//#define mod 998244353
//#define mod 1000000007
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3f
using namespace std;

template <class T>
void chkmax(T &x,T y){
    if(x < y) x = y;
}

template <class T>
void chkmin(T &x,T y){
    if(x > y) x = y;
}

inline int popcnt(int x){
    return __builtin_popcount(x);
}

inline int ctz(int x){
    return __builtin_ctz(x);
}

/*ll power(ll p,int k = mod - 2){
    ll ans = 1;
    while(k){
        if(k % 2 == 1) ans = ans * p % mod;
        p = p * p % mod;
        k /= 2; 
    }
    return ans;
}*/
int n;
int result[100005];

int cnt;
int head[200005];
struct eg{
    int to,nxt;
}edge[400005];

void make(int u,int v){
    edge[++cnt].to = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
}

int siz[200005],h[200005];
void dfs1(int u,int f){
    siz[u] = 1;
    h[u] = 0;
    for(int i = head[u];i;i = edge[i].nxt){
        int v = edge[i].to;
        if(v == f) continue;
        dfs1(v,u);
        siz[u] += siz[v];
        chkmax(h[u],siz[v]);
    }
}
int dfn[200005],dep[200005],fa[200005],ST[20][200005];
void dfs2(int u,int f){
    dfn[u] = ++cnt;
    ST[0][cnt] = u;
    dep[u] = dep[f] + 1;
    fa[u] = f;
    siz[u] = 1;
    for(int i = head[u];i;i = edge[i].nxt){
        int v = edge[i].to;
        if(v == f) continue;
        dfs2(v,u);
        siz[u] += siz[v];
    }
}
inline int cmp(int x,int y){
    if(dep[x] < dep[y]) return x;
    return y;
}

inline int qry(int l,int r){
    int x = __lg(r - l + 1);
    return cmp(ST[x][l],ST[x][r - (1 << x) + 1]);
}

inline int LCA(int u,int v){
    if(u == v) return u;
    u = dfn[u];v = dfn[v];
    if(u > v) swap(u,v);
    return fa[qry(u + 1,v)];
}

inline int getdis(int u,int v){
    return dep[u] + dep[v] - 2 * dep[LCA(u,v)];
}
int ord[200005];
bool cmp2(int x,int y){
    return siz[x] > siz[y];
}

int main(){
//  freopen("test.in","r",stdin);
//  freopen("test.out","w",stdout);
    scanf("%d",&n);
    rep(i,1,n - 1){
        int u,v;
        scanf("%d%d",&u,&v);
        make(u,v);make(v,u);
    }
    dfs1(1,0);
    int rt = -1;
    rep(u,1,n) if(max(h[u],n - siz[u]) <= n / 2) rt = u;
    cnt = 0;
    dfs2(rt,0);
    rep(i,1,17){
        rep(j,1,n){
            if(j + (1 << i) - 1 > n) break;
            ST[i][j] = cmp(ST[i - 1][j],ST[i - 1][j + (1 << (i - 1))]); 
        }
    }
    rep(i,1,n) ord[i] = i;
    sort(ord + 1,ord + n + 1,cmp2);

    int pu = 0,pv = 0,pw = 0,t1,t2;
    rep(_i,1,n){
        int u = ord[_i];
        if(u == rt) continue;

        if(!pu){
            pu = pv = u;
            continue;
        }
        t1 = getdis(u,pu);t2 = getdis(u,pv);
        if(t1 >= max(t2,pw)){
            pw = t1;
            pv = u;
        }else if(t2 >= max(t1,pw)){
            pw = t2;
            pu = u;
        }
        chkmax(result[siz[u]],pw + 1);
    }
    rep(u,1,n) if(u != rt) chkmax(result[siz[u]],dep[u]);
    result[n / 2 + 1] = 1;
    per(i,n / 2,1) chkmax(result[i],result[i + 1]);
    rep(i,1,n){
        if(i % 2) printf("1\n");
        else printf("%d\n",result[i / 2]);
    }
    return 0;
}