【题解】P13078 [NOISG 2019] Rigged Roads

· · 题解

题意

给定一个 N 个节点 E 条边的无向图，你需要给每条边设定一个权值，所有边的权值需要形成一个 1\sim E 的排列，并且这个图分配权值后的最小生成树为一棵给定的生成树，求字典序最小的分配边权的方案。

解法

由于是字典序最小，所以考虑贪心地处理。从 1 至 E 地枚举每条边，并考虑给其分配最小的边权。我们定义生成树上的边为关键边，则根据每条边是否为关键边可以进行如下分讨：

但是显然暴力分配边权会超时，发现一条边只能被分配一次边权，而每次分配边权都可以拆分为 u\to lca 和 v\to lca 两条路径，每条路径只需考虑其祖先，所以设 fa_u 为节点 u 的祖先节点中深度最大的没有点配边权的节点（生成树上的边权可以下放为点权），更新后令 fa_u 变为 u 的父节点，使用并查集维护即可。

时间复杂度 O(N+E\log N)，瓶颈在于找 LCA。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
class DSU //并查集
{
    private:
        int fa[N];
    public:
        int find(int u)
        {
            if(fa[u]==u)return u;
            return fa[u]=find(fa[u]);
        }
        void init(){for(int i=1;i<N;i++)fa[i]=i;}
        void update(int u,int v){fa[find(u)]=v;}
}dsu;
struct edge{int v,w;};
vector<edge>e[N];
void build(int u,int v,int w){e[u].emplace_back((edge){v,w});}
int fa[N],dep[N],siz[N],son[N],num[N];
void get_fa(int u,int f)
{
    fa[u]=f,dep[u]=dep[f]+1,siz[u]=1;
    for(auto i:e[u])
    {
        int v=i.v,w=i.w;
        if(v==f)continue;
        num[v]=w,get_fa(v,u),siz[u]+=siz[v];
        if(siz[v]>siz[son[u]])son[u]=v;
    }
}
int top[N];
void get_top(int u,int tp)
{
    top[u]=tp;
    if(son[u])get_top(son[u],tp);
    for(auto i:e[u])
        if(i.v!=son[u]&&i.v!=fa[u])get_top(i.v,i.v);
}
int LCA(int u,int v) //树链剖分求 LCA
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])swap(u,v);
    return u;
}
int now;
int ans[N];
vector<int>arr;
void get_arr(int u,int aim) //将所有需要分配边权的边存到 arr 中
{
    while(dep[u]>aim)
    {
        int nxt=dsu.find(u);
        if(dep[nxt]<=aim)break;
        arr.emplace_back(num[nxt]);
        u=nxt,dsu.update(u,fa[u]);
    }
}
bool typ[N];
int u[N],v[N];
void solve()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>u[i]>>v[i];
    for(int i=1,a;i<n;i++)cin>>a,typ[a]=true,build(u[a],v[a],a),build(v[a],u[a],a);
    dsu.init();
    get_fa(1,0),get_top(1,1);
    for(int i=1;i<=m;i++)
    {
        if(ans[i])continue;
        if(!typ[i])
        {
            int lca=LCA(u[i],v[i]);
            get_arr(u[i],dep[lca]),get_arr(v[i],dep[lca]);
            sort(arr.begin(),arr.end());
            for(int i:arr)ans[i]=++now; //分配边权
            arr.clear();
        }
        ans[i]=++now;
        if(typ[i])
        {
            if(dep[u[i]]>dep[v[i]])swap(u[i],v[i]);
            dsu.update(v[i],u[i]);
        }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<' ';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _=1;
    for(;_;_--)solve();
    return 0;
}