首页 > 代码库 > BZOJ2631: tree

BZOJ2631: tree

2024-07-20 08:23:36   213人阅读

2631: tree

Time Limit: 30 Sec  Memory Limit: 128 MB
Submit: 1486  Solved: 515
[Submit][Status]

Description

　一棵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的余数。

 

Input

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

Output

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

Sample Input

3 2
1 2
2 3
* 1 3 4
/ 1 1

Sample Output

4


HINT

 

数据规模和约定

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


 

 

Source

题解：

在pushdown上加一些东西就可以。坑爹的题目居然还要用unsigned int

我惊呆了，long long 居然T了，差这么多。。。

代码：

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cmath>  4 #include<cstring>  5 #include<algorithm>  6 #include<iostream>  7 #include<vector>  8 #include<map>  9 #include<set> 10 #include<queue> 11 #include<string> 12 #define inf 1000000000 13 #define maxn 100000+100 14 #define maxm 500+100 15 #define eps 1e-10 16 #define ll long long 17 #define pa pair<int,int> 18 #define mod 51061 19 using namespace std; 20 inline int read() 21 { 22     int x=0,f=1;char ch=getchar(); 23     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 24     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 25     return x*f; 26 } 27 struct edge{int go,next;}e[2*maxn]; 28 unsigned int  n,m,tot,head[maxn],fa[maxn],c[maxn][2],s[maxn]; 29 unsigned int sta[maxn],add[maxn],mul[maxn],sum[maxn],v[maxn]; 30 bool rev[maxn]; 31 inline void insert(int x,int y) 32 { 33     e[++tot].go=y;e[tot].next=head[x];head[x]=tot; 34     e[++tot].go=x;e[tot].next=head[y];head[y]=tot; 35 } 36 inline bool isroot(int x) 37 { 38     return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; 39 } 40 inline void pushup(int x) 41 { 42     s[x]=s[c[x][0]]+s[c[x][1]]+1; 43     sum[x]=(sum[c[x][0]]+sum[c[x][1]]+v[x])%mod; 44 } 45 inline void rotate(int x) 46 { 47     int y=fa[x],z=fa[y],l=(c[y][1]==x),r=l^1; 48     if(!isroot(y))c[z][c[z][1]==y]=x; 49     fa[x]=z;fa[y]=x;fa[c[x][r]]=y; 50     c[y][l]=c[x][r];c[x][r]=y; 51     pushup(y);pushup(x); 52 } 53 inline void update(int x,int y,int z) 54 { 55     if(!x)return; 56     add[x]=(add[x]*z+y)%mod;mul[x]=(mul[x]*z)%mod; 57     sum[x]=(sum[x]*z+s[x]*y)%mod;v[x]=(v[x]*z+y)%mod; 58 } 59 inline void pushdown(int x) 60 { 61     int l=c[x][0],r=c[x][1]; 62     if(rev[x]) 63     { 64      rev[x]^=1;rev[l]^=1;rev[r]^=1; 65      swap(c[x][0],c[x][1]); 66     } 67     update(l,add[x],mul[x]);update(r,add[x],mul[x]); 68     add[x]=0;mul[x]=1; 69 } 70 inline void splay(int x) 71 { 72     int top=0;sta[++top]=x; 73     for(int y=x;!isroot(y);y=fa[y])sta[++top]=fa[y]; 74     for(;top;)pushdown(sta[top--]); 75     while(!isroot(x)) 76     { 77         int y=fa[x],z=fa[y]; 78         if(!isroot(y)) 79          { 80              if(c[z][0]==y^c[y][0]==x)rotate(x);else rotate(y); 81          } 82         rotate(x);  83     } 84      85 } 86 inline void access(int x) 87 { 88     for(int y=0;x;x=fa[x]) 89     { 90         splay(x);c[x][1]=y;pushup(x);y=x; 91     } 92 } 93 inline void makeroot(int x) 94 { 95     access(x);splay(x);rev[x]^=1; 96 } 97 inline int find(int x) 98 { 99     access(x);splay(x);100     while(c[x][0])x=c[x][0];101     return x;102 }103 inline void link(int x,int y)104 {105     makeroot(x);fa[x]=y;splay(x);106 }107 inline void cut(int x,int y)108 {109     makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;110 }111 inline void split(int x,int y)112 {113     makeroot(x);access(y);splay(y);114 }115 int main()116 {117     freopen("input.txt","r",stdin);118     freopen("output.txt","w",stdout);119     n=read();m=read();120     int x,y,z,top=0;char ch[10];121     for(int i=1;i<n;i++)x=read(),y=read(),insert(x,y);122     for(int i=1;i<=n;i++)s[i]=sum[i]=v[i]=mul[i]=1,add[i]=0;123     sta[++top]=1;124     for(int i=1;i<=top;i++)125      for(int k=sta[i],j=head[k];j;j=e[j].next)126       if(e[j].go!=fa[k])127        {128            fa[y=e[j].go]=k;sta[++top]=y;129        }  130     while(m--)131     {132         scanf("%s",ch);133         switch(ch[0])134         {135             case ‘-‘:{cut(read(),read());link(read(),read());}break;136             case ‘/‘:{x=read();y=read();split(x,y);printf("%d\n",sum[y]);}break;137             case ‘+‘:{x=read();y=read();z=read();split(x,y);update(y,z,1);}break;138             case ‘*‘:{x=read();y=read();z=read();split(x,y);update(y,0,z);}break;139         }140     }141     return 0;142 }
View Cod

BZOJ2631: tree


联系
我们