bzoj2631 -- LCT
2018-06-17 23:06:20来源:未知 阅读 ()
包含了link、cut、update、query操作。
更新时类似线段树就可以了。
代码:
#include<cstdio> #include<iostream> #include<cstring> using namespace std; #define N 100010 #define M 51061 #define ll unsigned int inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if(p1==p2){ p2=(p1=buf)+fread(buf,1,100000,stdin); if(p1==p2)return EOF; } return *p1++; } inline void Read(int& x){ char c=nc(); for(;c<'0'||c>'9';c=nc()); for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc()); } inline void Read(char& C){ char c=nc(); for(;c!='+'&&c!='*'&&c!='-'&&c!='/';c=nc()); C=c; } int Len; char S[30]; inline void Print(ll x){ if(x==0)putchar(48); for(Len=0;x;x/=10)S[++Len]=x%10; for(;Len;)putchar(S[Len--]+48);putchar('\n'); } int i,j,k,n,m,Q,f[N],h[N],ch[N][2],x,y,z,s[N]; ll Sum[N],p1[N],p2[N],a[N]; bool b[N],r[N]; char C; inline int Get(int x){return ch[f[x]][1]==x;} inline void Update_rev(int x){ if(x==0)return; r[x]^=1;swap(ch[x][0],ch[x][1]); } inline void Update_mul(int x,int y){ Sum[x]=(Sum[x]*y)%M;a[x]=(a[x]*y)%M;p1[x]=(p1[x]*y)%M;p2[x]=(p2[x]*y)%M; } inline void Update_add(int x,int y){ Sum[x]=(Sum[x]+y*s[x])%M;a[x]=(a[x]+y)%M;p2[x]=(p2[x]+y)%M; } inline void Pushdown(int x){ if(r[x]){ Update_rev(ch[x][0]); Update_rev(ch[x][1]); r[x]=0; } if(p1[x]!=1){ Update_mul(ch[x][0],p1[x]); Update_mul(ch[x][1],p1[x]); p1[x]=1; } if(p2[x]){ Update_add(ch[x][0],p2[x]); Update_add(ch[x][1],p2[x]); p2[x]=0; } } inline void Pushup(int x){ Sum[x]=(Sum[ch[x][0]]+Sum[ch[x][1]]+a[x])%M; s[x]=s[ch[x][0]]+s[ch[x][1]]+1; } inline void Rotate(int x){ int y=f[x];bool d=Get(x); if(b[y])b[y]=0,b[x]=1;else ch[f[y]][Get(y)]=x; ch[y][d]=ch[x][d^1];f[ch[y][d]]=y; ch[x][d^1]=y;f[x]=f[y];f[y]=x; Pushup(y); } inline void P(int x){if(!b[x])P(f[x]);Pushdown(x);} inline void Splay(int x){ for(P(x);!b[x];Rotate(x)) if(!b[f[x]])Rotate(Get(x)==Get(f[x])?f[x]:x); Pushup(x); } inline void Access(int x){ int y=0; while(x){ Splay(x); b[ch[x][1]]=1;ch[x][1]=y;b[y]=0; Pushup(y=x);x=f[x]; } } inline void mr(int x){Access(x);Splay(x);Update_rev(x);} inline void Link(int x,int y){mr(x);f[x]=y;} inline void Update_Add(int x,int y,int z){ mr(x);Access(y);Splay(y); Update_add(y,z); } inline void Update_Mul(int x,int y,int z){ mr(x);Access(y);Splay(y); Update_mul(y,z); } inline void Del(int x,int y){ mr(x);Access(y);Splay(y); f[x]=ch[y][0]=0;b[x]=1;Pushup(y); } inline ll Query(int x,int y){ mr(x);Access(y);Splay(y); return Sum[y]; } int main() { Read(n);Read(Q); for(i=1;i<=n;i++)a[i]=b[i]=Sum[i]=s[i]=p1[i]=1; for(i=1;i<n;i++)Read(x),Read(y),Link(x,y); while(Q--){ Read(C); if(C=='+')Read(x),Read(y),Read(z),Update_Add(x,y,z);else if(C=='-')Read(x),Read(y),Del(x,y),Read(x),Read(y),Link(x,y);else if(C=='*')Read(x),Read(y),Read(z),Update_Mul(x,y,z);else Read(x),Read(y),Print(Query(x,y)); } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C语言程序结构 2020-05-31
- 读入字符串的方法 2020-01-04
- 类———用类定义对象———error:C++表达式必须包含类类型 2019-05-22
- 查看程序运行时间以及延时程序实现 2019-04-25
- 华为机试 合并表记录 2018-09-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash