fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pb push_back
  6. #define orta (bas + son >> 1)
  7. #define sag (k + k + 1)
  8. #define sol (k + k)
  9. #define endl '\n'
  10. #define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
  11. #define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
  12. #define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
  13. #define mp make_pair
  14. #define nd second
  15. #define st first
  16. #define type(x) __typeof(x.begin())
  17.  
  18. typedef pair < int ,int > pii;
  19.  
  20. typedef long long ll;
  21.  
  22. const long long linf = 1e15+5;
  23. const int mod = (int) 1e9 + 7;
  24. const int logN = 17;
  25. const int inf = 1e9;
  26. const int N = 1e6 + 5;
  27.  
  28. int n, m, x, y, z, c[N], start[N], finish[N], w[N], T;
  29. vector< int > v[N], add[N], del[N];
  30. ll dp[N], ST[N << 2], L[N << 2]; 
  31.  
  32. void dfs(int node, int root) {
  33. 	start[node] = T + 1;
  34. 	foreach(it, add[node]) w[*it] = ++T;
  35. 	foreach(it, v[node]) {
  36. 		if(*it != root) {
  37. 			dfs(*it, node);
  38. 		}
  39. 	} finish[node] = T;
  40. }
  41.  
  42. ll update(int k, int bas, int son, int x, ll D) {
  43. 	if(bas > x || son < x) return ST[k];
  44. 	if(bas == son) return ST[k] = D;
  45. 	ST[k] = min(update(sol, bas, orta, x, D), update(sag, orta + 1, son, x, D)) + L[k];
  46.     if(ST[k] > linf) ST[k] = linf;
  47. 	return ST[k];
  48.  
  49. }
  50.  
  51. ll update(int k, int bas, int son, int x, int y, ll D) {
  52. 	if(bas > y || son < x) return ST[k];
  53. 	if(x <= bas && son <= y) {
  54. 		L[k] = min(linf, D + L[k]);
  55. 		ST[k] = min(linf, D + ST[k]);
  56. 		return ST[k];
  57. 	}
  58. 	ST[k] = min(update(sol, bas, orta, x, y, D), update(sag, orta + 1, son, x, y, D)) + L[k];
  59. 	if(ST[k] > linf) ST[k] = linf;
  60. 	return ST[k];
  61. }
  62.  
  63. ll query(int k, int bas, int son, int x, int y) {
  64. 	if(bas > y || son < x) return linf;
  65. 	if(x <= bas && son <= y) return ST[k];
  66. 	return min(linf, min(query(sol, bas, orta, x, y), query(sag, orta + 1, son, x, y)) + L[k]);
  67. }
  68.  
  69. ll solve(int node, int root) {
  70. 	ll all = 0;
  71. 	foreach(it, v[node]) {
  72. 		if(*it == root) continue;
  73. 		all += solve(*it, node);
  74. 		if(all != 2 * linf)
  75. 		    all = min(all, 2 * linf);
  76. 	}
  77. 	if(node == 1) return dp[node] = all;
  78. 	foreach(it, add[node]) update(1, 1, m, w[*it], c[*it] + all);	
  79. 	foreach(it, del[node]) update(1, 1, m, w[*it], linf);	
  80. 	foreach(it, v[node])
  81. 		if(*it != root)
  82. 			update(1, 1, m, start[*it], finish[*it], all - dp[*it]);
  83. 	dp[node] = query(1, 1, m, start[node], finish[node]);
  84. 	return dp[node];
  85. }
  86.  
  87. int main() {
  88.  
  89. 	scanf("%d %d", &n, &m);
  90.  
  91. 	FOR(i, 2, n) {
  92. 		scanf("%d %d", &x, &y);
  93. 		v[x].pb(y); v[y].pb(x);
  94. 	}
  95.  
  96. 	FOR(i, 1, m) {
  97. 		scanf("%d %d %d", &x, &y, &c[i]);
  98. 		add[x].pb(i);
  99. 		del[y].pb(i);
  100. 	}
  101.  
  102. 	dfs(1, 0);
  103.  
  104. 	ll ans = solve(1, 0);
  105.  
  106. 	if(ans >= linf) ans = -1;
  107.  
  108. 	printf("%lld\n", ans);
  109.  
  110. 	return 0;
  111. }
  112.  
Success #stdin #stdout 0.03s 124544KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/oxuDlE
language:
C++ (gcc 8.3)
created:
7 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!