题解：P16352 「Gensokyo OI Round 1」雨后长虹

· · 题解

题意

给定一个无向联通图，每个点一个点权。有三个操作：

  1. 给定 q 个关键点 d_1,d_2,...,d_q，求删去能使关键点不连通的非关键点的点权最小值。
  2. 给定 q 个关键点 d_1,d_2,...,d_q，求删去能使关键点不连通的非关键点的点权之和。
  3. 将 u 点的点权改为 k。

思路

树

首先考虑树怎么做。

记 N(u,v) 为 u 到 v 路径上所有非关键点的点集，lc 为所有关键点的 LCA。我们不难发现，所有可以删去的点的集合 Q=N(d_1,lc) \cup N(d_2,lc) \cup ... \cup N(d_q,lc)，即所有关键点 d_i 到 lc 路径上的非关键点的并集。

这启发我们使用重链剖分和线段树。线段树维护 dfn 序下的区间和，以及区间最小值。

对于操作 1。我们可以从每个关键点开始向上跳，所有区间的最小值即为答案。

对于操作 2。如果像操作 1 一样求和，可能会重复计算点权。于是我们再开一颗线段树，区间修改哪些点是有贡献的，有贡献就将区间对应和复制过来，向上求和。操作结束后给 1 号结点打上标记，将此线段树清空即可。

操作 3 即为单点修改。

关于关键点，我们不妨在操作开始时对所有关键点单点修改，将和的贡献设置为 0，最小值的贡献设置为 +\infty。操作结束后改回来。

图

考虑将树的做法推广到图上。显然对于一个点双连通分量内部，我们无论删去哪个点，都无法满足条件。所以我们考虑建出圆方树，将所有方点的值设为 +\infty,0，其他操作照旧。

时间复杂度 O(n \log^2{n})。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=100005;
void read(int &x){
    int f=1;x=0;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    x*=f;
}
int n,m,a[N],low[N],dfn[N],tot,s[N],top,tott,t;
vector<int> g[N];
vector<int> gg[N<<1];
void kfc(int i,int fa){
    low[i]=dfn[i]=++tot;
    s[++top]=i;
    int son=0;
    for(int k=0;k<g[i].size();k++){
        int j=g[i][k];
        if(!dfn[j]){
            son++;
            kfc(j,i);
            low[i]=min(low[i],low[j]);
            if(low[j]>=dfn[i]){
                tott++;
                while(s[top+1]!=j){
                    gg[s[top]].push_back(tott);
                    gg[tott].push_back(s[top--]);
                }
                gg[tott].push_back(i);
                gg[i].push_back(tott);
            }
        }
        else if(j!=fa){
            low[i]=min(low[i],dfn[j]);
        }
    }
    if(son==0 && fa==0){
        tott++;
        gg[tott].push_back(i);
        gg[i].push_back(tott);
    }
}
int rnk[N<<1],siz[N<<1],son[N<<1],df[N<<1],tp[N<<1],dep[N<<1],f[N<<1];
void kfc1(int i,int fa){
    siz[i]=1;
    f[i]=fa;
    dep[i]=dep[fa]+1;
    for(int k=0;k<gg[i].size();k++){
        int j=gg[i][k];
        if(j==fa) continue;
        kfc1(j,i);
        siz[i]+=siz[j];
        if(siz[j]>siz[son[i]]) son[i]=j;
    }
}
int Tot;
void kfc2(int i,int fa,int zx){
    tp[i]=zx;
    df[i]=++Tot;
    rnk[Tot]=i;
    if(son[i]) kfc2(son[i],i,zx);
    for(int k=0;k<gg[i].size();k++){
        int j=gg[i][k];
        if(j==fa || j==son[i]) continue;
        kfc2(j,i,j);
    }  
}
int lca(int x,int y){
    while(tp[x]!=tp[y]){
        if(dep[tp[x]]>dep[tp[y]]) x=f[tp[x]];
        else y=f[tp[y]];
    }
    if(dep[x]>dep[y]) return y;
    else return x;
}
int tr[N<<3],sum[N<<3],ly[N<<3],as[N<<3];
void pushup(int p){
    tr[p]=min(tr[p*2],tr[p*2+1]);
    sum[p]=sum[p*2]+sum[p*2+1];
    as[p]=as[p*2]+as[p*2+1];
}
void pushdown(int p){
    if(ly[p]!=-1){
        ly[p*2]=ly[p*2+1]=ly[p];
        as[p*2]=sum[p*2]*ly[p];
        as[p*2+1]=sum[p*2+1]*ly[p];
        ly[p]=-1;
    }
}
void build(int s,int t,int p){
    ly[p]=-1;
    if(s==t){
        if(rnk[s]<=n) tr[p]=sum[p]=a[rnk[s]];
        else tr[p]=1e18,sum[p]=0;
        return;
    }
    int mid=(s+t)>>1;
    build(s,mid,p*2);
    build(mid+1,t,p*2+1);
    pushup(p);
}
void change(int s,int t,int c1,int c2,int pos,int p){
    if(s==t){
        tr[p]=c1;
        sum[p]=c2;      
        return;
    }
    int mid=(s+t)>>1;
    pushdown(p);
    if(pos<=mid) change(s,mid,c1,c2,pos,p*2);
    else change(mid+1,t,c1,c2,pos,p*2+1);
    pushup(p);
}
void tag(int s,int t,int l,int r,int p){
    if(s>=l && t<=r){
        as[p]=sum[p];
        ly[p]=1;
        return;
    }
    int mid=(s+t)>>1;
    pushdown(p);
    if(l<=mid) tag(s,mid,l,r,p*2);
    if(r>mid) tag(mid+1,t,l,r,p*2+1);
    pushup(p);
}
int query(int s,int t,int l,int r,int p){
    if(s>=l && t<=r){
        return tr[p];
    }
    int mid=(s+t)>>1,ans=1e18;
    pushdown(p);
    if(l<=mid) ans=min(ans,query(s,mid,l,r,p*2));
    if(r>mid) ans=min(ans,query(mid+1,t,l,r,p*2+1));
    return ans;
}
int vis[N<<1];
vector<int> c;
signed main(){
    ios::sync_with_stdio(0);
    cout.tie(0);
    read(n);read(m);
    tott=n;
    for(int i=1;i<=n;i++){
        read(a[i]);
    }
    for(int u,v,i=1;i<=m;i++){
        read(u);read(v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    kfc(1,0);
    kfc1(1,0);
    kfc2(1,0,1);
    build(1,tott,1);
    read(t);
    for(int i=1;i<=t;i++){
        int opt;
        read(opt);
        if(opt==1){
            int q,x;
            read(q);
            read(x);
            int lc=x;
            c.clear();
            c.push_back(x);
            change(1,tott,1e18,0,df[x],1);
            for(int j=2;j<=q;j++){
                read(x);
                c.push_back(x);
                change(1,tott,1e18,0,df[x],1);
                lc=lca(lc,x);
            }
            int ans=1e18;
            for(int k=0;k<c.size();k++){
                int j=c[k],p=lc;
                while(tp[j]!=tp[p]){
                    ans=min(query(1,tott,df[tp[j]],df[j],1),ans);
                    j=f[tp[j]];
                }
                ans=min(query(1,tott,df[p],df[j],1),ans);
            }
            if(ans==1e18) cout<<-1<<'\n';
            else cout<<ans<<'\n';
            for(int k=0;k<c.size();k++){
                change(1,tott,a[c[k]],a[c[k]],df[c[k]],1);
            }
        }       
        if(opt==2){
            int q,x;
            read(q);
            read(x);
            int lc=x;
            c.clear();
            c.push_back(x);
            change(1,tott,1e18,0,df[x],1);
            for(int j=2;j<=q;j++){
                read(x);
                c.push_back(x);
                change(1,tott,1e18,0,df[x],1);
                lc=lca(lc,x);
            }
            for(int k=0;k<c.size();k++){
                int j=c[k],p=lc;
                while(tp[j]!=tp[p]){
                    tag(1,tott,df[tp[j]],df[j],1);
                    j=f[tp[j]];
                }
                tag(1,tott,df[p],df[j],1);
            }
            if(as[1]==0) cout<<-1<<'\n';
            else cout<<as[1]<<'\n';
            ly[1]=0;
            as[1]=0;
            for(int k=0;k<c.size();k++){
                change(1,tott,a[c[k]],a[c[k]],df[c[k]],1);
            }
        }       
        if(opt==3){
            int x,c;
            read(x);read(c);
            a[x]=c;
            change(1,tott,a[x],a[x],df[x],1);
        }
    }
    return 0;
}