fork download
copy 
  1. /**
  2.  *    author:  orzvanh14 (  )
  3.  *    created: 23.12.2022 10:08:02
  4.  *    too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define fi first
  16. #define se second
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define eb emplace_back
  20. #define pb push_back
  21. #define TASK " "
  22.  
  23. #define ms(a, x) memset(a, x, sizeof(a))
  24. #define all(a) a.begin(), a.end()
  25. #define All(a, n) a + 1, a + 1 + n
  26.  
  27. #define LOG 19
  28.  
  29.  
  30. const int INF = 1e18;
  31. const int mod = 1e9+7;
  32. const int N = 1e5  + 5;
  33. int MOD = 998244353;
  34. int bit[200000];
  35. struct node{
  36. 	int kc, u, hk;
  37. 	bool operator<(const node& other) const {
  38.         return kc > other.kc; 
  39.     }
  40. };
  41. struct edge{
  42. 	int v, w, h;
  43. };
  44. struct dsu{
  45. 	int x, y, w;
  46. 	bool operator<(const dsu& other) const {
  47.         return w > other.w; 
  48.     }
  49. };
  50. struct query{
  51.     int k, v, id;
  52.     bool operator<(const query &other) const{
  53.         return k > other.k;
  54.     }
  55. };
  56. int n, q;
  57. dsu adj[N];
  58. query tv[N];
  59. int ans[N];
  60. int parent[N], sz[N];
  61. void nhap(){
  62. 	cin >> n >> q;
  63. 	for(int i =1 ;i <= n - 1;i++){
  64. 		cin >> adj[i].x >> adj[i].y >> adj[i].w;
  65. 	}
  66. 	sort(adj + 1, adj + 1 + n - 1);
  67. }
  68. void make_set(int v){
  69. 	parent[v] = v;
  70. 	sz[v] = 1;
  71. }
  72. int get(int a){
  73. 	if(a == parent[a]) return a;
  74.     parent[a] = get(parent[a]);
  75. 	return parent[a];
  76. }
  77. void union_sets(int a, int b){
  78. 	a = get(a);
  79. 	b = get(b);
  80. 	if(a != b){
  81. 		if(sz[a] < sz[b]) swap(a, b);
  82. 		parent[b] = a;
  83. 		sz[a] += sz[b];
  84. 	}
  85. }
  86. void solve(){
  87. 	for(int i = 1; i <= n; i++){
  88. 		make_set(i);
  89. 	}
  90. 	for(int i = 1;i <= q; i++){
  91. 		cin >> tv[i].k >> tv[i].v;
  92.         tv[i].id = i;
  93. 	}
  94. 	 sort(tv + 1, tv + q + 1);
  95. 	int l = 1;
  96. 	for(int i = 1;i <= q; i++){
  97. 		while(l <= n - 1 && adj[l].w >= tv[i].k){
  98. 				union_sets(adj[l].x, adj[l].y);
  99. 				l++;
  100. 		}
  101. 		ans[tv[i].id] = sz[get(tv[i].v)] - 1;
  102. 	}
  103.     for(int i = 1; i <= q; i++){
  104.         cout << ans[i] << nn;
  105.      }
  106.  
  107. }
  108. signed main() {
  109. 	// freopen("piggyback.in", "r", stdin);
  110. 	// freopen("piggyback.out", "w", stdout);
  111. 	ios_base::sync_with_stdio(0);
  112. 	cin.tie(0);
  113. 	cout.tie(0);
  114.     nhap();
  115.     solve();
  116. 	return (0 ^ 0);
  117.  
  118. }
  119.  
  120.  
Success #stdin #stdout 0.01s 9696KB
comments (?)
stdin
copy 
4 3
1 2 3
2 3 2
2 4 4
1 2
4 1
3 1
stdout
copy 
3
0
2
https://ideone.com/06WrC2
language:
C++14 (gcc 8.3)
created:
1 day 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!