fork download
copy 
  1. #include <cmath>
  2. #include <algorithm>
  3. #include <cstdlib>
  4. #include <queue>
  5. #include <fstream>
  6. #include <iostream>
  7. #include <cstdio>
  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.  
  14. using namespace std;
  15.  
  16. struct edge { int y, n; } e[MS*2]; int ec, f[MS];
  17. int tc, tl[MS*5], tr[MS*5], tn[MS*5], tlc[MS*5], trc[MS*5], tb[MS*5]; bool td[MS*5];
  18. int n, m, s[MS], d[MS], h[MS], c[MS], x, y, z, lc, rc, ans;
  19. int ln, lb[MS], lr[MS], ld[MS], ls[MS], lh[MS];
  20. char q[10];
  21.  
  22. void Cal(int o) { tn[o] = tn[tl[o]] + tn[tr[o]]; if (trc[tl[o]] == tlc[tr[o]]) tn[o]--; tlc[o] = tlc[tl[o]], trc[o] = trc[tr[o]]; }
  23.  
  24. void Down(int o) { if (td[o]) td[o] = 0, tn[tl[o]] = tn[tr[o]] = td[tl[o]] = td[tr[o]] = 1, tlc[tl[o]] = tlc[tr[o]] = trc[tl[o]] = trc[tr[o]] = tlc[o]; } 
  25.  
  26. void Search(int x, int n)
  27. {
  28. 	int o = f[x], m = 0, my = 0, y = e[o].y; s[x] = 1, d[x] = n;
  29. 	while (y) { if (y != h[x]) { h[y] = x; Search(y, n+1); s[x] += s[y]; if (m < s[y]) m = s[y], my = y; } o = e[o].n, y = e[o].y; }
  30. 	o = f[x], y = e[o].y;
  31. 	while (y) { if (y != h[x] && y != my) { ld[lb[y]] = n+1, ls[lb[y]] = lr[y], lh[lb[y]] = x; } o = e[o].n, y = e[o].y; }
  32. 	if (my) lb[x] = lb[my], lr[x] = lr[my]+1; else ln++, lb[x] = ln, lr[x] = 1;
  33. }
  34.  
  35. void Build(int l, int r, int o) { if (l == r) return; int m = (l+r)/2; tl[o] = ++tc; Build(l, m, tc); tr[o] = ++tc; Build(m+1, r, tc); }
  36.  
  37. void Edit(int l, int r, int o) 
  38. { 
  39. 	if (x <= l && r <= y) { tn[o] = td[o] = 1, tlc[o] = trc[o] = z; return; } 
  40. 	int m = (l+r)/2; Down(o);
  41. 	if (x <= m) Edit(l, m, tl[o]); if (m < y) Edit(m+1, r, tr[o]); Cal(o); 
  42. }
  43.  
  44. void QT(int l, int r, int o)
  45. {
  46. 	if (x <= l && r <= y) { ans += tn[o]; if (tlc[o] == lc) ans--; lc = trc[o]; return; }
  47. 	int m = (l+r)/2; Down(o);
  48. 	if (x <= m) QT(l, m, tl[o]); if (m < y) QT(m+1, r, tr[o]);
  49. }
  50.  
  51. void QAQ(int a, int b)
  52. {
  53. 	int k; lc = rc = -1;  while (lb[a] != lb[b])
  54. 	{
  55. 		if (ld[lb[a]] < ld[lb[b]]) k=a, a=b, b=k, k=lc, lc=rc, rc=k;
  56. 		x = lr[a], y = ls[lb[a]]; QT(1, ls[lb[a]], tb[lb[a]]); a = lh[lb[a]];
  57. 	}
  58. 	if (d[a] < d[b]) k=a, a=b, b=k, k=lc, lc=rc, rc=k;
  59. 	x = lr[a], y = lr[b]; QT(1, ls[lb[a]], tb[lb[a]]); if (lc == rc) ans--;
  60. }
  61.  
  62. void EditQ(int a, int b)
  63. {
  64. 	int k; while (lb[a] != lb[b])
  65. 	{
  66. 		if (ld[lb[a]] < ld[lb[b]]) k=a, a=b, b=k;
  67. 		x = lr[a], y = ls[lb[a]]; Edit(1, ls[lb[a]], tb[lb[a]]); a = lh[lb[a]];
  68. 	}
  69. 	if (d[a] < d[b]) k=a, a=b, b=k;
  70. 	x = lr[a], y = lr[b]; Edit(1, ls[lb[a]], tb[lb[a]]);
  71. }
  72.  
  73. int main()
  74. {
  75. 	scanf("%d%d", &n, &m);
  76. 	rep(i, 1, n) scanf("%d", &c[i]);
  77. 	rep(i, 1, n-1)
  78. 	{
  79. 		scanf("%d%d", &x, &y);
  80. 		ec++, e[ec].y = y, e[ec].n = f[x], f[x] = ec;
  81. 		ec++, e[ec].y = x, e[ec].n = f[y], f[y] = ec;
  82. 	}
  83. 	Search(1, 0); ld[lb[1]] = lh[lb[1]] = 0, ls[lb[1]] = lr[1];
  84. 	rep(i, 1, ln) { tb[i] = ++tc; Build(1, ls[i], tc); }
  85. 	rep(i, 1, n) { x = y = lr[i]; z = c[i]; Edit(1, ls[lb[i]], tb[lb[i]]); }
  86. 	rep(i, 1, m)
  87. 	{
  88. 		scanf("%s%d%d", q, &x, &y);
  89. 		if (q[0] == 'Q') { ans = 0; QAQ(x, y); printf("%d\n", ans); } else { scanf("%d", &z); EditQ(x, y); }
  90. 	}
  91. 	return 0;
  92. }
Success #stdin #stdout 0s 25128KB
comments (?)
stdin
copy 
6 11
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5
C 4 6 3
Q 3 6
C 2 5 4
Q 1 4
C 1 6 5
Q 3 5
stdout
copy 
3
1
2
3
3
3
https://ideone.com/tEutDp
BZOJ 2243
language:
C++ (gcc 8.3)
created:
9 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!