fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<pair<int, int>> adj[100001];
  5. vector<pair<int, int>> quer[100001];
  6. int ans[100001];
  7. vector<int> path;
  8.  
  9. void dfs(int u, int p, int t) {
  10. 	for (auto vp : adj[u]) {
  11. 		if (vp.first != p) {
  12. 			path.push_back(t + vp.second);
  13. 			dfs(vp.first, u, t + vp.second);
  14. 			path.pop_back();
  15. 		}
  16. 	}
  17. 	for (auto q: quer[u]) {
  18. 		int s = 0, e = path.size() - 1;
  19. 		while (s < e) {
  20. 			int m = (s + e + 1) / 2;
  21. 			if (path[m] <= q.first) {
  22. 				s = m;
  23. 			} else {
  24. 				e = m - 1;
  25. 			}
  26. 		}
  27. 		ans[q.second] = s + 1;
  28. 	}
  29. }
  30.  
  31. int main() {
  32. 	int n; cin >> n;
  33. 	for (int i = 0; i < n; ++i) {
  34. 		int u, v, w; cin >> u >> v >> w;
  35. 		adj[u].push_back({v, w});
  36. 		adj[v].push_back({u, w});
  37. 	}
  38. 	int q; cin >> q;
  39. 	for (int i = 0; i < q; ++i) {
  40. 		int u, d;
  41. 		cin >> u >> d;
  42. 		quer[u].push_back({d, i});
  43. 	}
  44. 	path.push_back(0);
  45. 	dfs(0, 0, 0);
  46. 	return 0;
  47. }
Success #stdin #stdout 0.01s 8276KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/VCrIrp
language:
C++14 (gcc 8.3)
created:
14 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!