fork download
copy 
  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
comments (?)
stdin
copy 
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
copy 
4
4
https://ideone.com/MG3XbK
language:
C++14 (gcc 8.3)
created:
8 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!