fork download
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define N 100010
  4. int w[N];
  5. int sn,n,m,u,v,tst;
  6. int cnt[100000]={0};
  7. vector<int> g[N];
  8. vector<pair<int, pair<int,int > > > q;
  9. int a[N];
  10. int st[N];
  11. int en[N];
  12. int lvl[N];
  13. int p[N];
  14. int ansq[N]={0};
  15. bool isvisited[N];
  16. struct compare{
  17. bool operator()(const pair<int, pair<int,int > > &a1, const pair<int, pair<int,int > > &a2)
  18. {
  19. if(((a1.second).first)/sn!=((a2.second).first)/sn)
  20. return ((a1.second).first)/sn<((a2.second).first)/sn;
  21. else
  22. return ((a1.second).second)<((a2.second).second);
  23. }
  24. };
  25. void dfs(int i,int l)
  26. {
  27. if(!isvisited[i])
  28. {
  29. if(l==0)
  30. {
  31. p[i]=0;
  32. }
  33. isvisited[i]=1;
  34. lvl[i]=l;
  35. st[i]=tst;
  36. a[tst]=i;
  37. tst++;
  38. vector<int>::iterator it;
  39. for(it=g[i].begin();it!=g[i].end();it++)
  40. {
  41. dfs(*it,l+1);
  42. p[*it]=i;
  43. }
  44. en[i]=tst;
  45. a[tst]=i;
  46. tst++;
  47. }
  48. }
  49. int par(int x,int z)
  50. {
  51. while(lvl[z]!=lvl[x])
  52. {
  53. z=p[z];
  54. }
  55. if(z==x)
  56. return 1;
  57. while(p[x]!=p[z]&&p[x]!=0&&p[z]!=0)
  58. {
  59. x=p[x];
  60. z=p[z];
  61. }
  62. if(p[x]==0)
  63. return x;
  64. else
  65. return p[x];
  66. }
  67. inline void check(int x, int& res){
  68. if ( (isvisited[x]) and (--cnt[w[x]] == 0) ) res--;
  69. else if ( (!isvisited[x]) and (cnt[w[x]]++ == 0) ) res++;
  70. isvisited[x] ^= 1;
  71. }
  72. int main()
  73. {
  74. memset(isvisited,0,sizeof(isvisited));
  75. for(int i=0;i<N;i++){
  76. ansq[i]=0;
  77. cnt[i]=0;
  78. }
  79. scanf("%d %d",&n,&m);
  80. for(int i=1;i<n+1;i++)
  81. scanf("%d",&w[i]);
  82. for(int i=0;i<n-1;i++)
  83. {
  84. scanf("%d %d",&u,&v);
  85. g[u].push_back(v);
  86. g[v].push_back(u);
  87. }
  88. tst=0,a[tst]=0;
  89. //cout<<"dfs start"<<endl;
  90. for(int i=1;i<n;i++){
  91. dfs(i,0);
  92. }
  93. //cout<<" dfs end"<<endl;
  94. //for(int i=0;i<tst;i++)
  95. // cout<<a[i]<<" ";
  96. //cout<<endl;
  97. //cout<<tst<<"\n";
  98. sn=sqrt(tst);
  99. //cout<<"query insertion time"<<endl;
  100. for(int i=1;i<=m;i++)
  101. {
  102. scanf("%d %d",&u,&v);
  103. if(lvl[u]>lvl[v])
  104. {
  105. int temp=u;
  106. u=v;
  107. v=temp;
  108. }
  109. //cout<<"query insertion processing"<<endl;
  110. int k=par(u,v);
  111. if(k==u)
  112. {
  113. q.push_back(make_pair(i,make_pair(st[u],st[v])));
  114. }
  115. else
  116. {
  117. q.push_back(make_pair(i,make_pair(en[u],st[v])));
  118. q.push_back(make_pair(i,make_pair(st[k],st[k])));
  119. }
  120. // cout<<"a query is inserted"<<endl;
  121. }
  122. //cout<<"all query inserted an sorting start"<<endl;
  123. sort(q.begin(),q.end(),compare());
  124. //cout<<"query sorted"<<endl;
  125. vector<pair<int, pair<int,int > > >::iterator it1;
  126. int curl=0,cur=0,ans=0,val;
  127. memset(isvisited,0,sizeof(isvisited));
  128. for(it1=q.begin();it1!=q.end();it1++)
  129. {
  130. //cout<<"a query is given consideration"<<endl;
  131. u=(it1->second).first;
  132. v=(it1->second).second;
  133. int ind=it1->first;
  134. //cout<<"a query curl and u is checked for <"<<endl;
  135. while(curl<u)
  136. {
  137. val=a[curl];
  138. check(val,ans);
  139. curl++;
  140. }
  141. //cout<<"a query curl and u is checked for >"<<endl;
  142. while(curl>u)
  143. {
  144. curl--;
  145. val=a[curl];
  146. check(val,ans); }
  147. //cout<<"a query cur and v is checked for >"<<endl;
  148. while(cur>v)
  149. {
  150. val=a[cur];
  151. check(val,ans);
  152. curl--;
  153. }
  154. while(cur<v)
  155. {
  156. cur++;
  157. val=a[cur];
  158. check(val,ans);
  159. }
  160. ansq[ind]+=ans;
  161. }
  162. for(int i=1;i<=m;i++)
  163. printf("%d\n",ansq[i]);
  164. return 0;
  165. }
  166.  
Success #stdin #stdout 0s 7812KB
stdin
8 2
105 2 9 3 8 5 7 7
1 2
1 3
1 4
3 5
3 6
3 7
4 8
2 5
7 8
stdout
4
4