fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define For(i, a, b) for (int i = (a); i <= (b); ++i)
  4. #define ForD(i, a, b) for (int i = (a); i >= (b); --i)
  5. #define rep(i, n) for (int i = 0; i < (n); ++i)
  6.  
  7. using namespace std;
  8.  
  9. void file(string s){
  10.  
  11.     if (s.empty()) return;
  12.  
  13.     freopen((s + ".inp").c_str(), "r", stdin);
  14.     freopen((s + ".out").c_str(), "w", stdout);
  15. }
  16.  
  17. void maximize(int &x, int y){
  18. 	if (x < y) x = y;
  19. }
  20.  
  21. const int N = 5e5 + 5;
  22.  
  23. struct query{
  24. 	int u, v, w;
  25. } quer[N];
  26.  
  27. int n, q, t, m;
  28. vector<int> g[N];
  29. int up[N][20], h[N];
  30. int lca[N];
  31.  
  32. int f[N], dp[N][10];
  33. int res;
  34.  
  35. int node[N], timer;
  36.  
  37. void dfs(int u){
  38.  
  39. 	++timer; node[timer] = u;
  40. 	for (int v: g[u]) if (v != up[u][0])
  41. 		dfs(v);
  42. }
  43.  
  44. signed main(){
  45.  
  46. 	ios_base::sync_with_stdio(0); 
  47. 	cin.tie(0); cout.tie(0);
  48. 	file("qtree");
  49.  
  50. 	cin >> n >> q >> t >> m;
  51. 	rep(i, n - 1){
  52. 		int u, v; cin >> u >> v;
  53. 		g[u].push_back(v); g[v].push_back(u);
  54. 	}
  55.  
  56. 	stack<int> st;
  57. 	st.push(1);
  58.  
  59. 	while (!st.empty()){
  60. 		int u = st.top(); st.pop();
  61. 		for (int v: g[u]) if (v != up[u][0]){
  62. 			up[v][0] = u; h[v] = h[u] + 1;
  63. 			st.push(v);
  64. 		}
  65. 	}
  66.  
  67. 	For(j, 1, 17)
  68. 		For(v, 1, n)
  69. 			up[v][j] = up[up[v][j - 1]][j - 1];
  70.  
  71. 	dfs(1);
  72.  
  73. 	For(i, 1, q){
  74. 		int u, v, w; cin >> u >> v >> w;
  75. 		quer[i] = {u, v, w};
  76.  
  77. 		if (h[u] != h[v]){
  78. 			if (h[u] < h[v]) swap(u, v);
  79. 			int k = h[u] - h[v];
  80.  
  81. 			for (int j = 0; (1 << j) <= k; ++j)
  82. 				if (k & (1 << j))
  83. 					u = up[u][j];
  84. 		}
  85.  
  86. 		if (u == v){
  87. 			lca[i] = u;
  88. 			continue;
  89. 		}
  90.  
  91. 		ForD(j, 17, 0)
  92. 			if (up[u][j] != up[v][j])
  93. 				u = up[u][j], v = up[v][j];
  94.  
  95. 		lca[i] = up[u][0];
  96. 	}
  97.  
  98. 	while (t--){
  99. 		int l, r; cin >> l >> r;
  100. 		For(u, 1, n){
  101. 			f[u] = 0;
  102. 			For(j, 1, m){
  103. 				dp[u][j] = 0;
  104. 			}
  105. 		}
  106.  
  107. 		For(i, l, r){
  108. 			int u = quer[i].u, v = quer[i].v, w = quer[i].w;
  109. 			f[u] += w; f[v] += w;
  110. 			f[lca[i]] -= 2 * w;
  111. 		}
  112.  
  113. 		res = 0;
  114.  
  115. 		ForD(i, n, 1){
  116. 			int u = node[i];
  117. 			for (int v: g[u]) if (v != up[u][0]){
  118. 				ForD(j, m, 1){
  119. 					For(k, 1, j){
  120. 						maximize(dp[u][j], dp[u][j - k] + dp[v][k - 1] + f[v]);
  121. 					}
  122. 					maximize(res, dp[u][j]);
  123. 				}
  124. 				f[u] += f[v];
  125. 			}
  126. 		}
  127.  
  128. 		cout << res << '\n';
  129. 	}
  130.  
  131. 	return 0;
  132. }
  133.  
Success #stdin #stdout 0.01s 18072KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/477kbT
language:
C++14 (gcc 8.3)
created:
4 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!