<\/span><\/h2>\nLCT\u5165\u95e8\u9898\uff0c\uff0c<\/p>\n
md\u4e00\u4e2a%=\u5199\u6210\u4e86%\u6539\u4e86\u6211\u4e00\u5929\u3002\u3002\u3002<\/p>\n
#include<map>\r\n#include<cmath>\r\n#include<queue>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<iostream>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define inf 1000000007\r\n#define ll long long\r\n#define uint unsigned int\r\n#define mod 51061\r\n#define N 100010\r\ninline int rd()\r\n{\r\n int x=0;char ch=getchar();\r\n while(ch<'0'||ch>'9') ch=getchar();\r\n while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}\r\n return x;\r\n}\r\nint c[N][2],fa[N],sz[N];\r\nuint lz1[N],lz2[N],v[N],sum[N];\r\nbool rev[N];\r\nint n,q;\r\n#define ls c[x][0]\r\n#define rs c[x][1]\r\nbool isrt(int x){return x!=c[fa[x]][0]&&x!=c[fa[x]][1];}\r\ninline void pd(int x)\r\n{\r\n uint mz;\r\n if(rev[x])\r\n {\r\n rev[ls]^=1;rev[rs]^=1;\r\n swap(ls,rs);rev[x]=0;\r\n }\r\n mz=lz2[x];lz2[x]=1;\r\n if(mz!=1)\r\n {\r\n lz2[ls]=lz2[ls]*mz%mod;\r\n lz2[rs]=lz2[rs]*mz%mod;\r\n lz1[ls]=lz1[ls]*mz%mod;\r\n lz1[rs]=lz1[rs]*mz%mod;\r\n sum[ls]=sum[ls]*mz%mod;\r\n sum[rs]=sum[rs]*mz%mod;\r\n v[ls]=v[ls]*mz%mod;v[rs]=v[rs]*mz%mod;\r\n }\r\n mz=lz1[x];lz1[x]=0;\r\n if(mz)\r\n {\r\n (lz1[ls]+=mz)%=mod;\r\n (lz1[rs]+=mz)%=mod;\r\n (sum[ls]+=sz[ls]*mz)%=mod;\r\n (sum[rs]+=sz[rs]*mz)%=mod;\r\n (v[ls]+=mz)%=mod;(v[rs]+=mz)%=mod;\r\n }\r\n}\r\ninline void upd(int x)\r\n{\r\n sz[x]=sz[ls]+sz[rs]+1;\r\n sum[x]=(v[x]+sum[ls]+sum[rs])%mod;\r\n}\r\nvoid rot(int x)\r\n{\r\n int y=fa[x],z=fa[y],l,r;\r\n l=c[y][1]==x;r=l^1;\r\n if(!isrt(y)) c[z][c[z][1]==y]=x;\r\n fa[x]=z;fa[y]=x;fa[c[x][r]]=y;\r\n c[y][l]=c[x][r];c[x][r]=y;\r\n upd(y);upd(x);\r\n}\r\n\r\nint st[N],tot;\r\nvoid splay(int x)\r\n{\r\n tot=1;st[1]=x;\r\n for(int i=x;!isrt(i);i=fa[i]) st[++tot]=fa[i];\r\n for(int i=tot;i;i--) pd(st[i]);\r\n int y,z;\r\n while(!isrt(x))\r\n {\r\n y=fa[x];z=fa[y];\r\n if(!isrt(y))\r\n {\r\n if((c[y][0]==x)^(c[z][0]==y)) rot(x);\r\n else rot(y);\r\n }\r\n rot(x);\r\n }\r\n}\r\nvoid acc(int x)\r\n{\r\n int t=0;\r\n while(x)\r\n {\r\n splay(x);\r\n rs=t;upd(x);\r\n t=x;x=fa[x];\r\n }\r\n}\r\nvoid rever(int x)\r\n{\r\n acc(x);\r\n splay(x);\r\n rev[x]^=1;\r\n}\r\nvoid mk(int x,int y)\r\n{\r\n rever(x);\r\n acc(y);splay(y);\r\n}\r\nvoid link(int x,int y)\r\n{\r\n rever(x);\r\n fa[x]=y;\r\n}\r\nvoid cut(int x,int y)\r\n{\r\n mk(x,y);\r\n c[y][0]=fa[x]=0;\r\n}\r\ninline void mul(int x,int V)\r\n{\r\n (v[x]*=V)%=mod;\r\n (sum[x]*=V)%=mod;\r\n (lz2[x]*=V)%=mod;\r\n (lz1[x]*=V)%=mod;\r\n}\r\ninline void add(int x,int V)\r\n{\r\n (v[x]+=V)%=mod;\r\n (sum[x]+=V*sz[x])%=mod;\r\n (lz1[x]+=V)%=mod;\r\n}\r\nint main()\r\n{\r\n n=rd();q=rd();\r\n for(int i=1;i<=n;i++) lz2[i]=sz[i]=sum[i]=v[i]=1;\r\n for(int i=1,x,y;i<n;i++)\r\n {\r\n x=rd();y=rd();\r\n link(x,y);\r\n }\r\n char op[2];\r\n int x,y,xx,yy,V;\r\n while(q--)\r\n {\r\n scanf(\"%s\",op);\r\n if(op[0]=='*')\r\n {\r\n x=rd();y=rd();V=rd();\r\n mk(x,y);mul(y,V);\r\n }\r\n else if(op[0]=='+')\r\n {\r\n x=rd();y=rd();V=rd();\r\n mk(x,y);add(y,V);\r\n }\r\n else if(op[0]=='-')\r\n {\r\n x=rd();y=rd();xx=rd();yy=rd();\r\n cut(x,y);link(xx,yy);\r\n }\r\n else \r\n {\r\n x=rd();y=rd();\r\n mk(x,y);printf(\"%d\\n\",sum[y]);\r\n }\r\n }\r\n return 0;\r\n}<\/pre>\n <\/p>\n","protected":false},"excerpt":{"rendered":"
2631: tree Time Limit:\u00a030 Sec\u00a0\u00a0Memory Limit:\u00a0128 MB Des […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[13],"class_list":["post-282","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-lct"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/282","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=282"}],"version-history":[{"count":1,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/282\/revisions"}],"predecessor-version":[{"id":283,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/282\/revisions\/283"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=282"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=282"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=282"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}