fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef pair<int,int>   II;
  6. typedef vector< II >      VII;
  7. typedef vector<int>     VI;
  8. typedef vector< VI > 	VVI;
  9. typedef long long int 	LL;
  10.  
  11. #define PB push_back
  12. #define MP make_pair
  13. #define F first
  14. #define S second
  15. #define SZ(a) (int)(a.size())
  16. #define ALL(a) a.begin(),a.end()
  17. #define SET(a,b) memset(a,b,sizeof(a))
  18.  
  19. #define si(n) scanf("%d",&n)
  20. #define dout(n) printf("%d\n",n)
  21. #define sll(n) scanf("%lld",&n)
  22. #define lldout(n) printf("%lld\n",n)
  23. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  24.  
  25. #define TRACE
  26.  
  27. #ifdef TRACE
  28. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  29. template <typename Arg1>
  30. void __f(const char* name, Arg1&& arg1){
  31. 	cerr << name << " : " << arg1 << std::endl;
  32. }
  33. template <typename Arg1, typename... Args>
  34. void __f(const char* names, Arg1&& arg1, Args&&... args){
  35. 	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  36. }
  37. #else
  38. #define trace(...)
  39. #endif
  40.  
  41. //FILE *fin = freopen("in","r",stdin);
  42. //FILE *fout = freopen("out","w",stdout);
  43.  
  44. struct node{
  45. 	int l,r,c,i;
  46. }q[100005];
  47. VI g[200005];
  48. VI v;
  49. int c[200005], timee=0, in[200005], out[200005], vs[200005], cnt[100005], f[100005], minn, ans=0;
  50. const int block =	447;
  51.  
  52. bool foo(struct node a,struct node b){
  53. 	if(a.l/block!=b.l/block)
  54. 		return a.l/block < b.l/block;
  55. 	return a.r < b.r;
  56. }
  57.  
  58. void dfs(int u){
  59. 	trace(u);
  60. 	vs[u]=1;
  61. 	in[u]=timee++;
  62. 	v.PB(c[u]);
  63. 	for(int i=0;i<SZ(g[u]);i++){
  64. 		int w = g[u][i];
  65. 		if(!vs[w])
  66. 			dfs(w);
  67. 	}
  68. 	out[u]=timee;
  69. }
  70.  
  71. void add(int i){
  72. 	cnt[v[i]]++;
  73. 	if(v[i]==minn)
  74. 		ans++;
  75. }
  76.  
  77. void remove(int i){
  78. 	cnt[v[i]]--;
  79. 	if(v[i]==minn-1)
  80. 		ans--;
  81. }
  82.  
  83. int main(){
  84. 	int n,m,a,b;
  85. 	si(n);si(m);
  86. 	for(int i=1;i<=n;i++) si(c[i]);
  87. 	for(int i=1;i<n;i++){
  88. 		si(a);si(b);
  89. 		g[a].PB(b);
  90. 		g[b].PB(a);
  91. 	}
  92. 	dfs(1);
  93. 	for(int i=0;i<SZ(v);i++)
  94. 		cout << v[i] << ' ';
  95. 	cout << endl;
  96. 	for(int i=0;i<m;i++){
  97. 		si(a);si(b);
  98. 		q[i].l = in[a];
  99. 		q[i].r = out[a];
  100. 		q[i].c = b;
  101. 		q[i].i = i;
  102. 	}
  103. 	sort(q,q+m,foo);	
  104. 	int L=0, R=0;
  105. 	for(int i=0;i<m;i++){
  106. 		int l = q[i].l;
  107. 		int r = q[i].r;
  108. 		trace(l,r);
  109. 		int j = q[i].i;
  110. 		minn = q[i].c;
  111. 		while(L<l){
  112. 			remove(L);
  113. 			L++;
  114. 		}	
  115. 		while(L>l){
  116. 			add(L-1);
  117. 			L--;
  118. 		}
  119. 		while(R<=r){
  120. 			add(R);
  121. 			R++;
  122. 		}
  123. 		while(R>r+1){
  124. 			remove(R-1);
  125. 			R--;
  126. 		}
  127. 		f[j] = ans;
  128. 	}
  129. 	for(int i=0;i<m;i++) dout(f[i]);
  130. 	return 0;
  131. }
Success #stdin #stdout #stderr 0s 11296KB
comments (?)
stdin
copy 
8 5
1 2 2 3 3 2 3 3
1 2
1 5
2 3
2 4
5 6
5 7
5 8
1 2
1 3
1 4
2 3
5 3
stdout
copy 
1 2 2 3 3 2 3 3 
3
3
3
2
1
stderr
copy 
u : 1
u : 2
u : 3
u : 4
u : 5
u : 6
u : 7
u : 8
l : 1 | r : 4
l : 0 | r : 8
l : 0 | r : 8
l : 0 | r : 8
l : 4 | r : 8
https://ideone.com/N2NqCN
language:
C++14 (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!