题解：CF1976F Remove Bridges

yshpdyt · 2024-06-01 15:27:45 · 题解

题意

一棵根节点为 1 的树，节点 1 只有一个儿子，你可以加 k 条边，且满足以下条件：

对于每一条割边，该割边的下顶点的子树上的所有树边也应该是割边。
使割边数量尽可能小。

输出对于每个 k\in[1,n-1] 的答案。

Sol

~~这 F 怎么比 D 还水。~~

注意到节点 1 只有一个儿子，所以其一定是割边的一端，先考虑第一条边如何加。

由于第一条限制，加的边的一端必须是 1。

由于第二条限制，加的边的另一端深度越大答案越优。

所以第一条边，两端分别是 1 和深度最大点。

接着考虑连成环后如何处理。

注意到第一次选择的链将整棵树分成若干部分，如图。

根据刚才的思想，我们要选择不在环上的部分长度最长的链。对于一条链的情况，和刚才类似处理即可。对于分成多个部分，我们发现可以选择两个被红链分开的链，在两个链的叶子节点处加边，一次性可以减少两个部分的割边。

这样做一定合法，因为选中的两条链的顶端的 lca 在红链上。

这样做一定最优，如果能选一条链让答案最大，那么让这条链与另一个链结合，答案会更大。

选完第二条链后，红色部分扩大，仍然是分成若干蓝色部分，重复刚才的操作即可。

~~乱猜结论贪心题证明总是能写一大堆。~~

如何统计答案？每次的答案是选择两条满足叶子节点到红链最长的链，特别的第一次答案是选择深度最大的叶子节点。

注意到分成若干条链的情况和树链剖分很相似，到红链可以变成到链顶。由于每次选择的点和最大深度有关，考虑长链剖分的思想。

具体来说，优先去找深度最大的链，每次走到叶子节点，就把 dep_x-dep_{top}+1 放入优先队列，最后每次选择长度最大的两个元素进行合并即可，特别的，第一次加边只应选择一个，且要答案减一，原因是 1 没有父亲，也就没有到红链的距离这一说，就是深度最大点到 1 的距离。

感觉说起来很抽象，还是看看代码吧。

时间复杂度 O(n\log n)。

Code

#include<bits/stdc++.h>
#define ll long long
#define N 300005
#define endl "\n" 
#define fi first
#define se second
using namespace std;
const ll mod=1e9+7;
const ll inf=1e18;
const double eps=1e-6;
priority_queue<ll>q;
namespace sp{
    ll fa[N],dep[N],son[N],siz[N],len[N],top[N];
    vector<ll>v[N];
    void dfs(ll x,ll fat){
        len[x]=x;//子树内深度最大点的编号，如果是自己说明是叶子节点
        fa[x]=fat;
        dep[x]=dep[fa[x]]+1;
        for(auto y:v[x]){
            if(y==fa[x])continue;
            dfs(y,x);
            if(dep[len[x]]<dep[len[y]]){
                len[x]=len[y];
                son[x]=y;//类似重链剖分，为长儿子
            }
        }
    }
    void dfs2(ll x,ll tp){
        top[x]=tp;
        if(son[x])dfs2(son[x],tp);//先找长的链
        for(auto y:v[x]){
            if(y==fa[x]||y==son[x])continue;
            dfs2(y,y);
        }
        if(len[x]==x)q.push(dep[x]-dep[top[x]]+1);
    }

}using namespace sp;
ll n;
void sol(){
    cin>>n;
    while (!q.empty())q.pop();
    for(int i=1;i<=n;i++){
        fa[i]=dep[i]=son[i]=siz[i]=len[i]=top[i]=0;
        v[i].clear();
    }
    for(int i=1;i<n;i++){
        ll x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,0);
    dfs2(1,1);
    ll res=n;//应该是n-1，但第一次要+1。
    auto t=q.top();
    q.pop();
    res-=t;
    cout<<res<<" ";
    for(int i=1;i<n-1;i++){
        if(q.size()>=1){
            t=q.top();
            q.pop();
            res-=t;
        }
        if(q.size()>=1){
            t=q.top();
            q.pop();
            res-=t;
        }
        cout<<res<<" ";
    }
    cout<<endl;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ll ttt;
    cin>>ttt;
    while(ttt--)sol();
    return 0;
}

题解：CF1976F Remove Bridges

题意

Sol

Code