[Medium] CF1976F Remove Bridges

简要题意

有一个 $n$ 个点的树，根节点为 $1$，且根节点的度数也为 $1$。

你需要在图上任意两点连接 $k$ 条边（允许重边），使得对于每一条割边，在树上深度较大的端点的子树内的所有边都是割边。在此限制下，要求整个图的割边数量最少。

对于所有 $k\in[1,n]$，输出此时图中的割边数量最小值。

$T$ 组数据。$2\leq n,\sum n\leq 3\times 10^5$。

思路

先来转化题意，当我们在 $u,v$ 间连接一条边时，路径 $(u,v)$ 时都不再是割边了，所以问题可以转换为对 $k$​ 条路径上的所有边进行覆盖，使得若一条边被覆盖，则这条边上的一端点到根的路径上的所有边均被覆盖。我们要求覆盖的边尽可能多。

接着，我们考虑 $k=1$ 的情况，由于根节点度数为 $1$，故我们只能选择根节点为端点的一条最长链。

然后考虑 $k=2$，此时我们还需要选择一条链进行覆盖，不同的是此时我们不一定需要让路径端点为根节点了，只需要端点的 LCA 在第一条链上即可。对于一般的情况，我们只需要选择两条链，并且这两条链的 LCA 到根的路径上的所有边都被覆盖即可。这个性质很像长链剖分，于是可以将树长链剖分一下（其实如果你做题足够多的话，已经可以看出一个正确且经典的贪心了）。下面是将样例的第二组数据的树进行长链剖分后得到的结果：

对于第一个路径，我们显然选择最长链，对于第二个路径我们可以选择次长链和次次长链。可以得到一个规律：对于 $k$，我们只需要选前 $2k-1$ 长链即可。

至于这样的正确性证明，最优性是显然的，至于合法性，由于链剖分的性质，当我们选择一条链时，顶端的父亲一定选过了（因为包含它的链比这条链更长）。

于是可以用一个大根堆维护长链信息，时间复杂度 $O(Tn\log n)$。

注意一个小细节，除了顶端为根的链之外，其余链的贡献应该是链的底端减去顶端的父节点的深度。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 3e5 + 5;
int n, dep[N], hgt[N], son[N], top[N], len[N];
vector<int> g[N];

void dfs1(int u, int fa){
    dep[u] = dep[fa] + 1;
    for(int v : g[u]){
        if(v == fa) continue;
        dfs1(v, u);
        if(hgt[u] < hgt[v] + 1) hgt[u] = hgt[v] + 1, son[u] = v;
    }
}

void dfs2(int u, int fa){
    len[top[u]] = max(len[top[u]], dep[u] - dep[top[u]] + (top[u] != 1));
    if(son[u]) top[son[u]] = top[u], dfs2(son[u], u);
    for(int v : g[u]){
        if(v == fa || v == son[u]) continue;
        top[v] = v, dfs2(v, u);
    }
}

void solve(){
    cin >> n;
    for(int i=1,x,y;i<n;i++){
        cin >> x >> y;
        g[x].push_back(y), g[y].push_back(x);
    }
    top[1] = 1;
    dfs1(1, 0), dfs2(1, 0);
    priority_queue<int> q;
    for(int i=1;i<=n;i++) q.push(len[i]);
    int cnt = n - 1;
    cout << (cnt -= q.top()) << ' ';
    q.pop();
    for(int i=2;i<n;i++){
        int x = 0, y = 0;
        if(!q.empty()) x = q.top(), q.pop();
        if(!q.empty()) y = q.top(), q.pop();
        cout << (cnt -= x + y) << ' ';
    }
    cout << '\n';
}

void clear(){
    for(int i=1;i<=n;i++){
        g[i].clear();
        dep[i] = hgt[i] = son[i] = top[i] = len[i] = 0;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t; cin >> t;
    while(t--) solve(), clear();
    return 0;
}

// Written by xiezheyuan