fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3.  
  4. using namespace std;
  5. using namespace __gnu_pbds;
  6.  
  7. typedef tree<
  8. pair<int, int>,
  9. null_type,
  10. less<pair<int, int>>,
  11. rb_tree_tag,
  12. tree_order_statistics_node_update> ordered_set;
  13.  
  14. const int maxn = 2e5;
  15.  
  16. vector<pair<int, int>> g[maxn];
  17. vector<int> que[maxn];
  18. ordered_set e[maxn];
  19. int knum[maxn];
  20. int ans[maxn];
  21.  
  22. void dfs(int v = 1, int p = 0)
  23. {
  24. 	for(auto it: g[v])
  25. 	{
  26. 		int u = it.first;
  27. 		int c = it.second;
  28. 		if(u == p)
  29. 			continue;
  30. 		e[v].insert({c, u});
  31. 		dfs(u, v);
  32. 		if(e[v].size() < e[u].size())
  33. 			e[v].swap(e[u]);
  34. 		for(auto it: e[u])
  35. 			e[v].insert(it);
  36. 	}
  37. 	for(auto it: que[v])
  38. 	{
  39. 		if(knum[it] > e[v].size())
  40. 			ans[it] = 1e9;
  41. 		else
  42. 			ans[it] = e[v].find_by_order(knum[it] - 1) -> first;
  43. 	}
  44. }
  45.  
  46. int main()
  47. {
  48. 	ios::sync_with_stdio(0);
  49. 	cin.tie(0);
  50. 	int n, q;
  51. 	cin >> n >> q;
  52. 	for(int i = 0; i < n - 1; i++)
  53. 	{
  54. 		int a, b, c;
  55. 		cin >> a >> b >> c;
  56. 		g[a].push_back({b, c});
  57. 		g[b].push_back({a, c});
  58. 	}
  59. 	for(int i = 1; i <= q; i++)
  60. 	{
  61. 		int u, k;
  62. 		cin >> u >> k;
  63. 		knum[i] = k;
  64. 		que[u].push_back(i);
  65. 	}
  66. 	dfs();
  67. 	for(int i = 1; i <= q; i++)
  68. 	{
  69. 		if(ans[i] == 1e9)
  70. 			cout << "nan";
  71. 		else
  72. 			cout << ans[i];
  73. 		cout << "\n";
  74. 	}
  75. 	return 0;
  76. }
  77.  
Success #stdin #stdout 0.03s 19136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
nan
https://ideone.com/u2JvvG
language:
C++14 (gcc 8.3)
created:
8 years 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!