fork download
copy 
  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <iostream>
  7. #include <fstream>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 34567
  13. #define MAX 1037471823
  14.  
  15. using namespace std;
  16.  
  17. struct node { int l, r, s, m, lch, rch; };
  18. struct edge { int n, next; };
  19.  
  20. node nd[MS*5]; int t[MS], nc;
  21. edge e[MS*2]; int fir[MS], ec;
  22. int f[MS], s[MS], pt[MS], pd[MS], ps[MS], pc, be[MS], r[MS];
  23. int n, w[MS], a, b, q;
  24. char qt[123];
  25.  
  26. void Init()
  27. {
  28. 	int x, y;
  29. 	scanf("%d", &n);
  30. 	rep(i, 1, n-1)
  31. 	{
  32. 		scanf("%d%d", &x, &y);
  33. 		ec++; e[ec].n = y; e[ec].next = fir[x]; fir[x] = ec;
  34. 		ec++; e[ec].n = x; e[ec].next = fir[y]; fir[y] = ec;
  35. 	}
  36. 	rep(i, 1, n) scanf("%d", &w[i]);
  37. }
  38.  
  39. void DFS(int x, int o)
  40. {
  41. 	o++; int p, a, b, m, ma;
  42. 	p = fir[x]; s[x] = 1; m = 0;
  43. 	while (p)
  44. 	{
  45. 		if (e[p].n != f[x])
  46. 		{
  47. 			a = e[p].n; 
  48. 			f[a] = x; DFS(a, o); s[x] += s[a];
  49. 			if (s[a] > m) m = s[a], ma = a;
  50. 		}
  51. 		p = e[p].next;
  52. 	}
  53. 	p = fir[x]; be[x] = 0;
  54. 	while (p)
  55. 	{
  56. 		if (e[p].n != f[x])
  57. 		{
  58. 			if (e[p].n == ma) be[x] = be[ma], r[x] = r[ma]+1; else 
  59. 			{
  60. 				a = e[p].n; b = be[a];
  61. 				pd[b] = o; ps[b] = r[a]; pt[b] = a;
  62. 			}
  63. 		}
  64. 		p = e[p].next;
  65. 	}
  66. 	if (be[x] == 0) be[x] = ++pc, r[x] = 1;
  67. }
  68.  
  69. void Build(int p, int l, int r)
  70. {
  71. 	nd[p].l = l, nd[p].r = r;
  72. 	if (r-l > 0)
  73. 	{
  74. 		nd[p].lch = ++nc; Build(nd[p].lch, l, (l+r)/2);
  75. 		nd[p].rch = ++nc; Build(nd[p].rch, (l+r)/2+1, r);
  76. 	}
  77. 	else nd[p].lch = nd[p].rch = 0;
  78. }
  79.  
  80. void Change(int p, int x, int d)
  81. {
  82. 	if (nd[p].l == nd[p].r) nd[p].s = nd[p].m = d;
  83. 	else 
  84. 	{
  85. 		if (x <= (nd[p].l + nd[p].r) / 2) Change(nd[p].lch, x, d); else Change(nd[p].rch, x, d);
  86. 		nd[p].m = max(nd[nd[p].lch].m, nd[nd[p].rch].m);
  87. 		nd[p].s = nd[nd[p].lch].s + nd[nd[p].rch].s;
  88. 	}
  89. }
  90.  
  91. void Prepare()
  92. {
  93. 	pc = f[1] = 0;
  94. 	DFS(1, 0); 
  95. 	pd[be[1]] = 0; ps[be[1]] = r[1]; pt[be[1]] = 1;
  96. 	rep(i, 1, pc)
  97. 	{
  98. 		t[i] = ++nc;
  99. 		Build(nc, 1, ps[i]);
  100. 	}
  101. 	rep(i, 1, n) Change(t[be[i]], r[i], w[i]);
  102. }
  103.  
  104. int Asksum(int p, int x, int y)
  105. {
  106. 	if (x <= nd[p].l && nd[p].r <= y) return nd[p].s;
  107. 	int ans = 0; 
  108. 	if (x <= (nd[p].l + nd[p].r) / 2) ans += Asksum(nd[p].lch, x, y);
  109. 	if ((nd[p].l + nd[p].r) / 2+1 <= y) ans += Asksum(nd[p].rch, x, y);
  110. 	return ans;
  111. }
  112.  
  113. int Askmax(int p, int x, int y)
  114. {
  115. 	if (x <= nd[p].l && nd[p].r <= y) return nd[p].m;
  116. 	int ans = -MAX; 
  117. 	if (x <= (nd[p].l + nd[p].r) / 2) ans = max(ans, Askmax(nd[p].lch, x, y));
  118. 	if ((nd[p].l + nd[p].r) / 2+1 <= y) ans = max(ans, Askmax(nd[p].rch, x, y));
  119. 	return ans;
  120. }
  121.  
  122. int Qsum(int a, int b)
  123. {
  124. 	int ans = 0, x = be[a], y = be[b];
  125. 	while (x != y)
  126. 	{
  127. 		if (pd[x] > pd[y])
  128. 		{
  129. 			ans += Asksum(t[x], r[a], ps[x]);
  130. 			a = f[pt[x]]; x = be[a];
  131. 		}
  132. 		else
  133. 		{
  134. 			ans += Asksum(t[y], r[b], ps[y]);
  135. 			b = f[pt[y]]; y = be[b];
  136. 		}
  137. 	}
  138. 	ans += Asksum(t[x], min(r[a], r[b]), max(r[a], r[b]));
  139. 	return ans;
  140. }
  141.  
  142. int Qmax(int a, int b)
  143. {
  144. 	int ans = -MAX, x = be[a], y = be[b];
  145. 	while (x != y)
  146. 	{
  147. 		if (pd[x] > pd[y])
  148. 		{
  149. 			ans = max(ans, Askmax(t[x], r[a], ps[x]));
  150. 			a = f[pt[x]]; x = be[a];
  151. 		}
  152. 		else
  153. 		{
  154. 			ans = max(ans, Askmax(t[y], r[b], ps[y]));
  155. 			b = f[pt[y]]; y = be[b];
  156. 		}
  157. 	}
  158. 	ans = max(ans, Askmax(t[x], min(r[a], r[b]), max(r[a], r[b])));
  159. 	return ans;
  160. }
  161.  
  162. int main()
  163. {
  164. 	Init();
  165. 	Prepare();
  166. 	scanf("%d", &q);
  167. 	rep(i, 1, q)
  168. 	{
  169. 		scanf("%s%d%d", qt, &a, &b);
  170. 		if (qt[1] == 'M') printf("%d\n", Qmax(a, b));
  171. 		else if (qt[1] == 'S') printf("%d\n", Qsum(a, b));
  172. 		else if (qt[1] == 'H') { w[a] = b; Change(t[be[a]], r[a], b); }
  173. 	}
  174. 	return 0;
  175. }
Success #stdin #stdout 0s 9248KB
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/xJheIb
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!