fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define mod 1000000007
  4. #define mp make_pair
  5. #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define pb push_back
  7. #define pii pair<int ,int >
  8. #define all(v) v.begin(),v.end()
  9. #define test(t) int t;cin>>t;while(t--)
  10. ll poww(ll x,ll y) {ll res=1;x%=mod; assert(y>=0); for(;y;y>>=1){if(y&1)res=res*x%mod;x=x*x%mod;}return res;}
  11. using namespace std;
  12.  
  13. struct query{
  14.     int l,r,k,idx;
  15. }qu[100005];
  16.  
  17. int cnt[40005],freq[40005],bsize;
  18. int P[40005][20],n,p[40005];
  19. int a[40005],in[40005],out[40005];
  20. vector<pair<ll,int> > b;
  21. vector<int> v[40005],vv;
  22. bool vis[40005];
  23. int t,Lvl[40005],anss[100005];
  24.  
  25.  
  26. int cmp(query lhs,query rhs){
  27.     if(lhs.l/bsize==rhs.l/bsize)
  28.         return lhs.r<rhs.r;
  29.     return lhs.l/bsize < rhs.l/bsize;
  30. }
  31.  
  32. void dfs(int x,int lvl){
  33.  
  34.     Lvl[x]=lvl;
  35.     vv.pb(x);
  36.     for(int i=0;i<v[x].size();++i)
  37.     if(!vis[v[x][i]]){
  38.         vis[v[x][i]]=1;
  39.         dfs(v[x][i],lvl+1);
  40.         p[v[x][i]]=x;
  41.     }
  42.     vv.pb(x);
  43.  
  44. }
  45.  
  46.  
  47. void build(){
  48.  
  49.     memset(P,-1,sizeof P);
  50.     memset(in,-1,sizeof in);
  51.     p[1]=-1;
  52.     int i,j;
  53.     for(i=1;i<=n;++i)
  54.         P[i][0]=p[i];
  55.     for(i=1;i<=n;++i)
  56.         for(j=1;j<=18;++j){
  57.         if(P[i][j-1]!=-1){
  58.             P[i][j]=P[P[i][j-1]][j-1];
  59.         }
  60.     }
  61. }
  62.  
  63. int LCA(int x,int y){
  64.  
  65.     int i;
  66.     if(Lvl[x]<Lvl[y])
  67.         swap(x,y);
  68.     int raise,dist=Lvl[x]-Lvl[y];
  69.     while(dist>0){
  70.         raise=log2(dist);
  71.         x=P[x][raise];
  72.         dist-=(1<<raise);
  73.     }
  74.     if(x==y)
  75.         return x;
  76.     for(i=16;i>=0;--i){
  77.         if(P[x][i]!=P[y][i]&&P[x][i]!=-1){
  78.             x=P[x][i];
  79.             y=P[y][i];
  80.         }
  81.     }
  82.     return p[x];
  83.  
  84. }
  85.  
  86. int main()
  87. {
  88.     int i,j,q,l,r,ml,mr,c=1,y;
  89.     ll x;
  90.     scanf("%d",&n);
  91.     scanf("%d",&q);
  92.     bsize=sqrt(n);
  93.     for(i=1;i<=n;i++){
  94.         scanf("%lld",&x);
  95.         b.pb(mp(x,i));
  96.     }
  97.     sort(all(b));
  98.     a[b[0].second]=c;
  99.     for(i=1;i<n;++i){
  100.         if(b[i].first!=b[i-1].first)
  101.             c++;
  102.         a[b[i].second]=c;
  103.     }
  104.  
  105.     for(i=0;i<n-1;++i){
  106.  
  107.         scanf("%d %d",&x,&y);
  108.         v[x].pb(y);
  109.         v[y].pb(x);
  110.     }
  111.     vis[1]=1;
  112.     dfs(1,0);
  113.     build();
  114.     for(i=0;i<vv.size();++i){
  115.         if(in[vv[i]]==-1)
  116.             in[vv[i]]=i;
  117.         out[vv[i]]=i;
  118.     }
  119.     for(i=0;i<q;i++){
  120.         scanf("%d %d",&qu[i].l,&qu[i].r);
  121.         qu[i].idx=i;
  122.         qu[i].l;
  123.         qu[i].r;
  124.     }
  125.     ml=0;
  126.     mr=-1;
  127.     int lca;
  128.     for(i=0;i<q;i++){
  129.         l=qu[i].l;
  130.         r=qu[i].r;
  131.         if(in[l]>in[r])
  132.             swap(l,r);
  133.         lca=LCA(l,r);
  134.         if(lca==l){
  135.             qu[i].l=in[l];
  136.             qu[i].r=in[r];
  137.             qu[i].k=-1;
  138.         }
  139.         else{
  140.             qu[i].l=out[l];
  141.             qu[i].r=in[r];
  142.             qu[i].k=lca;
  143.         }
  144.     }
  145.     sort(qu,qu+q,cmp);
  146.     int ans=0;
  147.     for(i=0;i<q;++i){
  148.         l=qu[i].l;
  149.         r=qu[i].r;
  150.  
  151.         while(mr<r){
  152.             mr++;
  153.             cnt[vv[mr]]++;
  154.             if(cnt[vv[mr]]==1){
  155.                 if(freq[a[vv[mr]]]==0)
  156.                     ans++;
  157.                 freq[a[vv[mr]]]++;
  158.             }
  159.             if(cnt[vv[mr]]==2){
  160.                 if(freq[a[vv[mr]]]==1)
  161.                     ans--;
  162.                 freq[a[vv[mr]]]--;
  163.             }
  164.  
  165.         }
  166.         while(ml>l){
  167.             ml--;
  168.  
  169.             cnt[vv[ml]]++;
  170.             if(cnt[vv[ml]]==1){
  171.                 if(freq[a[vv[ml]]]==0)
  172.                 ans++;
  173.                 freq[a[vv[ml]]]++;
  174.             }
  175.             if(cnt[vv[ml]]==2){
  176.                 if(freq[a[vv[ml]]]==1)
  177.                 ans--;
  178.                 freq[a[vv[ml]]]--;
  179.             }
  180.  
  181.         }
  182.         while(ml<l){
  183.  
  184.             cnt[vv[ml]]--;
  185.             if(cnt[vv[ml]]==0){
  186.                 if(freq[a[vv[ml]]]==1)
  187.                     ans--;
  188.                 freq[a[vv[ml]]]--;
  189.             }
  190.             if(cnt[vv[ml]]==1){
  191.                 if(freq[a[vv[ml]]]==0)
  192.                     ans++;
  193.                 freq[a[vv[ml]]]++;
  194.             }
  195.             ml++;
  196.  
  197.         }
  198.         while(mr>r){
  199.  
  200.             cnt[vv[mr]]--;
  201.             if(cnt[vv[mr]]==0){
  202.                 if(freq[a[vv[mr]]]==1)
  203.                     ans--;
  204.                 freq[a[vv[mr]]]--;
  205.             }
  206.             if(cnt[vv[mr]]==1){
  207.                 if(freq[a[vv[mr]]]==0)
  208.                     ans++;
  209.                 freq[a[vv[mr]]]++;
  210.             }
  211.  
  212.             mr--;
  213.         }
  214.         anss[qu[i].idx]=ans;
  215.         if(qu[i].k!=-1&&freq[a[qu[i].k]]==0)
  216.             anss[qu[i].idx]++;
  217.  
  218.  
  219.  
  220.     }
  221.  
  222.     for(i=0;i<q;i++)
  223.         printf("%d\n",anss[i]);
  224.  
  225. }
  226.  
Runtime error #stdin #stdout 0s 23208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0qRvNR
language:
C++14 (gcc 8.3)
created:
6 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!