一个叫 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 long

int 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;
}

  

最新文章

  1. ble示例代码
  2. 安装完ODAC,出现ORA-12560:TNS:协议适配器错误 12541 无监听程序的解决
  3. 浅析 - 提高xib(Interface Builder)高效工作的几个小技巧
  4. 定时器图片轮播淡入淡出基本功能已实现,正在修改BUG中。。(附图效果和源代码)
  5. Silverlight:版本控制的衍化
  6. javascript与服务器3
  7. XML 实体扩展攻击
  8. 资料Link集合
  9. Delphi中多线程下使用使用 UniDAC+MSSQL 需要注意的问题(连接前调用CoInitialize)
  10. Delphi实现窗口一直在桌面工作区内显示(重写WM_WINDOWPOSCHANGING消息)
  11. thinkphp框架实现删除上传的文件
  12. python全栈开发day118-Mui
  13. 如何阅读jdk源码?
  14. Scrapy基础(三) ------xpath基础
  15. sql server 转置 和实现随机分配和一串代码的含义拼在一行
  16. Javascript中的Bind,Call和Apply
  17. java为什么匿名内部类的参数引用时final(转)
  18. 前段时间,接手一个项目使用的是原始的jdbc作为数据库的访问,发布到服务器上在运行了一段时间之后总是会出现无法访问的情况,登录到服务器,查看tomcat日志发现总是报如下的错误。    Caused by: com.mysql.jdbc.exceptions.jdbc4.MySQLNonTransientConnectionException: Data source rejected est
  19. C#学习笔记(七):结构体、数组、冒泡排序和调试
  20. ucenter 认证登录

热门文章

  1. zzulioj--1777--和尚特烦恼3——何时能下山(水题)
  2. springMVC接受参数总结
  3. handsontable在线编辑excel扩展功能-踩坑篇
  4. Angular4集成ng2-file-upload
  5. ARM的六大类指令集---LDR、LDRB、LDRH、LDM、STR、STRB、STRH、STM
  6. 获取新浪微博的Access_token
  7. vue 事件上加阻止冒泡 阻止默认事件
  8. 对同层数据进行处理,做成树状图形式的数据结构,并符合elementui中的tree结构
  9. 【Computer Vision】图像单应性变换/投影/仿射/透视
  10. vue中的methods、computed和watch