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. ll n,block,ar[M5],st[M5],en[M5],dep[M5],con[M5],out[M5],par[M5][20],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. set<ll> ss;
  65. void add(ll i){
  66.     con[i]++;
  67.     if(con[i]==1){ 
  68.         ss.insert(ar[i]);
  69.     }
  70.     if(con[i]==2){ 
  71.         ss.erase(ar[i]);
  72.     }
  73. }
  74. void remove(ll i){
  75.     con[i]--;
  76.     if(con[i]==1){ 
  77.         ss.insert(ar[i]);
  78.     }
  79.     if(con[i]==0){ 
  80.         ss.erase(ar[i]);
  81.     }
  82. }
  83. int main(){
  84.     //buf; 
  85.     //sieve(); 
  86.     //fact();
  87.     ll l,r,i,j,test,ans,m,k,a,b; //string s;
  88.     //cin>>test;
  89.     test=1;
  90.     while(test--){
  91.         cin>>n>>m;
  92.         for(i=1;i<=n;i++) cin>>ar[i];
  93.         i=1;
  94.         while(i<n){
  95.             cin>>a>>b;
  96.             g[a].pb(b); g[b].pb(a);
  97.             i++;
  98.         }
  99.         memset(par,-1,sizeof(par));
  100.         dep[0]=-1; dfs(1,0);
  101.         //for(i=1;i<=n;i++) cout<<st[i]<<" "<<en[i]<<endl;
  102.         block=timer/sqrt(timer);
  103.         preLCA();
  104.         for(i=0;i<m;i++){
  105.             cin>>a>>b;
  106.             q[i].i=i;
  107.             ll l=lca(a,b);
  108.             if(st[a]>st[b]) swap(a,b);
  109.             if(l==a||l==b){
  110.                 q[i].l=st[a]; q[i].r=st[b]; q[i].p=-1;
  111.             }
  112.             else{
  113.                 q[i].l=en[a]; q[i].r=st[b]; q[i].p=l;
  114.             }
  115.         }
  116.         block=timer/sqrt(timer);
  117.         sort(q,q+m,comp);
  118.         ll cl=1,cr=1; add(1);
  119.         for(i=0;i<m;i++){
  120.             ll u=q[i].l,v=q[i].r;
  121.             while(cl<u){
  122.                 remove(kha[cl]);
  123.                 cl++;
  124.             }
  125.             while(cl>u){
  126.                 add(kha[cl+1]);
  127.                 cl--;
  128.             }
  129.             //cout<<endl;
  130.             while(cr>v){
  131.                 remove(kha[cr]);
  132.                 cr--;
  133.             }
  134.             while(cr<v){
  135.                 add(kha[cr+1]);
  136.                 cr++;
  137.             }
  138.             if(q[i].p!=-1&&con[ar[q[i].p]]==0) out[i]=ss.size()+1;
  139.             else out[i]=ss.size();
  140.         }
  141.         for(i=0;i<m;i++) cout<<out[i]<<" ";
  142.     }
  143.     return 0;
  144. }
Runtime error #stdin #stdout 0s 69184KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XayVRl
language:
C++14 (gcc 8.3)
created:
6 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!