「BZOJ2631」tree
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行，每行描述一个操作
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
Output
对于每个/对应的答案输出一行
Sample Input
3 2
1 2
2 3
* 1 3 4
/ 1 1
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
题解
其实这题不需要开long long。。。只要unsigned int，不然可能会T
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
#include<set> #include<map> #include<ctime> #include<queue> #include<cmath> #include<cstdio> #include<vector> #include<cstring> #include<cstdlib> #include<complex> #include<iostream> #include<algorithm> #define mod 51061 #define ll unsigned int using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,top,cnt; int c[100005][2],fa[100005]; int size[100005],q[100005]; bool rev[100005]; ll sum[100005],val[100005],at[100005],mt[100005]; void cal(int x,int m,int a) { if(!x)return; val[x]=(val[x]*m+a)%mod; sum[x]=(sum[x]*m+a*size[x])%mod; at[x]=(at[x]*m+a)%mod; mt[x]=(mt[x]*m)%mod; } bool isroot(int x) { return c[fa[x]][0]!=x&&c[fa[x]][1]!=x; } void update(int x) { int l=c[x][0],r=c[x][1]; sum[x]=(sum[l]+sum[r]+val[x])%mod; size[x]=(size[l]+size[r]+1)%mod; } void pushdown(int x) { int l=c[x][0],r=c[x][1]; if(rev[x]) { rev[x]^=1;rev[l]^=1;rev[r]^=1; swap(c[x][0],c[x][1]); } int m=mt[x],a=at[x]; mt[x]=1;at[x]=0; if(m!=1||a!=0) { cal(l,m,a);cal(r,m,a); } } void rotate(int x) { int y=fa[x],z=fa[y],l,r; l=(c[y][1]==x);r=l^1; if(!isroot(y))c[z][c[z][1]==y]=x; fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; update(y);update(x); } void splay(int x) { q[++top]=x; for(int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i]; while(top)pushdown(q[top--]); while(!isroot(x)) { int y=fa[x],z=fa[y]; if(!isroot(y)) { if(c[y][0]==x^c[z][0]==y)rotate(x); else rotate(y); } rotate(x); } } void access(int x) { for(int t=0;x;t=x,x=fa[x]) { splay(x);c[x][1]=t;update(x); } } void makeroot(int x) { access(x);splay(x);rev[x]^=1; } void split(int x,int y) { makeroot(y);access(x);splay(x); } 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; } int main() { n=read();m=read(); int u,v,c; for(int i=1;i<=n;i++) val[i]=sum[i]=mt[i]=size[i]=1; for(int i=1;i<n;i++) { u=read(),v=read(); link(u,v); } char ch[5]; while(m--) { scanf("%s",ch); u=read();v=read(); if(ch[0]=='+') { c=read(); split(u,v);cal(u,1,c); } if(ch[0]=='-') { cut(u,v); u=read();v=read();link(u,v); } if(ch[0]=='*') { c=read(); split(u,v);cal(u,c,0); } if(ch[0]=='/') { split(u,v); printf("%d\n",sum[u]); } } return 0; } |
计数器 9863396
OI 课件=>
OI 课件=>
黄学长，请问cut的时候为什么不需要update?
黄学长，请问isroot()能不能这样判断：
bool isroot(int x) { return fa[ x ] > 0; }
不可以，lct维护的一堆splay中，只有1棵splay的根是0，其余的根指向上一条重边。
还有你说的有根树不会有什么问题吧。
可是您打了一个rev标记，那就是说每次makeroot()之后节点相对深度都会改变，根节点不会随之变化吗？
黄学长，请问您写的LCT如何处理有根树的问题？
6 1
1 2
2 3
3 4
1 5
4 6
/ 4 5
这组数据好像不大对啊0.0,为什么输出了3？（好像是5）
已更正
为什么这个地方不用dfs而是一个一个link就行？
随意QAQ
“其实这题不需要开long long。。。只要unsigned int，不然可能会T”是可怕
+1