fork(1) download 
  1. /*Coded by::
  2.     **Avinash Tiwary**
  3.     **BE/10298/2015**
  4.     **Production Engineer**
  5.     **Producing <code>**
  6. */
  7. #include<bits/stdc++.h>
  8. #define buf ios_base::sync_with_stdio (0), cin.tie (0)
  9. typedef long long ll;
  10. typedef double dob;
  11. #define MAX 50010
  12. #define M5 200009
  13. #define M6 2000009
  14. #define M 1000000007
  15. #define INF 1e18
  16. using namespace std;
  17. typedef vector<ll> V;
  18. typedef queue<ll > Q;
  19. typedef stack<ll> S;
  20. typedef pair<ll,ll> P;
  21. #define mp make_pair
  22. #define mt make_tuple
  23. #define pb push_back
  24. ll n,block,ar[M5],st[M5],en[M5],dep[M5],out[M5],par[M5][20],con[M5],conr[M6],answer=0,timer=0,kha[M5];
  25. struct query{
  26.     ll l,r,i,p;
  27. }q[M5];
  28. bool comp(query a,query b){
  29.     if(a.l/block!=b.l/block) return a.l<b.l;
  30.     return a.r<b.r;
  31. }
  32. vector<list<ll> >g(M5);
  33. void dfs(ll cur,ll p){
  34.     dep[cur]=dep[p]+1;
  35.     par[cur][0]=p;
  36.     timer++;
  37.     st[cur]=timer;
  38.     kha[timer]=cur;
  39.     for(auto it=g[cur].begin();it!=g[cur].end();it++) if(*it!=p) dfs(*it,cur);
  40.     timer++;
  41.     en[cur]=timer;
  42.     kha[timer]=cur;
  43. }
  44. void preLCA(){
  45.     for(ll i=1;i<log2(n)+1;i++){
  46.         for(ll j=1;j<=n;j++){
  47.             if(par[j][i-1]!=-1)
  48.                 par[j][i]=par[par[j][i-1]][i-1];
  49.         }
  50.     }
  51. }
  52. ll lca(ll u,ll v){
  53.     if(dep[u]>dep[v]) swap(u,v);
  54.     ll dif=dep[v]-dep[u];
  55.     while(dif>0){
  56.         ll up=log2(dif);
  57.         v=par[v][up];
  58.         dif-=(1<<up);
  59.     }
  60.     if(u==v) return u;
  61.     for(ll i=log2(n)+1;i>=0;i--) if(par[u][i]!=par[v][i]){u=par[u][i]; v=par[v][i];}
  62.     return par[u][0];
  63. }
  64. void add(ll i){
  65.     con[i]++;
  66.     if(con[i]==1){ 
  67.         conr[ar[i]]++;
  68.         if(conr[ar[i]]==1) answer++;
  69.     }
  70.     if(con[i]==2){ 
  71.         conr[ar[i]]--;
  72.         if(conr[ar[i]]==0) answer--;
  73.     }
  74. }
  75. void remove(ll i){
  76.     con[i]--;
  77.     if(con[i]==1){ 
  78.         conr[ar[i]]++;
  79.         if(conr[ar[i]]==1) answer++;
  80.     }
  81.     if(con[i]==0){ 
  82.         conr[ar[i]]--;
  83.         if(conr[ar[i]]==0) answer--;
  84.     }
  85. }
  86. int main(){
  87.     //buf; 
  88.     //sieve(); 
  89.     //fact();
  90.     ll l,r,i,j,test,ans,m,k,a,b; //string s;
  91.     //cin>>test;
  92.     test=1;
  93.     while(test--){
  94.         cin>>n>>m;
  95.         for(i=1;i<=n;i++) cin>>ar[i];
  96.         i=1;
  97.         while(i<n){
  98.             cin>>a>>b;
  99.             g[a].pb(b); g[b].pb(a);
  100.             i++;
  101.         }
  102.         memset(par,-1,sizeof(par));
  103.         dep[0]=-1; dfs(1,0);
  104.         //for(i=1;i<=n;i++) cout<<st[i]<<" "<<en[i]<<endl;
  105.         block=timer/sqrt(timer);
  106.         preLCA();
  107.         for(i=0;i<m;i++){
  108.             cin>>a>>b;
  109.             q[i].i=i;
  110.             ll l=lca(a,b);
  111.             if(st[a]>st[b]) swap(a,b);
  112.             if(l==a||l==b){
  113.                 q[i].l=st[a]; q[i].r=st[b]; q[i].p=-1;
  114.             }
  115.             else{
  116.                 q[i].l=en[a]; q[i].r=st[b]; q[i].p=l;
  117.             }
  118.         }
  119.         block=timer/sqrt(timer);
  120.         sort(q,q+m,comp);
  121.         ll cl=1,cr=1; add(1);
  122.         //for(i=1;i<=timer;i++) cout<<kha[i]<<" ";
  123.         //cout<<endl;
  124.         for(i=0;i<m;i++){
  125.             ll u=q[i].l,v=q[i].r;
  126.             //cout<<q[i].i<<" "<<u<<" "<<v<<" "<<q[i].p<<endl;
  127.             while(cl<u){
  128.                 remove(kha[cl]);
  129.                 //for(j=1;j<=n;j++) cout<<conr[ar[j]]<<" "; cout<<endl;
  130.                 cl++;
  131.             }
  132.             //cout<<endl;
  133.             while(cl>u){
  134.                 add(kha[cl+1]);
  135.                 //for(j=1;j<=n;j++) cout<<conr[ar[j]]<<" "; cout<<endl;
  136.                 cl--;
  137.             }
  138.             //cout<<endl;
  139.             while(cr>v){
  140.                 remove(kha[cr]);
  141.                 //for(j=1;j<=n;j++) cout<<conr[ar[j]]<<" "; cout<<endl;
  142.                 cr--;
  143.             }
  144.             //cout<<endl;
  145.             while(cr<v){
  146.                 add(kha[cr+1]);
  147.                 //for(j=1;j<=n;j++) cout<<conr[ar[j]]<<" "; cout<<endl;
  148.                 cr++;
  149.             }
  150.             //cout<<endl;
  151.             if(q[i].p!=-1&&con[ar[q[i].p]]==0) out[i]=answer+1;
  152.             else out[i]=answer;
  153.             //cout<<out[i]<<endl;
  154.         }
  155.         for(i=0;i<m;i++) cout<<out[i]<<" ";
  156.     }
  157.     return 0;
  158. }
Success #stdin #stdout 0.01s 79296KB
comments (?)
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
https://ideone.com/GVvY2q
language:
C++14 (gcc 8.3)
created:
7 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!