CF1039D You Are Given a Tree

有一棵 n 个节点的树。

其中一个简单路径的集合被称为 k 合法当且仅当：

树的每个节点至多属于其中一条路径，且每条路径恰好包含 k 个点。

对于 k\in [1,n]，求出 k 合法路径集合的最多路径数 即：设 k 合法路径集合为 S，求最大的 |S|。

n \leq 10^5

解题思路：

分治（整体二分）。

首先可以观察一下这个问题的一些性质，很显然，我们考虑对于这个合法路径的答案取值其实最多只有 \sqrt{n} 种并且具有单调性，这个的证明非常显然，类似数论分块的证明。

接下来想下暴力怎么做，我们对于单独的一个 k 来考虑。首先，每个点最多只可能在一条链中，这给我们贪心提供了一个正确性的保证。对于一个点，如果当前点有一条拐弯的最长链长度大于等于 k ，我们就贪心划分成一条答案所需要的链。

image-20220310144247767

如图，红色圈起来的就是一条拐弯的最长链。

否则，我们这个节点保存一个不拐弯的最长链长度 f_x 以供接下来使用。

image-20220310144401233

如图，红色圈起来的就是一条不拐弯的最长链。

接下来考虑分治，有点类似整体二分（其实我个人是按整体二分来理解的，但是被机房学长纠正说不是整体二分），在分治过程中，我们对于 k \in [L,R] ，答案属于 [l,r] 的询问进行分治。每次选取 mid = \lfloor \frac{L+R}{2}\rfloor 进行 dfs，得出的答案记为 tmp，那么对于 k \in [L,mid] 来说，答案属于 [l,tmp]，对于 k \in [mid + 1,R] 来说，答案属于 [tmp,r] ，当 l = r 时，我们就将 [L,R] 的答案全部赋为 l。

这样，我们的时间复杂度就做到了 \mathcal{O}(n \sqrt{n} \log n)，这个复杂度感性理解即可（因为我也不会证是机房学长告诉我的orz，如果有dalao会证也可以在评论区，目前的想法是分治树有 \log n 层，答案有 \sqrt{n} 个，分治的过程就是 n \log n \times \sqrt{n} ）

注意这个东西常数非常大……你需要一些卡常技巧，这里提供一个亲测能过的。首先把原图存下来，然后 dfs 一遍，确定每个点的父子关系，然后只保存从父亲到儿子的边，能快一半以上，具体可以看代码。

代码：

const int N = 1e5 + 10;

int n,ans[N],f[N],cnt;
vector <int> G[N];
int hd[N],nxt[N<<1],to[N<<1],tot;

inline void addedge(int u,int v) {
    to[++tot] = v;nxt[tot] = hd[u];hd[u] = tot;
}

void dfs(int x,int fa,int k) {
    f[x] = 0;
    int maxx = 0,secmax = 0;
    for (int i = hd[x];i;i = nxt[i]) {
        int y= to[i];
        if (y != fa) {
            dfs(y,x,k);
            if (f[y] > maxx) {
                secmax = maxx;
                maxx = f[y];
            } else {
                secmax = max(secmax,f[y]);
            }
        }
    }
    if (maxx + secmax + 1 >= k) ++cnt,f[x] = 0;
    else f[x] = maxx + 1;
}

void solve(int l,int r,int L,int R) {
    if (l > r || L > R) return ;
    if (L == R) {
        for (int i = l;i <= r;++i) {
            ans[i] = L;
        }//sqrtn
        return ;
    }
    int mid = (l + r) >> 1;
    cnt = 0;
    dfs(1,0,mid);
    ans[mid] = cnt;
    solve(l,mid - 1,cnt,R);//越短越多.
    solve(mid + 1,r,L,cnt);
}

void prework(int x,int fa) {
    for (auto y : G[x]) {
        if (y != fa) {
            addedge(x,y);
            prework(y,x);
        }
    }
}

signed main() {
    read(n);
    for (int i = 1;i < n;++i) {
        int x,y;read(x);read(y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    prework(1,0);
    solve(1,n,0,n);
    for (int i = 1;i <= n;++i) writeln(ans[i]);
}