fork download
copy 
  1. #include <cmath>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <map>
  6. #include <fstream>
  7. #include <iostream>
  8.  
  9. #define rep(i, l, r) for(int i = l; i <= r; i++)
  10. #define down(i, l, r) for(int i = l; i >= r; i--)
  11. #define MS 123456
  12. #define MAX 1037471823
  13. #define Q 51061
  14.  
  15. using namespace std;
  16.  
  17. struct node { node *ch[2], *h; bool rec; unsigned int sum, k, a, c, s, n;
  18. inline bool d();
  19. inline bool Root();
  20. inline void Cal();
  21. inline void Down();
  22. } t[MS];
  23.  
  24. inline bool node::d() { return h->ch[1]==this; }
  25.  
  26. inline bool node::Root() { return (h==NULL) || (h->ch[1]!=this && h->ch[0]!=this); }
  27.  
  28. inline void node::Down() 
  29. {
  30. 	if (!this) return;
  31. 	if (rec) 
  32. 	{
  33. 		if (ch[0]) ch[0]->rec^=1;
  34. 		if (ch[1]) ch[1]->rec^=1;
  35. 		swap(ch[0], ch[1]); rec=0;
  36. 	}
  37. 	k=(k*c+a)%Q; 
  38. 	if (ch[0]) ch[0]->c=(ch[0]->c*c)%Q, ch[0]->a=(ch[0]->a*c+a)%Q;
  39. 	if (ch[1]) ch[1]->c=(ch[1]->c*c)%Q, ch[1]->a=(ch[1]->a*c+a)%Q;
  40. 	a=0, c=1; ch[0]->Cal(); ch[1]->Cal(); Cal();
  41. }
  42.  
  43. inline void node::Cal()
  44. {
  45. 	if (!this) return; 
  46. 	s=1; if (ch[0]) s+=ch[0]->s; if (ch[1]) s+=ch[1]->s;
  47. 	sum=k; if (ch[0]) sum+=ch[0]->sum; if (ch[1]) sum+=ch[1]->sum; sum=((sum%Q*c)%Q+(s%Q*a)%Q)%Q;
  48. }
  49.  
  50. inline void Rotate(node *x) 
  51. {
  52. 	node *o=x->h; o->Down(); x->Down();
  53. 	bool d=x->d();
  54. 	if (!o->Root()) o->h->ch[o->d()]=x;
  55. 	x->h=o->h;
  56. 	if (x->ch[d^1]) x->ch[d^1]->h=o;
  57. 	o->ch[d]=x->ch[d^1];
  58. 	x->ch[d^1]=o;
  59. 	o->h=x;
  60. 	o->Cal(); x->Cal();
  61. }
  62.  
  63. inline void Splay(node *x) 
  64. {
  65. 	x->Down();
  66. 	while (!x->Root())
  67. 	{
  68. 		if (x->h->Root()) Rotate(x);
  69. 		else if (x->d()!=x->h->d()) Rotate(x), Rotate(x);
  70. 		else Rotate(x->h), Rotate(x);
  71. 	}
  72. 	x->Cal();
  73. }
  74.  
  75. inline node* Acc(node *x) 
  76. {
  77. 	node *o;
  78. 	for (o=NULL; x; o=x, x=x->h)
  79. 		{ Splay(x); x->ch[1]=o; x->Cal(); }
  80. 	return o;
  81. }
  82. inline void Evert(node *x) { Acc(x)->rec^=1; Splay(x); }
  83. inline void Link(node *x, node *y) { Evert(x); x->h=y; Acc(x); }
  84. inline void Cut(node *x, node *y) { Evert(x); Acc(y); Splay(y); y->ch[0]=x->h=NULL; y->Cal(); x->Cal(); }
  85. inline void Add(node *x, node *y, int z) { Evert(x); Acc(y); Splay(y); y->a=(y->a+z)%Q; y->Cal(); }
  86. inline void Mult(node *x, node *y, int z) { Evert(x); Acc(y); Splay(y);  y->c=(y->c*z)%Q; y->Cal(); }
  87. inline void QSum(node *x, node *y) { Evert(x); Acc(y); Splay(y); printf("%d\n", y->sum); }
  88.  
  89. int n, m, x, y, z;
  90. char q[10];
  91.  
  92. int main()
  93. {
  94. 	scanf("%d%d", &n, &m);
  95. 	rep(i, 1, n) t[i].rec=false, t[i].h=t[i].ch[0]=t[i].ch[1]=NULL, t[i].sum=t[i].k=t[i].c=t[i].s=1, t[i].a=0, t[i].n=i;
  96. 	rep(i, 1, n-1) { scanf("%d%d", &x, &y); Link(&t[x], &t[y]); }
  97. 	rep(i, 1, m)
  98. 	{
  99. 		scanf("%s", q);
  100. 		if (q[0] == '+') { scanf("%d%d%d", &x, &y, &z); Add(&t[x], &t[y], z); }
  101. 		else if (q[0] == '-') { scanf("%d%d", &x, &y); Cut(&t[x], &t[y]); scanf("%d%d", &x, &y); Link(&t[x], &t[y]); }
  102. 		else if (q[0] == '*') { scanf("%d%d%d", &x, &y, &z); Mult(&t[x], &t[y], z); }
  103. 		else { scanf("%d%d", &x, &y); QSum(&t[x], &t[y]); }
  104. 	}
  105. 	return 0;
  106. }
Success #stdin #stdout 0s 8176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/zsQdHR
BZOJ 2631 LCT（指针写残版）
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!