用 LCT 支持: 在线加边, 单点修改, 求一个两个点路径上的所有边 BCC 的点权和.
用 LCT 维护边 BCC 的形态(即缩边双之后的树),2,3 操作都是 LCT 基本操作, 重点考虑加边操作.
当这条边的两个端点属于同一 BCC 时显然没有任何影响. 当两个端点不在同一个连通块里时直接在 LCT 上做 link(bel[x],bel[y])即可.
当两个端点在同一个连通块里但不在同一个 BCC 中时, 相当于将 (缩点后的) 树上两个点之间的路径全部缩成一个点.
由于过程中有频繁的点合并操作, 所以再拿一个并查集记录每个 BCC 目前真正属于哪个 BCC(即它被合并到哪个点去了), 链合并的时候, 先 split(x,y)分离出这条链, 再将链上所有点的 fa[](并查集上的父亲)全部设为 y, 再将 y 左子树整个删去. 在 LCT 操作中, 我们所有的 f[x](LCT 上的父亲)全部变为 find(f[x]), 这样那些链上连出去的虚子树就能找到自己的新父亲 (y) 了.
- #include<cstdio>
- #include<algorithm>
- #define rep(i,l,r) for (int i=(l); i<=(r); i++)
- using namespace std;
- const int N=150010;
- int n,m,op,x,y,v[N],f[N],fa1[N],fa2[N],c[N][2],w[N],sm[N],rev[N];
- int get1(int x){ return x==fa1[x] ? x : fa1[x]=get1(fa1[x]); }
- int get2(int x){ return x==fa2[x] ? x : fa2[x]=get2(fa2[x]); }
- void upd(int x){ sm[x]=sm[c[x][0]]+sm[c[x][1]]+w[x]; }
- void push(int x){ if (rev[x]) swap(c[x][0],c[x][1]),rev[c[x][0]]^=1,rev[c[x][1]]^=1,rev[x]=0; }
- bool isrt(int x){ return c[get1(f[x])][1]!=x && c[get1(f[x])][0]!=x; }
- void pd(int x){ if (!isrt(x)) pd(get1(f[x])); push(x); }
- void rot(int x){
- int y=get1(f[x]),z=get1(f[y]),w=(c[y][1]==x);
- if (!isrt(y)) c[z][c[z][1]==y]=x;
- f[x]=z; f[y]=x; f[c[x][w^1]]=y;
- c[y][w]=c[x][w^1]; c[x][w^1]=y; upd(y);
- }
- void splay(int x){
- for (pd(x); !isrt(x); rot(x)){
- int y=get1(f[x]),z=get1(f[y]);
- if (!isrt(y)) rot((c[y][0]==x)^(c[z][0]==y)?x:y);
- }
- upd(x);
- }
- void access(int x){ for (int y=0; x; y=x,x=get1(f[x])) splay(x),c[x][1]=y,upd(x); }
- void mkrt(int x){ access(x); splay(x); rev[x]^=1; }
- void link(int x,int y){ mkrt(x); f[x]=y; }
- void split(int x,int y){ mkrt(x); access(y); splay(y); }
- void cut(int x,int y){ split(x,y); c[y][0]=f[x]=0; upd(y); }
- void dfs(int x,int y){
- fa1[x]=y; push(x);
- if (c[x][0]) dfs(c[x][0],y);
- if (c[x][1]) dfs(c[x][1],y);
- }
- int main(){
- freopen("bzoj2959.in","r",stdin);
- freopen("bzoj2959.out","w",stdout);
- scanf("%d%d",&n,&m);
- rep(i,1,n) scanf("%d",&w[i]),sm[i]=v[i]=w[i],fa1[i]=fa2[i]=i;
- rep(i,1,m){
- scanf("%d%d%d",&op,&x,&y); int tx=get1(x),ty=op==2?0:get1(y);
- if (op==1){
- if (tx==ty) continue;
- if (get2(tx)!=get2(ty)) link(tx,ty),fa2[get2(tx)]=get2(ty);
- else split(tx,ty),w[ty]=sm[ty],dfs(ty,ty),c[ty][0]=0;
- }
- if (op==2) splay(tx),w[tx]+=y-v[x],sm[tx]+=y-v[x],v[x]=y;
- if (op==3){
- if (get2(tx)!=get2(ty)) puts("-1");
- else split(tx,ty),printf("%d\n",sm[ty]);
- }
- }
- return 0;
- }
[BZOJ2959]长跑(LCT + 并查集)
来源: http://www.bubuko.com/infodetail-3008233.html