BZOJ2631tree——LCT-白红宇

BZOJ2631tree——LCT

阅读量：5214 次

发布时间：2019-06-14

本文共 2502 字，大约阅读时间需要 8 分钟。

题目描述

　一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：

+ u v c：将u到v的路径上的点的权值都加上自然数c；

- u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；

* u v c：将u到v的路径上的点的权值都乘上自然数c；

/ u v：询问u到v的路径上的点的权值和，求出答案对于51061的余数。

输入

　　第一行两个整数n，q

接下来n-1行每行两个正整数u，v，描述这棵树

接下来q行，每行描述一个操作

输出

　　对于每个/对应的答案输出一行

样例输入

3 2

1 2

2 3

* 1 3 4

/ 1 1

样例输出

提示

数据规模和约定

10%的数据保证，1<=n，q<=2000

另外15%的数据保证，1<=n，q<=5*10^4，没有-操作，并且初始树为一条链

另外35%的数据保证，1<=n，q<=5*10^4，没有-操作

100%的数据保证，1<=n，q<=10^5，0<=c<=10^4

LCT，splay每个点维护子树和，单点权值和两个区间修改标记，注意加法和乘法运算顺序即可。开unsigned int即可，开longlong可能会T。

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define ll unsigned intusing namespace std;int n,m;int x,y,z,w;int mod=51061;char ch[2];int f[100010];int s[100010][2];int st[100010];int r[100010];int size[100010];ll sum[100010];ll val[100010];ll a[100010];ll b[100010];int get(int rt){ return rt==s[f[rt]][1];}void change(int rt,int x,int y){ if(!rt) { return ; } sum[rt]=(sum[rt]*x+y*size[rt])%mod; val[rt]=(val[rt]*x+y)%mod; a[rt]=(a[rt]*x+y)%mod; b[rt]=(b[rt]*x)%mod;}void pushup(int rt){ sum[rt]=(sum[s[rt][0]]+sum[s[rt][1]]+val[rt])%mod; size[rt]=(size[s[rt][0]]+size[s[rt][1]]+1)%mod;}void pushdown(int rt){ if(r[rt]) { swap(s[rt][0],s[rt][1]); r[s[rt][0]]^=1; r[s[rt][1]]^=1; r[rt]^=1; } int x=a[rt]; int y=b[rt]; a[rt]=0; b[rt]=1; if(x!=0||y!=1) { change(s[rt][0],y,x); change(s[rt][1],y,x); }}int is_root(int rt){ return s[f[rt]][0]!=rt&&s[f[rt]][1]!=rt;}void rotate(int rt){ int fa=f[rt]; int anc=f[fa]; int k=get(rt); if(!is_root(fa)) { s[anc][fa==s[anc][1]]=rt; } s[fa][k]=s[rt][k^1]; f[s[fa][k]]=fa; s[rt][k^1]=fa; f[fa]=rt; f[rt]=anc; pushup(fa); pushup(rt);}void splay(int rt){ int top=0; st[++top]=rt; for(int i=rt;!is_root(i);i=f[i]) { st[++top]=f[i]; } for(int i=top;i>=1;i--) { pushdown(st[i]); } for(int fa;!is_root(rt);rotate(rt)) { if(!is_root(fa=f[rt])) { rotate(get(rt)==get(fa)?fa:rt); } }}void access(int rt){ for(int x=0;rt;x=rt,rt=f[rt]) { splay(rt); s[rt][1]=x; pushup(rt); }}void reverse(int rt){ access(rt); splay(rt); r[rt]^=1;}void split(int x,int y){ reverse(x); access(y); splay(y);}void link(int x,int y){ reverse(x); f[x]=y;}void cut(int x,int y){ reverse(x); access(y); splay(y); s[y][0]=f[x]=0;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { size[i]=val[i]=sum[i]=b[i]=1; } for(int i=1;i