【bzoj2631】【tree】【lct】
发布日期:2021-11-16 15:38:18 浏览次数:4 分类:技术文章

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

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

题解:行星序列的lct版。
           在下放标记的时候乘的标记直接乘上即可。
           加的标记先加再乘。
代码:
#include
     
      #include
      
       #define N 100010#define P 51061using namespace std;int st[N],n,q,x,y,w,rev[N],size[N],c[N][2],fa[N];char ch[10];unsigned int mt[N],a[N],v[N],s[N];bool isroot(int x){return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}void updata(int x){  int l=c[x][0],r=c[x][1];  size[x]=(size[l]+size[r]+1)%P;  s[x]=(s[l]+s[r]+v[x])%P; }void paint(int x,int cc,int aa){  if (!x) return;  v[x]=(v[x]*cc%P+aa)%P;  s[x]=(s[x]*cc%P+size[x]*aa%P)%P;  a[x]=(a[x]*cc%P+aa)%P;  mt[x]=(mt[x]*cc)%P;}void pushdown(int x){  int l=c[x][0],r=c[x][1];  if (rev[x]){rev[l]^=1;rev[r]^=1;rev[x]^=1;swap(c[x][0],c[x][1]);}  int aa=a[x],cc=mt[x];  a[x]=0;mt[x]=1;  if (cc!=1||aa!=0){paint(l,cc,aa);paint(r,cc,aa);} }void rotata(int x){  int y=fa[x],z=fa[y],l,r;  if (x==c[y][0]) l=0;else l=1;r=l^1;  if (!isroot(y)){if (c[z][0]==y)c[z][0]=x;else c[z][1]=x;}  fa[x]=z;fa[y]=x;fa[c[x][r]]=y;  c[y][l]=c[x][r];c[x][r]=y;  updata(y);updata(x);}void splay(int x){  int top(0);st[++top]=x;  for(int i=x;!isroot(i);i=fa[i]) st[++top]=fa[i];   for (int i=top;i;i--) pushdown(st[i]);  while (!isroot(x)){
       
int y=fa[x],z=fa[y];
if (!isroot(y)){
  if (c[y][0]==x^c[z][0]==y) rotata(x);
  else rotata(y);
}
rotata(x);  }}void access(int x){int t(0);while (x){splay(x);c[x][1]=t;t=x;updata(x);x=fa[x];}}void makeroot(int x){access(x);splay(x);rev[x]^=1;}void link(int x,int y){makeroot(x);fa[x]=y;}void cut(int x,int y){makeroot(x);access(y);splay(y);c[y][0]=fa[x]=0;}void split(int x,int y){makeroot(y);access(x);splay(x);}int main(){ scanf("%d%d",&n,&q); for (int i=1;i<=n;i++) mt[i]=size[i]=v[i]=s[i]=1; for (int i=1;i <=q;i++){  scanf("%s",ch);scanf("%d%d",&x,&y);  if (ch[0]=='+'){scanf("%d",&w);split(x,y);paint(x,1,w);}  if (ch[0]=='-'){cut(x,y);scanf("%d%d",&x,&y);link(x,y);}  if (ch[0]=='*'){scanf("%d",&w);split(x,y);paint(x,w,0);}  if (ch[0]=='/'){split(x,y);printf("%d\n",s[x]);} }}


转载地址:https://blog.csdn.net/sunshinezff/article/details/50972941 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:【bzoj1180】【CROATIAN2009】【OTOCI】【lct】
下一篇:【bzoj2049】【SDOI2008】【洞穴勘测】【lct】

发表评论

最新留言

路过按个爪印,很不错,赞一个!
[***.172.111.71]2022年05月22日 08时39分44秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章