首页 > 代码库 > 【bzoj3786】星系探索
【bzoj3786】星系探索
ETT模版题。
真正的Eular-Tour-Tree维护的是树的欧拉序。
由于各种原因,没人知道怎么维护欧拉序,所以我写的是个假的,维护dfs序的。
本质还是用Splay维护序列。
然后因为我常数太差,压着线跑过去的……
#include<bits/stdc++.h> #define N 100010 using namespace std; typedef long long ll; const int M=200500; int n,m,a[M]; struct Edge{int u,v,next;}G[M]; int head[M],tot=0,tpos[M],rt; inline void addedge(int u,int v){ G[++tot].u=u;G[tot].v=v;G[tot].next=head[u];head[u]=tot; G[++tot].u=v;G[tot].v=u;G[tot].next=head[v];head[v]=tot; } int size[M],c[M][3],val[M],addv[M],fa[M],w[M],s[M],top; ll sumv[M]; inline void pushup(int x){ size[x]=size[c[x][0]]+size[c[x][1]]+w[x]; sumv[x]=sumv[c[x][0]]+sumv[c[x][1]]+w[x]*val[x]; } inline void puttag(int x,ll v){val[x]+=v;addv[x]+=v;sumv[x]+=v*size[x];} inline void pushdown(int x){ if(!addv[x])return ; if(c[x][0])puttag(c[x][0],addv[x]); if(c[x][1])puttag(c[x][1],addv[x]); addv[x]=0; } inline void rotate(int x,int &k){ int y=fa[x],z=fa[y],l,r; if(c[y][0]==x)l=0;else l=1;r=l^1; if(y==k)k=x;else{if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;} fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; pushup(y);pushup(x); } inline void splay(int x,int &k){ s[top=1]=x;for(int i=x;i!=rt;i=fa[i])s[++top]=fa[i]; for(int i=top;i;--i)pushdown(s[i]); while(x!=k){ int y=fa[x],z=fa[y]; if(y!=k) if(c[z][0]==y^c[y][0]==x)rotate(x,k); else rotate(y,k); rotate(x,k); } } inline void ins(int x,int v,int ww){ if(!rt)rt=x;else fa[x]=rt,c[rt][1]=x; val[x]=v;w[x]=ww;pushup(x);splay(x,rt); } inline int tmax(int x){while(c[x][1])x=c[x][1];return x;} inline int tmin(int x){while(c[x][0])x=c[x][0];return x;} inline ll query(int x){ splay(x,rt);return sumv[c[x][0]]+1LL*w[x]*val[x]; } inline void change(int x,int y){ splay(x,rt);int t1=tmax(c[rt][0]); splay(x+N,rt);int t2=tmin(c[rt][1]); splay(t1,rt);splay(t2,c[t1][1]); int z=c[t2][0];fa[z]=c[t2][0]=0; splay(y,rt);int t3=tmin(c[y][1]); splay(t3,c[y][1]);fa[z]=t3;c[t3][0]=z; } inline void add(int x,int v){ splay(x,rt);int t1=tmax(c[rt][0]); splay(x+N,rt);int t2=tmin(c[rt][1]); splay(t1,rt);splay(t2,c[t1][1]); puttag(c[t2][0],v); } void build(int u,int f){ ins(u+1,a[u],1); for(int i=head[u];i;i=G[i].next){ int v=G[i].v;if(v==f)continue; build(v,u); } ins(u+N+1,a[u],-1); } int main(){ n=io.read(); for(int i=2;i<=n;i++){int u=io.read();addedge(u,i);} for(int i=1;i<=n;i++)a[i]=io.read(); ins(1,0,0);build(1,0);ins(N*2+1,0,0); m=io.read();char s[20]; while(m--){ scanf("%s",s); if(s[0]==‘Q‘){int x=read();printf("%lld\n",query(x+1));} if(s[0]==‘C‘){int x=read(),y=read();change(x+1,y+1);} if(s[0]==‘F‘){int x=read(),y=read();add(x+1,y);} } return 0; }
【bzoj3786】星系探索
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。