「CF1039D」You Are Given a Tree

· · 个人记录

根号分治，最近遇到挺多的。

\texttt {Solution}

考虑对于一个固定的 k ，如何求答案。

可以贪心，如果子树中过根的最长链的长度 \geq k ，那么就把取这条链；否则就把以根为端点的最长链传给父亲。

如果已知 s = | S | ，是否能找出一个最大的 k 呢？这个也不难，可以二分解决。

如果暴力跑 k 或暴力跑 s 肯定是不行的，但是我们知道每个 k 对应的 s ，或者每个 s 对应的 k 都满足 k \times s \leq n 。

所以容易想到根号分治，不妨设一个临界值 B ，当 k \leq B 时暴力跑 k ， k > B 时 s < \dfrac n B 暴力跑 s 。

因为跑 $ s $ 时有二分，取 $ B = \sqrt {n \log_2 n} $ 可以平衡复杂度为 $ \mathcal O (n \sqrt {n \log_2 n}) $。 这道题卡常，我们还需要把遍历树的方式改成递推，按照 `dfn` 序倒着跑，跑到当前点时这个点的儿子一定跑过，和递归一样算贡献即可。 主要是递归常数太大，我们需要用它的次数较多，所以会卡常。 ### $ \texttt {Code} 
#include <cstdio>
#include <vector>

#define LL long long
#define uLL unsigned LL

namespace Read {
    static const int buf_size = 1 << 12;
    static const bool use_fread = true;

    static unsigned char buf[buf_size];
    static int buf_len, buf_pos;

    bool isEOF() {
        if (buf_pos == buf_len) {
            buf_pos = 0; buf_len = fread(buf, 1, buf_size, stdin);
            if (buf_pos == buf_len) return true;
        }
        return false;
    }

    char readChar() {
        if (!use_fread) return getchar();
        return isEOF() ? EOF : buf[buf_pos++];
    }

    LL rint() {
        LL x = 0, Fx = 1; char c = readChar();
        while (c < '0' || c > '9') { Fx ^= (c == '-'); c = readChar(); }
        while ('0' <= c && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48); c = readChar(); }
        return Fx ? x : -x;
    }

    template <typename T>
    void read(T &x) {
        x = rint(); 
    }

    template <typename T, typename... Ts>
    void read(T &x, Ts &...rest) {
        read(x);
        read(rest...);
    }
} using namespace Read;

namespace Math {
    LL Max(LL u, LL v) { return (u > v) ? u : v; }
    LL Min(LL u, LL v) { return (u < v) ? u : v; }
} using namespace Math;

const int MAX_n = 1e5;
const int mx = 1289;

int n, Time;
int dp[MAX_n + 5];
int id[MAX_n + 5];
int dfn[MAX_n + 5];
int res[MAX_n + 5];

std::vector<int> G[MAX_n + 5];

void add_edge(int u, int v) {
    G[u].push_back(v);
    G[v].push_back(u);
}

void dfs(int u, int Fu) {
    id[dfn[u] = ++Time] = u;
    for (auto v : G[u])
        if (v != Fu) dfs(v, u);
}

int chk(int k) {
    int ans = 0;
    for (int i = n; i >= 1; i--) {
        int u = id[i];
        int fir = 0, sec = 0;
        for (auto v : G[u]) {
            if (dfn[v] >= dfn[u]) {
                if (dp[v] > fir) sec = fir, fir = dp[v];
                else if (dp[v] > sec) sec = dp[v];
            }
        }
        dp[u] = (((fir + sec + 1) >= k) ? 0 : (fir + 1));
        ans += ((fir + sec + 1) >= k);
    }
    return ans;
}

int main() {
    #ifdef LOCAL
        freopen("DATA.in", "r", stdin);
//      freopen("DATA.out", "w", stdout);
    #endif
    read(n);
    for (int i = 1, u, v; i < n; i++)
        read(u, v), add_edge(u, v);
    dfs(1, 0);
    for (int k = 1; k <= mx && k <= n; k++)
        res[k] = chk(k);
    for (int s = 1; s <= n; s++) {
        int L = 1, R = n / s;
        if (R <= mx) break;
        while (L < R) {
            int Mid = (L + R + 1) >> 1;
            if (chk(Mid) >= s) L = Mid;
            else R = Mid - 1;
        }
        res[L] = Max(res[L], s);
    }
    for (int i = n; i >= 1; i--)
        res[i] = Max(res[i], res[i + 1]);
    for (int i = 1; i <= n; i++)
        printf("%d\n", res[i]);
    return 0;
}