Tourists——圆方树

CF487E Tourists

一般图，带修求所有简单路径代价。

简单路径，不能经过同一个点两次，那么每个V-DCC出去就不能再回来了。

所以可以圆方树，然后方点维护一下V-DCC内的最小值。

那么，从任意一个割点进入这个DCC，必然可以绕一圈再从另一个割点出去。

所以，路径上的最小值，就是圆方树路径上的最小值。方点的最小值就是在这个DCC中走一走得到的。

树链剖分+线段树维护路径

用堆维护方点四周的圆点的最小值。然后更新。

一个问题是：

更新一个割点圆点，会影响到四周所有的方点。暴力更新，菊花图直接TLE

这样更新：

方点只维护圆方树上儿子圆点的最值。

这样，每次修改圆点，只要修改father的方点的值即可。

查询路径的时候，如果LCA是方点，那么把这个方点的father的值也取min即可。

圆点就无所谓了。LCA自己一定会取到的。

代码：

#include<bits/stdc++.h>

#define reg register int

#define mid ((l+r)>>1)

#define il inline

#define numb (ch^'0')

using namespace std;

typedef long long ll;

il void rd(int &x){

    char ch;x=;bool fl=false;

    while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);

    for(x=numb;isdigit(ch=getchar());x=x*+numb);

    (fl==true)&&(x=-x);

}

namespace Miracle{

const int N=2e5+;

const int inf=0x3f3f3f3f;

int n,m,q;

struct node{

    int nxt,to;

}e[*N],bian[*N];

int hd[N],pre[N];

int cnt1,cnt2;

void _add(int x,int y){

    bian[++cnt1].nxt=pre[x];

    bian[cnt1].to=y;

    pre[x]=cnt1;

}

void add(int x,int y){

    e[++cnt2].nxt=hd[x];

    e[cnt2].to=y;

    hd[x]=cnt2;

}

struct heap{

    priority_queue<int,vector<int>,greater<int> >h,d;

    int top(){

        while(h.size()&&d.size()&&h.top()==d.top()){

            h.pop();d.pop();

        }

        if(h.empty()) return inf;

        return h.top();

    }

    void push(int c){

        h.push(c);

    }

    void dele(int c){

        d.push(c);

    }

}f[N];

int w[N];

int tot,df;

int dfn[N],low[N],sta[N],tp;

void tarjan(int x){

    dfn[x]=low[x]=++df;

    sta[++tp]=x;

    for(reg i=pre[x];i;i=bian[i].nxt){

        int y=bian[i].to;

        if(!dfn[y]){

            tarjan(y);

            low[x]=min(low[x],low[y]);

            if(dfn[x]<=low[y]){

                ++tot;//fang

                w[tot]=inf;//warning!!!

                int z;

                do{

                    z=sta[tp--];

                    add(tot,z);add(z,tot);

                }while(z!=y);

                add(x,tot);add(tot,x);

            }

        }

        else low[x]=min(low[x],dfn[y]);

    }

}

int dep[N],fa[N],top[N],fdfn[N],son[N],sz[N];

void dfs1(int x,int d){

    dep[x]=d;

    sz[x]=;

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa[x]) continue;

        fa[y]=x;

        dfs1(y,d+);

        sz[x]+=sz[y];

        if(sz[y]>sz[son[x]]) son[x]=y;

        if(x>n){//a fang

            f[x].push(w[y]);

            w[x]=min(w[x],w[y]);

        }

    }

}

void dfs2(int x){

    dfn[x]=++df;

    fdfn[df]=x;

    if(!top[x]) top[x]=x;

    if(son[x]) top[son[x]]=top[x],dfs2(son[x]);

    for(reg i=hd[x];i;i=e[i].nxt){

        int y=e[i].to;

        if(y==fa[x]) continue;

        if(y==son[x]) continue;

        dfs2(y);

    }

}

int mi[*N];

void pushup(int x){

    mi[x]=min(mi[x<<],mi[x<<|]);

}

void build(int x,int l,int r){

    if(l==r){

        mi[x]=w[fdfn[l]];return;

    }

    build(x<<,l,mid);

    build(x<<|,mid+,r);

    pushup(x);

}

void chan(int x,int l,int r,int to,int c){

    if(l==r){

        mi[x]=c;return;

    }

    if(to<=mid) chan(x<<,l,mid,to,c);

    else chan(x<<|,mid+,r,to,c);

    pushup(x);

}

int query(int x,int l,int r,int L,int R){

    if(L<=l&&r<=R){

        return mi[x];

    }

    int ret=inf;

    if(L<=mid) ret=min(ret,query(x<<,l,mid,L,R));

    if(mid<R) ret=min(ret,query(x<<|,mid+,r,L,R));

    return ret;

}

int wrk(int x,int y){

    int ret=inf;

    while(top[x]!=top[y]){

        if(dep[top[x]]<dep[top[y]]) swap(x,y);

        ret=min(ret,query(,,tot,dfn[top[x]],dfn[x]));

        x=fa[top[x]];

    }

    if(dep[x]<dep[y]) swap(x,y);

    ret=min(ret,query(,,tot,dfn[y],dfn[x]));

    if(y>n) ret=min(ret,w[fa[y]]);

    return ret;

}

int main(){

    rd(n);rd(m);rd(q);

    for(reg i=;i<=n;++i)rd(w[i]);

    int x,y;

    for(reg i=;i<=m;++i){

        rd(x);rd(y);

        _add(x,y);_add(y,x);

    }

    tot=n;

    tarjan();

    memset(dfn,,sizeof dfn);

    df=;

    dfs1(,);

    dfs2();

    build(,,tot);

    char ch[];

    while(q--){

        scanf("%s",ch+);

        if(ch[]=='A'){

            rd(x);rd(y);

            printf("%d\n",wrk(x,y));

        }

        else{

            rd(x);rd(y);

            int ff=fa[x];

            f[ff].dele(w[x]);

            f[ff].push(y);

            int tmp=f[ff].top();

            chan(,,tot,dfn[ff],tmp);

            w[ff]=tmp;//no use in fact

            w[x]=y;

            chan(,,tot,dfn[x],y);

        }

    }

    return ;

}

}

int main(){

    Miracle::main();

    return ;

}

/*

   Author: *Miracle*

   Date: 2018/11/30 16:10:40

*/

巴特西

Tourists——圆方树

最新文章

热门文章