首页 > 代码库 > BZOJ2631: tree

BZOJ2631: tree

2024-08-13 13:06:08   221人阅读

传送门

AC的有些艰难，为了学这个下标传递先去水了这道题，其实会了下标传递这就是个LCT模板题..

不过LCT还是比较容易写崩，数据结构毁一生

 

 

另外，怎么动态求$node_a$到$node_b$的路径？

void LCA(int noda,int nodb){//noda is LCA    Reverse(nodb);access(noda);splay(noda);    }

先把$node_b$提到树根，然后打通$node_a$到$root$的路径，再把$node_a$转到链根，显然$node_a$的信息就是到$node_b$的路径

 

技术分享
  1 //bzoj 2631  2 //by Cydiater  3 //2016.9.14  4 #include <iostream>  5 #include <cstdio>  6 #include <cstring>  7 #include <string>  8 #include <algorithm>  9 #include <queue> 10 #include <map> 11 #include <cstdlib> 12 #include <iomanip> 13 #include <ctime> 14 #include <cmath> 15 using namespace std; 16 #define ll unsigned int 17 #define up(i,j,n)        for(int i=j;i<=n;i++) 18 #define down(i,j,n)        for(int i=j;i>=n;i--) 19 const int MAXN=1e6+5; 20 const int oo=0x3f3f3f3f; 21 const int mod=51061; 22 inline ll read(){ 23     char ch=getchar();ll x=0,f=1; 24     while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();} 25     while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 26     return x*f; 27 } 28 ll LINK[MAXN],len=0,N,M,q[MAXN],top=0,num,nodea,nodeb; 29 char op; 30 struct edge{ 31     int y,next; 32 }e[MAXN<<1]; 33 struct SplayTree{ 34     ll son[2],sum,delta1,delta2,fa,tag,v,siz; 35 }t[MAXN]; 36 namespace solution{ 37     inline bool get(int node){return t[t[node].fa].son[1]==node;} 38     inline void insert(ll x,ll y){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;} 39     inline bool isroot(int node){return t[t[node].fa].son[0]!=node&&t[t[node].fa].son[1]!=node;} 40     inline void work(int node,ll d1,ll d2){ 41         if(!node)return; 42         t[node].v=t[node].v*d2+d1;t[node].v%=mod;         43         t[node].sum=t[node].sum*d2+d1*t[node].siz;t[node].sum%=mod; 44         t[node].delta1=t[node].delta1*d2+d1;t[node].delta1%=mod; 45         t[node].delta2*=d2;t[node].delta2%=mod; 46     } 47     inline void updata(int node){ 48         if(node){ 49             t[node].sum=t[node].v;t[node].siz=1; 50             if(t[node].son[0]){t[node].sum+=t[t[node].son[0]].sum;t[node].siz+=t[t[node].son[0]].siz;} 51             if(t[node].son[1]){t[node].sum+=t[t[node].son[1]].sum;t[node].siz+=t[t[node].son[1]].siz;} 52             t[node].sum%=mod; 53         } 54     } 55     inline void downit(int node){ 56         ll d1=t[node].delta1,d2=t[node].delta2,tmp; 57         if(t[node].tag){ 58             t[t[node].son[0]].tag^=1;t[t[node].son[1]].tag^=1; 59             swap(t[node].son[0],t[node].son[1]); 60         } 61         work(t[node].son[0],d1,d2);work(t[node].son[1],d1,d2); 62         t[node].delta1=0;t[node].delta2=1;t[node].tag=0; 63     } 64     void rotate(int node){ 65         int old=t[node].fa,oldf=t[old].fa,which=get(node); 66         if(!isroot(old))t[oldf].son[old==t[oldf].son[1]]=node; 67         t[old].son[which]=t[node].son[which^1];t[t[old].son[which]].fa=old; 68         t[old].fa=node;t[node].son[which^1]=old;t[node].fa=oldf; 69         updata(old);updata(node); 70     } 71     void splay(int node){ 72         top=0;q[++top]=node; 73         for(int i=node;!isroot(i);i=t[i].fa)q[++top]=t[i].fa; 74         down(i,top,1)downit(q[i]); 75         while(!isroot(node)){ 76             int old=t[node].fa,oldf=t[old].fa; 77             if(!isroot(old))rotate(get(node)==get(old)?old:node); 78             rotate(node); 79         } 80     } 81     void access(int node){int tmp=0;while(node){splay(node);t[node].son[1]=tmp;updata(node);tmp=node;node=t[node].fa;}} 82     void Reverse(int node){access(node);splay(node);t[node].tag^=1;} 83     void Link(int noda,int nodb){Reverse(noda);t[noda].fa=nodb;splay(noda);} 84     void Cut(int noda,int nodb){Reverse(noda);access(nodb);splay(nodb);t[nodb].son[0]=t[noda].fa=0;} 85     void LCA(int noda,int nodb){//noda is LCA 86         Reverse(nodb);access(noda);splay(noda);     87     } 88     void dfs(int node,int fa){ 89         t[node].sum=1;t[node].fa=fa;t[node].son[1]=t[node].son[0]=0; 90         t[node].delta1=0;t[node].delta2=1;t[node].v=1;t[node].siz=1; 91         for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa)dfs(e[i].y,node); 92     } 93     void init(){ 94         N=read();M=read(); 95         up(i,2,N){ 96             ll x=read(),y=read(); 97             insert(x,y); 98             insert(y,x); 99         }100         dfs(1,0);101     }102     void slove(){103         while(M--){104             scanf("%c",&op);nodea=read();nodeb=read();105             ll de1,de2;106             if(op==‘*‘){107                 de1=0;de2=read();108                 LCA(nodea,nodeb);work(nodea,de1,de2);109             }110             if(op==‘+‘){111                 de1=read();de2=1;112                 LCA(nodea,nodeb);work(nodea,de1,de2);113             }114             if(op==‘-‘){115                 Cut(nodea,nodeb);116                 nodea=read();nodeb=read();117                 Link(nodea,nodeb);118             }119             if(op==‘/‘){120                 LCA(nodea,nodeb);121                 printf("%u\n",t[nodea].sum);122             }123         }124     }125 }126 int main(){127     //freopen("input.in","r",stdin);128     using namespace solution;129     init();130     slove();131     return 0;132 }
View Code

 

BZOJ2631: tree


联系
我们