fork download 
  1. #include<iostream>
  2. #include<vector>
  3. #include <algorithm>
  4. #include <unordered_map>
  5. #include <cmath>
  6. using namespace std;
  7. #define ll long long
  8. const int pom = 524288;
  9. ll wyn[1048576];
  10. int n, q;
  11. void pus(int x)
  12. {
  13. 	if (x >= pom)return;
  14. 	wyn[2 * x] += wyn[x];
  15. 	wyn[2 * x + 1] += wyn[x];
  16. 	wyn[x] = 0;
  17. }
  18. void dod(ll a, int l, int p, int lll, int pp, int x)
  19. {
  20. 	pus(x);
  21. 	if (lll > p)return;
  22. 	if (pp < l)return;
  23. 	if (pp <= p and lll >= l) {
  24. 		wyn[x] += a;
  25. 		return;
  26. 	}
  27. 	dod(a, l, p, lll, (lll + pp - 1) / 2, 2 * x);
  28. 	dod(a, l, p, (lll + pp + 1) / 2, pp, 2 * x + 1);
  29. }
  30. ll oddp = 0;
  31. void odp(int x, int l, int p, int a)
  32. {
  33. 	pus(a);
  34. 	if (l > x)return;
  35. 	if (p < x)return;
  36. 	if (l == p & x == p)
  37. 	{
  38. 		oddp = wyn[a];
  39. 		return;
  40. 	}
  41. 	odp(x, l, (l + p - 1) / 2, a * 2);
  42. 	odp(x, (l + p + 1) / 2, p, a * 2 + 1);
  43. }
  44. int kto[pom];
  45. int zak[pom];
  46. int jump[pom][20];
  47. int gl[pom];
  48. vector<int>sas[pom];
  49. int num = 0;
  50. int dfs(int x)
  51. {
  52. 	int p = num;
  53. 	kto[x] = num;
  54. 	num++;
  55. 	for (int i = 0; i < sas[x].size(); i++)
  56. 	{
  57. 		if (sas[x][i] == jump[x][0])continue;
  58. 		jump[sas[x][i]][0] = x;
  59. 		gl[sas[x][i]] = gl[x] + 1;
  60. 		p = max(p, dfs(sas[x][i]));
  61. 	}
  62. 	zak[x] = p;
  63. 	return p;
  64. }
  65. void settup()
  66. {
  67. 	for (int i = 1; i < 19; i++)
  68. 	{
  69. 		for (int j = 1; j <= n; j++)
  70. 		{
  71. 			jump[i][j] = jump[jump[i][j - 1]][j - 1];
  72. 		}
  73. 	}
  74. }
  75. int lca(int a, int b)
  76. {
  77. 	if (gl[a] < gl[b])swap(a, b);
  78. 	for (int i = 18; i >= 0; i--)
  79. 	{
  80. 		if (gl[jump[a][i]] < gl[b])continue;
  81. 		a = jump[a][i];
  82. 	}
  83. 	if (a == b)return a;
  84. 	for (int i = 18; i >= 0; i--)
  85. 	{
  86. 		if (jump[a][i] == jump[b][i])continue;
  87. 		a = jump[a][i];
  88. 		b = jump[b][i];
  89. 	}
  90. 	return jump[a][0];
  91. }
  92. vector<vector<ll>>pomoc;
  93. ll odpowiedzi[pom];
  94. int main()
  95. {
  96. 	ios_base::sync_with_stdio(0);
  97. 	cin.tie(0);
  98. 	cin >> n >> q;
  99. 	jump[1][0] = 1;
  100. 	for (int i = 1; i < n; i++)
  101. 	{
  102. 		int a, b, c, d;
  103. 		cin >> a >> b >> c >> d;
  104. 		sas[a].push_back(b);
  105. 		sas[b].push_back(a);
  106. 		pomoc.push_back({ c,d,a,b });
  107. 	}
  108. 	dfs(1);
  109. 	settup();
  110. 	for (int i = 0; i < q; i++)
  111. 	{
  112. 		int a, b, c;
  113. 		cin >> a >> b >> c;
  114. 		pomoc.push_back({ c,10000000000,b,a,i });
  115. 	}
  116. 	sort(pomoc.begin(), pomoc.end());
  117. 	for (int i = 0; i < pomoc.size(); i++)
  118. 	{
  119. 		if (pomoc[i].size() == 4)
  120. 		{
  121. 			int pp = pomoc[i][2];
  122. 			if (gl[pomoc[i][3]] > gl[pp])pp = pomoc[i][3];
  123. 			dod(pomoc[i][1], kto[pp], zak[pp], 0, pom - 1,1);
  124. 		}
  125. 		else
  126. 		{
  127. 			ll wyn = 0;
  128. 			oddp = 0;
  129. 			odp(kto[pomoc[i][2]], 0, pom - 1, 1);
  130. 			wyn += oddp;
  131. 			odp(kto[pomoc[i][3]], 0, pom - 1, 1);
  132. 			wyn += oddp;
  133. 			odp(kto[lca(pomoc[i][3], pomoc[i][2])], 0, pom - 1, 1);
  134. 			wyn -= 2 * oddp;
  135. 			odpowiedzi[pomoc[i][4]] = wyn;
  136. 		}
  137. 	}
  138. 	for (int i = 0; i < q; i++)
  139. 	{
  140. 		cout << odpowiedzi[i] << "\n";
  141. 	}
  142. }
Success #stdin #stdout 0.01s 17988KB
comments (?)
stdin 
19 1
2 1 1 1
3 2 1 1
4 3 1 1
5 4 1 1
6 5 1 1
7 6 1 1
8 7 1 1
9 8 1 1
10 9 1 1
11 10 1 1
12 11 1 1
13 12 1 1
14 13 1 1
15 14 1 1
16 15 1 1
17 16 1 1
18 17 1 1
19 18 1 1
2 19 1
stdout 
19
https://ideone.com/n60lMx
language:
C++ (gcc 8.3)
created:
6 days 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!