fork download
copy 
  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. unordered_map<int,int>conr, con;
  25. ll n,block,ar[M5],st[M5],en[M5],dep[M5],out[M5],par[M5][20],answer=0,timer=0,kha[M5];
  26. struct query{
  27.     ll l,r,i,p;
  28. }q[M5];
  29. bool comp(query a,query b){
  30.     if(a.l/block!=b.l/block) return a.l<b.l;
  31.     return a.r<b.r;
  32. }
  33. vector<list<ll> >g(M5);
  34. void dfs(ll cur,ll p){
  35.     dep[cur]=dep[p]+1;
  36.     par[cur][0]=p;
  37.     timer++;
  38.     st[cur]=timer;
  39.     kha[timer]=cur;
  40.     for(auto it=g[cur].begin();it!=g[cur].end();it++) if(*it!=p) dfs(*it,cur);
  41.     timer++;
  42.     en[cur]=timer;
  43.     kha[timer]=cur;
  44. }
  45. void preLCA(){
  46.     for(ll i=1;i<log2(n)+1;i++){
  47.         for(ll j=1;j<=n;j++){
  48.             if(par[j][i-1]!=-1)
  49.                 par[j][i]=par[par[j][i-1]][i-1];
  50.         }
  51.     }
  52. }
  53. ll lca(ll u,ll v){
  54.     if(dep[u]>dep[v]) swap(u,v);
  55.     ll dif=dep[v]-dep[u];
  56.     while(dif>0){
  57.         ll up=log2(dif);
  58.         v=par[v][up];
  59.         dif-=(1<<up);
  60.     }
  61.     if(u==v) return u;
  62.     for(ll i=log2(n)+1;i>=0;i--) if(par[u][i]!=par[v][i]){u=par[u][i]; v=par[v][i];}
  63.     return par[u][0];
  64. }
  65. void add(ll i){
  66.     con[i]++;
  67.     if(con[i]==1){ 
  68.         conr[ar[i]]++;
  69.         if(conr[ar[i]]==1) answer++;
  70.     }
  71.     if(con[i]==2){ 
  72.         conr[ar[i]]--;
  73.         if(conr[ar[i]]==0) answer--;
  74.     }
  75. }
  76. void remove(ll i){
  77.     con[i]--;
  78.     if(con[i]==1){ 
  79.         conr[ar[i]]++;
  80.         if(conr[ar[i]]==1) answer++;
  81.     }
  82.     if(con[i]==0){ 
  83.         conr[ar[i]]--;
  84.         if(conr[ar[i]]==0) answer--;
  85.     }
  86. }
  87. int main(){
  88.     //buf; 
  89.     //sieve(); 
  90.     //fact();
  91.     ll l,r,i,j,test,ans,m,k,a,b; //string s;
  92.     //cin>>test;
  93.     test=1;
  94.     while(test--){
  95.         cin>>n>>m;
  96.         for(i=1;i<=n;i++) cin>>ar[i];
  97.         i=1;
  98.         while(i<n){
  99.             cin>>a>>b;
  100.             g[a].pb(b); g[b].pb(a);
  101.             i++;
  102.         }
  103.         memset(par,-1,sizeof(par));
  104.         dep[0]=-1; dfs(1,0);
  105.         //for(i=1;i<=n;i++) cout<<st[i]<<" "<<en[i]<<endl;
  106.         block=timer/sqrt(timer);
  107.         preLCA();
  108.         for(i=0;i<m;i++){
  109.             cin>>a>>b;
  110.             q[i].i=i;
  111.             ll l=lca(a,b);
  112.             if(st[a]>st[b]) swap(a,b);
  113.             if(l==a||l==b){
  114.                 q[i].l=st[a]; q[i].r=st[b]; q[i].p=-1;
  115.             }
  116.             else{
  117.                 q[i].l=en[a]; q[i].r=st[b]; q[i].p=l;
  118.             }
  119.         }
  120.         block=timer/sqrt(timer);
  121.         sort(q,q+m,comp);
  122.         ll cl=1,cr=1; add(1);
  123.         //for(i=1;i<=timer;i++) cout<<kha[i]<<" ";
  124.         //cout<<endl;
  125.         for(i=0;i<m;i++){
  126.             ll u=q[i].l,v=q[i].r;
  127.             //cout<<q[i].i<<" "<<u<<" "<<v<<" "<<q[i].p<<endl;
  128.             while(cl<u){
  129.                 remove(kha[cl]);
  130.                 //for(j=1;j<=n;j++) cout<<conr[ar[j]]<<" "; cout<<endl;
  131.                 cl++;
  132.             }
  133.             //cout<<endl;
  134.             while(cl>u){
  135.                 add(kha[cl+1]);
  136.                 //for(j=1;j<=n;j++) cout<<conr[ar[j]]<<" "; cout<<endl;
  137.                 cl--;
  138.             }
  139.             //cout<<endl;
  140.             while(cr>v){
  141.                 remove(kha[cr]);
  142.                 //for(j=1;j<=n;j++) cout<<conr[ar[j]]<<" "; cout<<endl;
  143.                 cr--;
  144.             }
  145.             //cout<<endl;
  146.             while(cr<v){
  147.                 add(kha[cr+1]);
  148.                 //for(j=1;j<=n;j++) cout<<conr[ar[j]]<<" "; cout<<endl;
  149.                 cr++;
  150.             }
  151.             //cout<<endl;
  152.             if(q[i].p!=-1&&con[ar[q[i].p]]==0) out[i]=answer+1;
  153.             else out[i]=answer;
  154.             //cout<<out[i]<<endl;
  155.         }
  156.         for(i=0;i<m;i++) cout<<out[i]<<endl;
  157.     }
  158.     return 0;
  159. }
Success #stdin #stdout 0s 63688KB
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/jY2HeC
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!