fork download 
  1. #include <cmath>
  2. #include <cstdlib>
  3. #include <cstdio>
  4. #include <algorithm>
  5. #include <queue>
  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. struct node{int y, n;} e[MS*2]; int ec, f[MS];
  16. int n, m, l[MS], r[MS], h[MS], s[MS], ph[MS], x, y, z;
  17. unsigned int k[MS], a[MS], c[MS], sum[MS];
  18. bool rev[MS];
  19. char q[10];
  20.  
  21. using namespace std;
  22.  
  23. inline void Cal(int x) { if (!x) return; s[x] = s[l[x]] + s[r[x]] + 1, sum[x] = (((sum[l[x]]+sum[r[x]]+k[x])%Q*c[x])%Q+(a[x]*(s[x]%Q))%Q)%Q; }
  24.  
  25. inline void Down(int x) 
  26. { 
  27. 	if (rev[x]) { int k; k = l[x], l[x] = r[x], r[x] = k, rev[x]^=1, rev[l[x]]^=1, rev[r[x]]^=1; } 
  28. 	k[x] = (k[x]*c[x]+a[x])%Q; c[l[x]] = (c[l[x]]*c[x])%Q; c[r[x]] = (c[r[x]]*c[x])%Q; a[l[x]] = (a[l[x]]*c[x]+a[x])%Q; a[r[x]] = (a[r[x]]*c[x]+a[x])%Q;
  29. 	a[x] = 0, c[x] = 1;
  30. 	Cal(l[x]); Cal(r[x]); Cal(x);
  31. }
  32.  
  33. inline void Splay(int x)
  34. {
  35. 	if (!x) return; int o = h[x], rr = s[l[x]];
  36. 	while (o) { if (r[o] == x) rr += s[l[o]]+1; x = o, o = h[x]; }
  37. 	while (rr != s[l[x]]) { if (rr < s[l[x]]) o = l[x]; else rr -= s[l[x]]+1, o = r[x]; Down(x); x = o; } Down(x);
  38. 	o = h[x]; while (o)
  39. 	{
  40. 		if (!h[o]) ph[x] = ph[o], ph[o] = 0;
  41. 		if (l[o] == x) { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o]; l[o] = r[x]; h[r[x]] = o; h[o] = x; r[x] = o; Cal(o); }
  42. 		else { l[h[o]] == o ? l[h[o]] = x : r[h[o]] = x; h[x] = h[o]; r[o] = l[x]; h[l[x]] = o; h[o] = x; l[x] = o; Cal(o); }
  43. 		o = h[x];
  44. 	}
  45. 	Cal(x);
  46. }
  47.  
  48. void Search(int x)
  49. {
  50. 	int o = f[x], y = e[o].y, m = 0, my = 0; s[x] = 1;
  51. 	while (y) { if (y != h[x]) { h[y] = x; Search(y); if (m < s[y]) m = s[y], my = y; h[y] = 0; } o = e[o].n, y = e[o].y; }
  52. 	r[x] = my; h[my] = x; Cal(x);
  53. 	o = f[x], y = e[o].y; 
  54. 	while (y) { if (y != h[x] && y != my) ph[y] = x; o = e[o].n, y = e[o].y; }
  55. }
  56.  
  57. inline void Acc(int x)
  58. {
  59. 	int o = 0; 
  60. 	while (x) { Splay(x); ph[r[x]] = x, h[r[x]] = 0, r[x] = o; if (o) h[o] = x, ph[o] = 0; Cal(x); o = x; x = ph[x]; }
  61. }
  62.  
  63. inline void Evert(int x) { Acc(x); Splay(x); rev[x]^=1; }
  64.  
  65. inline void Cut(int x, int y) { Evert(x); Acc(y); Splay(y); h[x] = l[y] = 0; Cal(y); }
  66.  
  67. inline void Link(int x, int y) { Evert(x); Splay(y); ph[r[y]] = y, h[r[y]] = 0, r[y] = x, h[x] = y; Cal(y);}
  68.  
  69. inline void Add(int x, int y, int z) { Evert(x); Acc(y); Splay(y); a[y] = (a[y] + z) % Q; Cal(y); }
  70.  
  71. inline void Mult(int x, int y, int z) { Evert(x); Acc(y); Splay(y); c[y] = (c[y] * z) % Q; a[y] *= z; a[y] %= Q; Cal(y); }
  72.  
  73. inline void QSum(int x, int y) { Evert(x); Acc(y); Splay(y); printf("%d\n", sum[y]%Q); }
  74.  
  75. int main()
  76. {
  77. 	scanf("%d%d", &n, &m);
  78. 	rep(i, 1, n) s[i] = k[i] = c[i] = sum[i] = 1;
  79. 	rep(i, 1, n-1)
  80. 	{
  81. 		scanf("%d%d", &x, &y);
  82. 		ec++, e[ec].y = y, e[ec].n = f[x], f[x] = ec;
  83. 		ec++, e[ec].y = x, e[ec].n = f[y], f[y] = ec;
  84. 	}
  85. 	Search(1);
  86. 	rep(i, 1, m)
  87. 	{
  88. 		scanf("%s", q);
  89. 		if (q[0] == '+') { scanf("%d%d%d", &x, &y, &z); Add(x, y, z); }
  90. 		else if (q[0] == '-') { scanf("%d%d", &x, &y); Cut(x, y); scanf("%d%d", &x, &y); Link(x, y); }
  91. 		else if (q[0] == '*') { scanf("%d%d%d", &x, &y, &z); Mult(x, y, z); }
  92. 		else { scanf("%d%d", &x, &y); QSum(x, y); }
  93. 	}
  94. 	return 0;
  95. }
Success #stdin #stdout 0s 10232KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/lf2lRZ
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!