树的直径性质 miaomiao problem

· · 题解

miaomiao problem

这是一篇非常详细的有图有证明题解。

思考 a 在哪

结论：a=1

考虑反正：

假设我们 a,b\ne1，像这样：

不妨设加边之前 d(a)\le d(b)，那么加完边后如果边对最终答案有贡献，那么 a 一定可以通过这条边对 b 进行松弛，换句话说，这条边有用当且仅当 d(a)+x\le d(b)。但是如果我们链接 1 和刚才的 b，这条边有用当且仅当 d(1)+x\le d(b)。发现 d(1)=0<d(a)，即把 a 换成 1 一定不会劣。

思考 b 在哪

题目问的是最大距离的最小值，想到~二分~。

也对，这也可以二分，我们就来想想如果写这个 check 函数。

对于目前已经设定好的一个答案 mid，d(v)\le mid 的点成为放心点（这里用棕色），否咋叫做闹心点（这里用红色）。

容易想到，在这个 check 函数中我们可以先确定一个 b，然后返回 [\max_{v\in\mathtt{闹心点}}dis(b,v)\le mid-x]。

我们称由闹心点和两两闹心点之间简单路径上的点组成的联通子图为“闹心树”。

结论：b 为闹心树的直径的最中间位置的任意一点

先设闹心树直径为 D。

前置结论：\ 假设上图横着的那个链是一个直径，闹心点的代价 \max_{v\in\mathtt{闹心点}}d(b)+dis(b,v)=\max_{v\in\mathtt{闹心点}}x+dis(b,v)=\max\{dis(b,d_1),dis(b,d_2)\}=x+\lfloor\frac{D+1}2\rfloor，其中 d_1 和 d_2 为选中的直径的端点。\ 证明这个前置结论可以反证，假设还有闹心点 v 使得 x+dis(b,v)>x+\max\{dis(b,d_1),dis(b,d_2)\} 如上图，那么 dis(b,v)>dis(b,d_2)，因此直径就是 d_1\leftrightarrow\dots\leftrightarrow v，d_1\leftrightarrow\dots\leftrightarrow d_2 不可能是直径，与假设矛盾。

开始证明这个求 b 的结论：\ 还是考虑反正：假设我们找到了一个不是闹心树的任意一直径的最中间位置的任意一点的一个比上面选的 b 还要优的一个结点 b_{good} 使得 \max_{v\in\mathtt{闹心点}}d(b_{good})+dis(b_{good},v)<\max_{v\in\mathtt{闹心点}}d(b)+dis(b,v)。那么我们可以发现 b_{good} 到 d_1 或者 d_2，一定会至少经过一段长度为 \lfloor\frac{D+1}2\rfloor 闹心树的直径的字段。我们在前置结论一中证明了结论中的 b 的代价恰好是 x+\max\{dis(b,d_1),dis(b,d_2)\}，而 b_{good} 的代价至少是 x+\max\{dis(b,d_1),dis(b,d_2)\}，因此选择结论中的 b 肯定不会劣与 b_{good}，然而我们假设找到了严格优于 b 的 b_{good}，因此矛盾。

怎样计算答案

对于一个目前枚举到的 x，我们二分答案（后面会说怎么优化）。暴力找出闹心点和闹心树，跑树形 DP 或两遍 DFS 求直径。时间复杂度 O(n^2\log n)，然后你就可以通过 [450,1500] pts 的 E1。

两个优化

第一个优化

观察~样例输出~随便一棵树，我们发现随着我们的答案的增加（或者说限制的放宽），我们 x 可以变得越来越大。也就是说，随着 x 越来越大，答案不降。

因此我们可以考虑使用双指针之类的东西（我是枚举答案然后计算 \lfloor\frac{D+1}2\rfloor，和答案比大小后计算最大的可行 x，这样似乎好写一点），一个标记目前的 x，一个标记答案，因此我们的这个 \log n 就没了。

第二个优化

后面我们需要通过考虑两次 DFS 求直径把复杂度降下去。

我们第一次 DFS 选择以 1 为根，可以发现得到的与 1 最近的点一定是最后一个变得不再闹心的点之一。

我们还有一个结论，就是这个点一定是任意时刻的闹心树直径之一的端点之一。

证明：闹心树中一定有且仅有一个距离 1 最近的点（这就是闹心点的 LCA，很好证），闹心树为以这个“闹心树跟”为根的子树，那么闹心树中距离闹心树根最远的点一定是一个合法的直径端点。证毕。

因此我们直接维护所有闹心点到这个最闹心点的距离即可，距离这个最闹心的点最远的仍然闹心的点和这个最闹心的点的距离就是闹心树直径长度。（维护这个就随便选一个 O(1) 删或加单点，O(1) 查最值的数据结构即可）

这样，每一个闹心点只会变成放心点，因此总复杂度为 O(n)。

优美的屎山两题都是一遍过（不想加注释了，代码请自行理解）：

// Problem: Distance Tree (easy version)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1632E1
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define int long long
#define MAXN 300005
using namespace std;
int T, n, dis[MAXN], ans[MAXN], dep[MAXN];
vector<int> e[MAXN], box[MAXN];
void dfs(int u, int k, int *Dis) {
    Dis[u] = k;
    for (int v : e[u])
        if (!Dis[v])
            dfs(v, k + 1, Dis);
}
int getdis(int id, int *Dis) {
    for (int i = 1; i <= n; i++)
        Dis[i] = 0;
    dfs(id, 1, Dis);
    int maxn = 0, maxni = id;
    for (int i = 1; i <= n; i++) {
        Dis[i]--;
        if (Dis[i] > maxn) {
            maxn = Dis[i];
            maxni = i;
        }
    }
    return maxni;
}
signed main() {
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            ans[i] = n;
            e[i].clear();
            box[i].clear();
        }
        for (int i = 1, a, b; i < n; i++) {
            cin >> a >> b;
            e[a].push_back(b);
            e[b].push_back(a);
        }
        int maxdep = getdis(1, dep);
        getdis(maxdep, dis);
        ans[n] = dep[maxdep];
        for (int i = 1; i <= n; i++)
            box[dep[i]].push_back(i);
        for (int i = n, D = 0; i >= 0; i--) {
            if ((D + 1) / 2 <= i)
                ans[i - (D + 1) / 2] = min(ans[i - (D + 1) / 2], i);
            for (int j : box[i])
                D = max(D, dis[j]);
        }
        for (int i = n - 1; i >= 1; i--)
            ans[i] = min(ans[i], ans[i + 1]);
        for (int i = 1; i <= n; i++)
            cout << ans[i] << " ";
        cout << endl;
    }
    return 0;
}