fork download
copy 
  1. /// MO on tree by muoii
  2. /// MO algo: (block(l1)!=block(l2))?l1<l2:r1<r2
  3.  
  4. /// www.spoj.com/problems/COT2/
  5.  
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. #define tag "spoj"
  9. #define maxn 40007
  10. #define maxc 0
  11. #define maxlog 17
  12. #define oo 1000000007
  13. #define mid ((l+r)>>1)
  14. #define meset(a,x) memset(a,x,sizeof(a))
  15. #define loop(x) for(int LoOpEr=1;LoOpEr<=x;LoOpEr++)
  16. ///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
  17. int n,m;
  18. int a[maxn];
  19. int c[maxn];
  20. vector<int> adj[maxn];
  21. #define add_edge(u,v) adj[u].push_back(v),adj[v].push_back(u)
  22.  
  23. int numbering;
  24. int tour[2*maxn];
  25. int beg[maxn],fin[maxn];
  26.  
  27. int par[maxn][(int)log2(2*maxn)];
  28. #define parent(u) par[u][0]
  29. #define ances(u,i) par[u][i]
  30.  
  31. int h[maxn];
  32. #define depth(u) h[u]
  33.  
  34. /// DFS:
  35. void dfs(const int &u,const int &parent,const int &depth)
  36. {
  37.     tour[beg[u]=++numbering]=u;
  38.  
  39.     parent(u)=parent;
  40.     depth(u)=depth;
  41.  
  42.     ///dplca:
  43.     for(int i=1;1<<i<n;i++) ances(u,i)=ances(ances(u,i-1),i-1);
  44.  
  45.     for(const int &v: adj[u])
  46.         if(!depth(v))
  47.             dfs(v,u,depth+1);
  48.  
  49.     tour[fin[u]=++numbering]=u;
  50. }
  51.  
  52. /// LCA:
  53. int lca(int x,int y)
  54. {
  55.     if(depth(x)<depth(y)) swap(x,y);
  56.  
  57.     while(depth(x)>depth(y)) x=ances(x,(int)log2(depth(x)-depth(y)));
  58.  
  59.     int lg=log2(depth(x));
  60.  
  61.     while(x!=y)
  62.     {
  63.         while(lg>0 && ances(x,lg)==ances(y,lg)) --lg;
  64.         x=ances(x,lg),y=ances(y,lg);
  65.     }
  66.  
  67.     return x;
  68. }
  69.  
  70. /// MO algo:
  71. #define sqrt2n ((int)(sqrt(2*n)))
  72. #define block(i) (i/sqrt2n)
  73. struct query{
  74.     int id,left,right;
  75.     int special;
  76.  
  77.     query(const int &x,const int &y,const int &i)
  78.     {
  79.         id=i;
  80.         int u=x,v=y;
  81.         if(beg[u]>beg[v]) swap(u,v);
  82.  
  83.         int lcanc=lca(u,v);
  84.  
  85.         special=(lcanc!=u)?lcanc:0;
  86.  
  87.         left=!special?beg[u]:fin[u];
  88.         right=beg[v];
  89.     }
  90.  
  91.     bool operator < (const query &q) const{
  92.         return (block(left)!=block(q.left))?left<q.left:right<q.right;
  93.     }
  94. };
  95.  
  96. int CNTER=0;
  97. #define onpath(ver,left,right) (!((left<=beg[ver] && fin[ver]<=right) || (fin[ver]<left && beg[ver]>right)))
  98.  
  99. void add(const int &i,const int &l,const int &r)
  100. {
  101.     if(onpath(tour[i],l,r)) CNTER+=!c[a[tour[i]]],c[a[tour[i]]]++;
  102.     else c[a[tour[i]]]--,CNTER-=!c[a[tour[i]]];
  103. }
  104. void del(const int &i,const int &l,const int &r)
  105. {
  106.     if(onpath(tour[i],l,r)) c[a[tour[i]]]--,CNTER-=!c[a[tour[i]]];
  107.     else CNTER+=!c[a[tour[i]]],c[a[tour[i]]]++;
  108. }
  109.  
  110. ///MAIN:
  111. int main()
  112. {
  113.     #ifdef dmdd
  114.     freopen(tag".inp","r",stdin); freopen(tag".out","w",stdout);
  115.     #endif // dmdd
  116.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  117.  
  118.     ///input:
  119.     cin>>n>>m;
  120.     vector<int> d;
  121.     for(int i=1;i<=n;i++) cin>>a[i],d.push_back(a[i]);
  122.     sort(d.begin(),d.end());
  123.     for(int i=1;i<=n;i++) a[i]=lower_bound(d.begin(),d.end(),a[i])-d.begin()+1;
  124.  
  125.     int u,v;
  126.     loop(n-1) cin>>u>>v,add_edge(u,v);
  127.  
  128.     dfs(1,0,1);
  129.  
  130.     vector<query> Q;
  131.     vector<int> ans(m);
  132.  
  133.     for(int i=0;i<m;i++) cin>>u>>v,Q.push_back(query(u,v,i));
  134.  
  135.     sort(Q.begin(),Q.end());
  136.  
  137.     int l=1,r=0,L=1,R=0;
  138.  
  139.     for(const auto &q: Q)
  140.     {
  141.         L=q.left,R=q.right;
  142.  
  143.         while (l>L) --l,add(l,l,r);
  144.         while (r<R) ++r,add(r,l,r);
  145.         while (l<L) del(l,l,r),l++;
  146.         while (r>R) del(r,l,r),r--;
  147.  
  148.         ans[q.id]=CNTER + (q.special && c[a[q.special]]==0);
  149.     }
  150.  
  151.     for(const int &rep: ans) cout<<rep<<"\n";
  152.  
  153.     return 0;
  154. }
Success #stdin #stdout 0s 4500KB
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/KcjOik
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!