一個叫 Euler-Tour-Tree 的數據結構，說白了就是用 Splay_Tree 維護歐拉序

#include <cstring> #include <algorithm> #include <string> #include <cstdio>using namespace std;void setIO(string a){ freopen((a+".in").c_str(),"r",stdin);freopen((a+".out").c_str(),"w",stdout); }#define maxn 300000 #define ll long longint euler[maxn], w[maxn], cnt=1; int head[maxn],to[maxn],nex[maxn],edges,root; ll sumv[maxn], val[maxn], lazy[maxn]; void addedge(int u,int v){nex[++edges]=head[u],head[u]=edges,to[edges]=v; }void dfs(int u){euler[++cnt]=u*2, val[u*2]=w[u];for(int v=head[u];v;v=nex[v])dfs(to[v]);euler[++cnt]=u*2+1, val[u*2+1]=-w[u]; }struct Splay_Tree{int f[maxn],ch[maxn][2],sta[maxn],siz[maxn];int rson(int x){return ch[x][1];}int lson(int x){return ch[x][0];}int get(int x){return ch[f[x]][1]==x;}void update(int x,int c){val[x]+=(x%2==0?1:-1)*c;lazy[x]+=c;sumv[x]+=siz[x]*c;}void pushup(int x){ sumv[x]=sumv[lson(x)]+sumv[rson(x)]+val[x];siz[x]=siz[lson(x)]+siz[rson(x)];siz[x]+=(x>=200099 ? 0: (x%2==0?1:-1));}void pushdown(int x){if(lazy[x]) update(lson(x),lazy[x]), update(rson(x),lazy[x]),lazy[x]=0;} int pre(int x){splay(x,root);x=lson(root);while(rson(x)) x=rson(x);return x;}int las(int x){splay(x,root);x=rson(root);while(lson(x)) x=lson(x);return x;}void build(int l,int r,int &o,int fa){if(l>r)return;int mid=(l+r)>>1;o=euler[mid], f[o]=fa;build(l,mid-1,ch[o][0],o);build(mid+1,r,ch[o][1],o);pushup(o);}void rotate(int x){int old=f[x], oldf=f[old], which=get(x);ch[old][which]=ch[x][which^1], f[ch[old][which]]=old;ch[x][which^1]=old,f[old]=x,f[x]=oldf;if(oldf) ch[oldf][ch[oldf][1]==old]=x;pushup(old),pushup(x);}void splay(int x,int &tar){int v=0,u=x,a=f[tar];while(u!=a) sta[++v]=u,u=f[u];while(v) pushdown(sta[v--]);for(int fa;(fa=f[x])!=a;rotate(x))if(f[fa]!=a) rotate(get(fa)==get(x)?fa:x);tar=x;}void opt1(int a){int x=las(a*2);splay(200100,root),splay(x,ch[root][1]);printf("%lld\n",sumv[ch[ch[root][1]][0]]);}void opt2(int a,int b){int x=pre(a*2),y=las(a*2+1),tmp;splay(x,root),splay(y,ch[root][1]);tmp=ch[ch[root][1]][0], ch[ch[root][1]][0]=f[tmp]=0;pushup(ch[root][1]), pushup(root);x=las(b*2);splay(b*2,root), splay(x,ch[root][1]);ch[ch[root][1]][0]=tmp,f[tmp]=ch[root][1];pushup(ch[root][1]),pushup(root);}void opt3(int a,int b){int x=pre(a*2),y=las(a*2+1);splay(x,root),splay(y,ch[root][1]);update(ch[ch[root][1]][0],b);pushup(ch[root][1]),pushup(root);}}tree;int main(){//setIO("input");int n,x,m;scanf("%d",&n);for(int i=2;i<=n;++i)scanf("%d",&x),addedge(x,i);for(int i=1;i<=n;++i) scanf("%d",&w[i]);dfs(1);euler[1]=200100, euler[++cnt]=200101;tree.build(1,cnt,root,0);scanf("%d",&m);while(m--){char opt[10];int a,b;scanf("%s",opt);if(opt[0]=='Q'){scanf("%d",&a);tree.opt1(a);}if(opt[0]=='C'){scanf("%d%d",&a,&b);tree.opt2(a,b);}if(opt[0]=='F'){scanf("%d%d",&a,&b);tree.opt3(a,b);}}return 0; }

　　

轉載于:https://www.cnblogs.com/guangheli/p/10011464.html

總結

以上是生活随笔為你收集整理的BZOJ 3786: 星系探索 欧拉游览树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。