嘘~ 正在从服务器偷取页面 . . .

CF1632E2 Distance Tree (hard version) 题解

发布日期: 2024-07-03

更新日期: 2024-07-03

文章字数: 672

CF1632E2 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;
}