CF1632E2 Distance Tree (hard version) 题解

题目链接：Distance Tree (hard version)

题意：

本题与 CF1632E1 的唯一区别在于 $n$ 的数据范围。

给定一个包含 $n$ 个节点的树，每条边的长度为 $1$。给出如下定义：

• 定义 $d(v)$ 为从节点 $1$ 到节点 $v$ 的距离。
• 定义 $f(x)$ 为在任意两个点 $a,b$ 之间添加一个长度为 $x$ 的边后，$\max\limits_{1\le v\le n}d(v)$ 的最小值。

现在，对于所有的 $1\le x\le n$，求出 $f(x)$ 的值。

数据范围：

$t$ 组数据，$1\le t\le 10^4,~2\le \sum n\leq 3\times 10^5$。

显然，以 $1$ 为起点连边一定不劣。

设我们已经求出了 $f(x)=k$ ，那么我们只需要考察 $d(x) > k$ 的点即可，因为 $d(x)\le k$ 的 $x$ 连边也没意义。

记 $D_k$ 为所有 $d(x) > k$ 的节点两两之间的最大距离，则有 $\left\lceil\frac{D_k}{2}\right\rceil+x \le k$

这个不等式的可以看作，将整张图中最长的链（直径）的中点与 $1$ 连边。

注意到当 $k$ 增大时，$d(x) > k$ 的节点数会减少，这样 $D_k$ 就是单调减的，已经可以二分出来了。

而 $x$ 增大的过程中会使 $k$ 单调不减，因此我们只需要预处理出 $D_k$ 就可以线性计算答案了。

时间复杂度 $\mathcal{O}(n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define pb push_back
#define N ((int)(3e5 + 15))

vector<int> vec[N]; int dep[N], mx[N];
int dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1; int mx1 = dep[u], mx2 = dep[u];
    for(int v : vec[u]) if(v != fa)
    {
        int k = dfs(v, u);
        if(k > mx1) { mx2 = mx1, mx1 = k; } else up(mx2, k);
    }
    int p = min(mx1, mx2) - 1;
    if(~p) up(mx[p], mx1 + mx2 - 2 * dep[u] + 1);
    return mx1;
}
void solve()
{
    int n; cin >> n; dep[0] = -1;
    rep(i, 0, n + 5) { vec[i].clear(), mx[i] = 0; }
    for(int i = 1, u, v; i < n; i++) { cin >> u >> v; vec[u].pb(v); vec[v].pb(u); }
    int k = dfs(1, 0); Rep(i, k - 1, 0) up(mx[i], mx[i + 1]);
    int res = 0;
    rep(i, 1, n)
    {
        while(res < k && mx[res] / 2 + i > res) ++res;
        cout << res << " \n"[i == n];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}

双倍经验：CF1632E1 Distance Tree (easy version)

---

参考文献：

[1] https://www.luogu.com.cn/article/rhy4zedk

[2] https://www.luogu.com.cn/article/4xrn95l0