fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. // - Nhận xét: dist(u, v, x, y) = dist(1, u, x, y) + dist(1, v, x, y) - 2 * dist(1, lca(u, v), x, y)
  12. // => Với mọi truy vấn (u, v, x, y) ban đầu ta đều có thể biến đổi thành các truy vấn có dạng (1, i, x, y),
  13. //    và mỗi truy vấn (1, i, x, y) sẽ đi kèm với hệ số nhân thêm (coef) khi đóng góp vào đáp án của truy vấn ban đầu
  14. // - Ngoài ra việc trả lời các truy vấn (1, i, x, y) cũng sẽ dễ dàng hơn, ta có thể thiết kế dfs sao cho khi dfs đến i thì ta cũng có được thông tin (cnt[c], sum[c]) của đường đi từ 1 đến i
  15.  
  16. const int N = 1e5 + 5; 
  17. const int Q = 1e5 + 5;  
  18. const int LOG = 17;   
  19.  
  20. struct AdjEdge {
  21. 	int to, c, w;  
  22. }; 
  23.  
  24. int n, q;  
  25. vector<AdjEdge> adj[N]; 
  26.  
  27. ll dist[N]; // dist[u] = Khoảng cách từ 1 đến u ở cây ban đầu
  28. int up[LOG][N]; 
  29. int tin[N], tout[N], timer;  
  30.  
  31. void dfs1(int u, int p) {
  32. 	tin[u] = ++timer;  
  33. 	up[0][u] = p;   
  34. 	for (int i = 1; i < LOG; i++) {
  35. 		up[i][u] = up[i - 1][up[i - 1][u]]; 
  36. 	}
  37. 	for (auto e : adj[u]) {
  38. 		int v = e.to; 
  39. 		if (v == p) continue; 
  40. 		dist[v] = dist[u] + e.w; 
  41. 		dfs1(v, u);  
  42. 	}
  43. 	tout[u] = timer; 
  44. }
  45.  
  46. bool isAncestor(int u, int v) {
  47. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]); 
  48. }
  49.  
  50. int lca(int u, int v) {
  51. 	if (isAncestor(u, v)) return u; 
  52. 	if (isAncestor(v, u)) return v;  
  53. 	for (int i = LOG - 1; i >= 0; i--) {
  54. 		if (!isAncestor(up[i][u], v)) {
  55. 			u = up[i][u]; 
  56. 		}
  57. 	}
  58. 	return up[0][u]; 
  59. }
  60.  
  61. struct Query {
  62. 	int x, y, coef, idx;  
  63. }; 
  64.  
  65. vector<Query> queries[N]; // queries[u] = Danh sách các truy vấn ở đỉnh u  
  66. int cnt[N]; // cnt[c] = Số cạnh có màu c
  67. ll sum[N]; // sum[c] = Tổng trọng số của những cạnh có màu c
  68. ll ans[Q]; // ans[i] = Đáp án của truy vấn thứ i 
  69.  
  70. void dfs2(int u, int p) {
  71. 	// Khi dfs đến u thì ta có luôn thông tin của đường đi từ 1 đến u 
  72. 	for (Query q : queries[u]) {
  73. 		ans[q.idx] += q.coef * (dist[u] - sum[q.x] + 1ll * cnt[q.x] * q.y); 
  74. 	}
  75.  
  76. 	for (auto &e : adj[u]) {
  77. 		int v = e.to;  
  78. 		if (v == p) continue; 
  79. 		// Thêm thông tin của cạnh (u, v) rồi sau đó gọi dfs vào v
  80. 		cnt[e.c]++;  
  81. 		sum[e.c] += e.w; 
  82. 		dfs2(v, u); 
  83. 		// Khi quay lui từ v lên u thì ta loại bỏ đi thông tin của cạnh (u, v)
  84. 		cnt[e.c]--; 
  85. 		sum[e.c] -= e.w; 
  86. 	}
  87. }
  88.  
  89. int main() {
  90. 	ios::sync_with_stdio(false); 
  91. 	cin.tie(nullptr); 	
  92. 	cin >> n >> q; 
  93. 	for (int i = 0; i < n - 1; i++) {
  94. 		int u, v, c, w;  
  95. 		cin >> u >> v >> c >> w; 
  96. 		adj[u].push_back({v, c, w}); 
  97. 		adj[v].push_back({u, c, w}); 
  98. 	}
  99.  
  100. 	timer = 0; 
  101. 	dfs1(1, 1); 
  102.  
  103. 	for (int i = 0; i < q; i++) {
  104. 		int x, y, u, v; 
  105. 		cin >> x >> y >> u >> v; 
  106. 		queries[u].push_back({x, y, 1, i});
  107. 		queries[v].push_back({x, y, 1, i});
  108. 		queries[lca(u, v)].push_back({x, y, -2, i}); 
  109. 	}
  110.  
  111. 	dfs2(1, 1);  
  112.  
  113. 	for (int i = 0; i < q; i++) {
  114. 		cout << ans[i] << '\n'; 
  115. 	}
  116. }
Success #stdin #stdout 0.01s 17880KB
comments (?)
stdin
copy 
5 3
1 2 1 10
1 3 2 20
2 4 4 30
5 2 1 40
1 100 1 4
1 100 1 5
3 1000 3 4
stdout
copy 
130
200
60
https://ideone.com/X4ZYc2
language:
C++14 (gcc 8.3)
created:
174 days ago
visibility:
secret

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!