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. // Với mỗi cạnh, ta cần biết được có bao nhiêu đường đi đi qua cạnh này
  12. // Với mỗi đường đi 1 -> 2, 2 -> 3, 3 -> 4, ..., n - 1 -> n, update các cạnh có trên đường đi
  13.  
  14. const int N = 2e5 + 5;  
  15. const int LOG = 18;  
  16.  
  17. struct AdjEdge {
  18. 	int to, id;  
  19. }; 
  20.  
  21. int n;  
  22. vector<AdjEdge> adj[N];  
  23. ll c1[N]; // c1[i] = Giá vé đi 1 lần của cạnh thứ i 
  24. ll c2[N]; // c2[i] = Giá vé đi nhiều lần của cạnh thứ i
  25.  
  26. int up[LOG][N]; 
  27. int tin[N], tout[N], timer;   
  28. int edge_to_node[N]; // edge_to_node[i] = Đỉnh đại diện cho cạnh thứ i 
  29.  
  30. void dfs1(int u, int p) {
  31. 	tin[u] = ++timer;   
  32. 	up[0][u] = p;   
  33. 	for (int i = 1; i < LOG; i++) {
  34. 		up[i][u] = up[i - 1][up[i - 1][u]]; 
  35. 	}
  36. 	for (auto e : adj[u]) {
  37. 		int v = e.to, id = e.id;
  38. 		if (v == p) continue;  
  39. 		edge_to_node[id] = v;   
  40. 		dfs1(v, u); 
  41. 	}
  42. 	tout[u] = timer; 
  43. }
  44.  
  45. bool isAncestor(int u, int v) {
  46. 	return (tin[u] <= tin[v] && tout[v] <= tout[u]); 
  47. }
  48.  
  49. int lca(int u, int v) {
  50. 	if (isAncestor(u, v)) return u;  
  51. 	if (isAncestor(v, u)) return v;   
  52. 	for (int i = LOG - 1; i >= 0; i--) {
  53. 		if (!isAncestor(up[i][u], v)) {
  54. 			u = up[i][u]; 
  55. 		}
  56. 	}
  57. 	return up[0][u]; 
  58. }
  59.  
  60. int sum[N]; 
  61.  
  62. void dfs2(int u, int p) {
  63. 	for (auto e : adj[u]) {
  64. 		int v = e.to; 
  65. 		if (v == p) continue; 
  66. 		dfs2(v, u);  
  67. 		sum[u] += sum[v]; 
  68. 	}
  69. }
  70.  
  71. int main() {
  72. 	ios::sync_with_stdio(false); 
  73. 	cin.tie(nullptr); 	
  74. 	cin >> n; 
  75. 	for (int i = 0; i < n - 1; i++) {
  76. 		int u, v; 
  77. 		cin >> u >> v >> c1[i] >> c2[i]; 
  78. 		adj[u].push_back({v, i}); 
  79. 		adj[v].push_back({u, i});
  80. 	}
  81.  
  82. 	timer = 0;   
  83. 	dfs1(1, 1); 
  84.  
  85. 	for (int u = 1; u + 1 <= n; u++) {
  86. 		int v = u + 1;  
  87. 		sum[u]++; 
  88. 		sum[v]++; 
  89. 		sum[lca(u, v)] -= 2;  
  90. 	}
  91.  
  92. 	dfs2(1, 1); 
  93.  
  94. 	ll ans = 0;  
  95. 	for (int i = 0; i < n - 1; i++) {
  96. 		int u = edge_to_node[i]; 
  97. 		ans += min(sum[u] * c1[i], c2[i]); 
  98. 	}
  99.  
  100. 	cout << ans << '\n'; 
  101. }
Success #stdin #stdout 0.01s 26808KB
comments (?)
stdin
copy 
4
1 2 3 5
1 3 2 4
2 4 1 3
stdout
copy 
10
https://ideone.com/Zce2gg
language:
C++14 (gcc 8.3)
created:
173 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!