fork download
copy 
  1. #include <cstring>
  2. #include <cmath>
  3. #include <cstdlib>
  4. #include <cstdio>
  5. #include <algorithm>
  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 99999
  12. #define MAX 1037471823
  13. #define Q 1
  14.  
  15. using namespace std;
  16.  
  17. struct edge { int y, n; } e[MS]; int ec, f[MS];
  18. int tl[MS], tr[MS], ts[MS], tn[MS], tc, tb[MS];
  19. int lb[MS], ld[MS], lr[MS], ls[MS], lh[MS], ln;
  20. int n, w[MS], s[MS], d[MS], h[MS], m, x, y, ans;
  21. char q[10];
  22.  
  23. void Search(int x, int n)
  24. {
  25. 	int o = f[x], m = 0, my = 0, y = e[o].y; s[x] = 1; d[x] = n;
  26. 	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; }
  27. 	o = f[x], y = e[o].y; while (y) { if (y != h[x] && y != my) { ls[lb[y]] = lr[y], ld[lb[y]] = n+1, lh[lb[y]] = x; } o = e[o].n, y = e[o].y; }
  28. 	if (my) lb[x] = lb[my], lr[x] = lr[my] + 1; else ln++, lb[x] = ln, lr[x] = 1; 
  29. }
  30.  
  31. 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); }
  32.  
  33. void Edit(int x, int l, int r, int o) 
  34. { 
  35. 	if (l == r) ts[o] = tn[o] = w[x]; 
  36. 	else 
  37. 	{ 
  38. 		int m = (l+r) / 2; 
  39. 		if (lr[x] <= m) Edit(x, l, m, tl[o]); else Edit(x, m+1, r, tr[o]);
  40. 		ts[o] = ts[tl[o]] + ts[tr[o]]; tn[o] = max(tn[tl[o]], tn[tr[o]]);
  41. 	} 
  42. }
  43.  
  44. void TQMax(int l, int r, int o) { if (x <= l && r <= y) ans = max(ans, tn[o]); else { int m = (l+r)/2; if (x <= m) TQMax(l, m, tl[o]); if (m+1 <= y) TQMax(m+1, r, tr[o]); } }
  45.  
  46. void TQSum(int l, int r, int o) { if (x <= l && r <= y) ans += ts[o]; else { int m = (l+r)/2; if (x <= m) TQSum(l, m, tl[o]); if (m+1 <= y) TQSum(m+1, r, tr[o]); } }
  47.  
  48. void QMax(int a, int b)
  49. {
  50. 	while (lb[a] != lb[b]) 
  51. 		{ if (ld[lb[a]] <= ld[lb[b]]) x = a, a = b, b = x; x = lr[a], y = ls[lb[a]]; TQMax(1, ls[lb[a]], tb[lb[a]]); a = lh[lb[a]]; }
  52. 	x = min(lr[a], lr[b]); y = max(lr[a], lr[b]); TQMax(1, ls[lb[a]], tb[lb[a]]);
  53. }
  54.  
  55. void QSum(int a, int b)
  56. {
  57. 	while (lb[a] != lb[b]) 
  58. 		{ if (ld[lb[a]] <= ld[lb[b]]) x = a, a = b, b = x; x = lr[a], y = ls[lb[a]]; TQSum(1, ls[lb[a]], tb[lb[a]]); a = lh[lb[a]]; }
  59. 	x = min(lr[a], lr[b]); y = max(lr[a], lr[b]); TQSum(1, ls[lb[a]], tb[lb[a]]);
  60. }
  61.  
  62. int main()
  63. {
  64. 	scanf("%d", &n);
  65. 	rep(i, 1, n-1) 
  66. 		{ scanf("%d%d", &x, &y); e[++ec].y = y, e[ec].n = f[x], f[x] = ec, e[++ec].y = x, e[ec].n = f[y], f[y] = ec; }	
  67. 	rep(i, 1, n) scanf("%d", &w[i]);
  68. 	Search(1, 0); ls[lb[1]] = lr[1], ld[lb[1]] = 0, lh[lb[1]] = 0;
  69. 	rep(i, 1, ln) { tb[i] = ++tc; Build(1, ls[i], tb[i]); } tn[0] = -MAX;
  70. 	rep(i, 1, n) Edit(i, 1, ls[lb[i]], tb[lb[i]]);
  71. 	scanf("%d", &m); rep(i, 1, m) 
  72. 	{
  73. 		scanf("%s%d%d", q, &x, &y);
  74. 		if (q[1] == 'M') { ans = -MAX; QMax(x, y); printf("%d\n", ans); }
  75. 		else if (q[1] == 'S') { ans = 0; QSum(x, y); printf("%d\n", ans); }
  76. 		else { w[x] = y; Edit(x, 1, ls[lb[x]], tb[lb[x]]); }
  77. 	}
  78. }
Success #stdin #stdout 0s 9992KB
comments (?)
stdin
copy 
4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4
stdout
copy 
4
1
2
2
10
6
5
6
5
16
https://ideone.com/ly11Qf
BZOJ 1036
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!