题解 CF1039D 【You Are Given a Tree】

· · 题解

首先讲一讲O(N^2)的做法

O(N^2)就是枚举每个k，然后O(N)判断

怎么判断呢？

遇到树上的覆盖问题，往往都是贪心！

我们可以dfs贪心判断，具体的就是每个点维护一个往下扩展的最长和次长的距离，(不包括当前的点)记为Mx1,Mx2

我们定义Mx1所在的节点为所有在Mx1记录的这条链上的点，Mx2同理！

如果Mx1+Mx2+1>=k那么我们就把这条链提出来，这肯定是最优的，否则Mx2所在的节点将不被覆盖，并且还要覆盖Mx1所在的节点和当且节点和当前节点的fa，但是如果覆盖就只会覆盖Mx1所在的节点和Mx2所在的节点和当前节点，比上述更优！

这个判断类似于noip2018的赛道修建！

给出核心代码：

inline void dfs(int x, int Fa) {
    int Mx1 = 0, Mx2 = 0;
    for (int i = head[x]; i; i = nxt[i]) {
        int y = to[i];
        if (y != Fa) {
            dfs(y, x);
            if (dp[y] > Mx1) Mx2 = Mx1, Mx1 = dp[y]; else if (dp[y] > Mx2) Mx2 = dp[y];
        }
    }
    if (Mx1 + Mx2 + 1 >= cur) dp[x] = 0, cnt++; else dp[x] = Mx1 + 1;
}

剩下的我们考虑怎么优化！

O(N)的判断显然不太可以优化，我们要考虑优化枚举k的过程

我们发现k递增的情况下答案单调不增！

既然答案有单调性，我们有发现这个过程其实和整数分块的过程很像！

答案的取值是O(sqrt(N))种

对于k<=sqrt(N)的我们可以暴力枚举

k>sqrt(N)的答案显然只有<=sqrt(N)的，我们枚举答案，求出答案覆盖的k分别是从Lk-Rk的，就可以了！

但是发现直接按照上述过程模拟，码量稍大，并且要带一个log，于是我们可以考虑写一个整体二分，但是这个整体二分并不是log的复杂度，而是O(N*sqrt(N))的

其实我们只是写了一个O(N^2)的整体二分，但是利用上述性质在优化，最终复杂度是O(N*sqrt(N))的，并且代码非常短！

以下是整体二分的核心代码：

inline 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; return;
    }
    int mid = (l + r) >> 1;
    cur = mid; cnt = 0; dfs(1, 0); ans[mid] = cnt;
    solve(l, mid - 1, cnt, R); solve(mid + 1, r, L, cnt);
}