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

highkj · 2026-04-27 09:53:32 · 题解

前言

乱炖题吧。

思路

树

首先我们考虑树的情况，我们发现对于两个点 x,y 能删除的点使得其不连通的只有 x\to y 路径上的点可以满足，然后对于每一个操作维护一下就行了。

具体来说，对于操作 1 我们只需要求出包含这个点击的最小的连通块内的最小点权即可，这里我们只需要按 dfs 序排序然后求相邻两点之间的路径上的最小值即可；对于操作二我们相当于要求这个连通块的点权之和，也很简单我们还是将这些点按照 dfs 序排序，然后答案就是 \sum s_{a_i}-\sum s_{lca_{a_i,a_i+1}}+val_{x} 其中的 s_i 表示从 1\sim i 的路径和，x 表示 a_1\sim a_p 的最近公共祖先，这个也很好用树剖维护，对于第三个操作直接线段树上单点修改就行了。

对于他说的不能选择点集中的点我们只需要在每次查询前先将每一个点的最小值改为极大值，和改为 0 即可。

图

考虑将树的做法类推到图上，我们发现对于图上的 x,y 能删的点还是路径上的，但是路径可能有多条那么能删的点其实就是所有路径的交，因为图上的路径不好维护所以还是考虑往树上靠，所以我们考虑对于原图建出园方树，那么能删的点就能了路径上的点了，然后所有操作就和上面一样维护即可。

代码

简直是史。

#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
    if(x<0) printf("-"),x=-x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
const int N=2e5+10;
int a[N];
int n,m;
int dfn[N],low[N];
stack<int>s;
vector<int>v[N];
vector<int>ve[N];
int idx,tot,rt[N],ss[N];
void tarjan(int x,int fr) {
    dfn[x]=low[x]=++tot;
    ss[fr]++;
    s.push(x);
    rt[x]=fr;
    for(auto to:v[x]) {
        if(!dfn[to]) {
            tarjan(to,fr);
            low[x]=min(low[x],low[to]);
            if(low[to]==dfn[x]) {
                idx++;
                int p;
                do{
                    p=s.top();
                    s.pop();
                    ve[idx].pb(p);
                    ve[p].pb(idx);
                }while(p!=to);
                ve[idx].pb(x);
                ve[x].pb(idx);
            }
        }else low[x]=min(low[x],dfn[to]);
    }
}
struct node{
    int l,r;
    int mn,sum;
}tr[N<<2];
void up(int x) {
    tr[x].mn=min(tr[x<<1].mn,tr[x<<1|1].mn);
    tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
}
int siz[N],mx[N];
int fat[N],dep[N],val[N];
void dfs(int x,int fa) {
    fat[x]=fa;
    dep[x]=dep[fa]+1;
    siz[x]=1;
    for(auto to:ve[x]) {
        if(to==fa) continue;
        dfs(to,x);
        siz[x]+=siz[to];
        if(siz[to]>siz[mx[x]]) mx[x]=to;
    }
}
int top[N],df[N],dd,v1[N],a1[N];
void dfs1(int x,int h) {
    top[x]=h;
    df[x]=++dd;
    val[dd]=a[x];
    v1[dd]=a1[x];
    if(!mx[x]) return;
    dfs1(mx[x],h);
    for(auto to:ve[x]) {
        if(!df[to]) dfs1(to,to);
    }
}
const int inf=1e18;
void build(int u,int l,int r) {
    tr[u]={l,r,inf,0};
    if(l==r) {
        tr[u].mn=val[l];
        tr[u].sum=v1[l];
        return;
    }
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    up(u);
}
void modify(int u,int x,int k,int k1) {
    if(tr[u].l==tr[u].r) {
        tr[u].mn=k1,tr[u].sum=k;
        return;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(mid>=x) modify(u<<1,x,k,k1);
    else modify(u<<1|1,x,k,k1);
    up(u);
}
int Ans(int u,int l,int r) {
    if(l>r) return false;
    if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;
    int mid=tr[u].l+tr[u].r>>1,res=0;
    if(mid>=l) res=Ans(u<<1,l,r);
    if(mid<r) res+=Ans(u<<1|1,l,r);
    return res;
}
int Ans1(int u,int l,int r) {
    if(l>r) return inf;
    if(tr[u].l>=l&&tr[u].r<=r) {
        return tr[u].mn;
    }
    int mid=tr[u].l+tr[u].r>>1,res=inf;
    if(mid>=l) res=Ans1(u<<1,l,r);
    if(mid<r) res=min(res,Ans1(u<<1|1,l,r));
    return res;
}
bool cmp(int x,int y) {
    return df[x]<df[y];
}
int f[N][20];
void init() {
    rep(j,1,19) rep(i,1,idx) f[i][j]=f[f[i][j-1]][j-1];
}
int lca(int x,int y) {
    if(dep[x]>dep[y]) swap(x,y);
    rep1(i,19,0) if(dep[f[y][i]]>=dep[x]) y=f[y][i];
    if(x==y) return x;
    rep1(i,19,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return f[x][0];
}
int get(int x,int y) {
    int res=inf;
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        res=min(res,Ans1(1,df[top[x]],df[x]));
        x=fat[top[x]];
    }
    if(df[x]>df[y]) swap(x,y);
    res=min(res,Ans1(1,df[x],df[y]));
    return res;
}
int get1(int x,int y) {
    int res=0;
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        res+=Ans(1,df[top[x]],df[x]);
        x=fat[top[x]];
    }
    if(df[x]>df[y]) swap(x,y);
    res+=Ans(1,df[x],df[y]);
    return res;
}
void solve() {
    in(n),in(m);
    idx=n;
    rep(i,1,n) in(a[i]),a1[i]=a[i];
    rep(i,1,m) {
        int x,y;
        in(x),in(y);
        v[x].pb(y);
        v[y].pb(x);
    }
    rep(i,1,n) if(!dfn[i]) tarjan(i,i);
    rep(i,n+1,idx) a[i]=1e18,a1[i]=0;
    dfs(1,0);
    dfs1(1,1);
    build(1,1,dd);
    int q;
    in(q);
    rep(i,1,dd) f[i][0]=fat[i];
    init();
    while(q--) {
        int opt;
        in(opt);
        if(opt==1) {
            int qc;
            in(qc);
            vector<int>arr;
            vector<array<int,2>>vk;
            rep(i,1,qc)  {
                int x;
                in(x);
                arr.pb(x);
                vk.pb({x,a[x]});
                modify(1,df[x],0,inf);
            }
            sort(arr.begin(),arr.end(),cmp);
            int len=arr.size(),res=1e18;
            rep(i,0,len-2) {
                res=min(res,get(arr[i],arr[i+1]));
            }
            if(res>=inf) puts("-1");
            else printf("%lld\n",res);
            for(auto to:vk) modify(1,df[to[0]],to[1],to[1]);
        }else if(opt==2) {
            int qc;
            in(qc);
            vector<int>arr;
            vector<array<int,2>>vk;
            rep(i,1,qc)  {
                int x;
                in(x);
                arr.pb(x);
                vk.pb({x,a[x]});
                modify(1,df[x],0,inf);
            }
            sort(arr.begin(),arr.end(),cmp);
            arr.erase(unique(arr.begin(),arr.end()),arr.end());
            int len=arr.size(),res=0;
            int tt=arr[0];
            for(auto to:arr) res+=get1(1,to),tt=lca(tt,to);
            arr.pb(arr[0]);
            rep(i,0,len-1) {
                int lc=lca(arr[i],arr[i+1]);
                res-=get1(1,lc);
            }
            res+=Ans(1,df[tt],df[tt]);
            if(!res) puts("-1");
            else printf("%lld\n",res);
            for(auto to:vk) modify(1,df[to[0]],to[1],to[1]);
        }else {
            int x,k;
            in(x),in(k);
            a[x]=k;
            modify(1,df[x],k,k);
        }
    }
}
fire main() {
    while(T--) {
        solve();
    }
    return false;
}