fork download
copy 
  1. /*
  2. ye mera template hai
  3. apna khud likho bc :P
  4. */
  5.  
  6. /*
  7. Author : Sarvagya Agarwal
  8. */
  9.  
  10. #include<bits/stdc++.h>
  11. using namespace std;
  12.  
  13. //defines
  14. #define openin freopen("input.txt","r",stdin)
  15. #define openout freopen("output.txt","w",stdout)
  16. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
  17. #define ll long long
  18. #define int long long
  19. #define mod 1000000007
  20. #define rep(i,x,y) for (__typeof(x) i=x;(x<=y?i<=y:i>=y);i=(x<=y?i+1:i-1))
  21. #define all(c) (c).begin(),(c).end()
  22. #define ff first
  23. #define ss second
  24. #define pb push_back
  25. #define mp make_pair
  26.  
  27. int power(int a , int b)
  28. {
  29.     int res = 1 ;
  30.     while(b)
  31.     {
  32.         if(b%2) {
  33.             res = (res * a)%mod ;
  34.         }
  35.         b/=2 ;
  36.         a = (a*a)%mod ;
  37.     }
  38.     return res ;
  39. }
  40.  
  41. //debug
  42. #define TRACE
  43.  
  44. #ifdef TRACE
  45. #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
  46. template <typename Arg1>
  47. void __f(const char* name, Arg1&& arg1){
  48. 		cerr << name << " : " << arg1 << std::endl;
  49. }
  50. template <typename Arg1, typename... Args>
  51. void __f(const char* names, Arg1&& arg1, Args&&... args){
  52. 		const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
  53. }
  54. #else
  55. #define trace(...)
  56. #endif
  57. const int MAX_N = 40005 ;
  58. const int MAX_M = 100005 ;
  59. int weight[MAX_N] , answers[MAX_M] , N , M ,arr[3*MAX_N];
  60. vector<int> graph[MAX_N] ;
  61. int start[MAX_N] , endd[MAX_N] ;
  62. int P[MAX_N][23] , depth[MAX_N] , vis[MAX_N] ,timer = 1 ;
  63. void DFS(int node = 1 , int par = 0 , int d = 0)
  64. {
  65.     start[node] = timer ;
  66.     arr[timer++] = node ;
  67.     depth[node] = d ;
  68.     P[node][0] = par ;
  69.     for(auto child : graph[node]) {
  70.         if(child != par) {
  71.             DFS(child,node,d+1) ;
  72.         }
  73.     }
  74.     endd[node] = timer ;
  75.     arr[timer++] = node ;
  76. }
  77. void pre(int n)
  78. {
  79.     for(int j=1;(1<<j)<n;j++)
  80.     {
  81.         rep(i,1,n)
  82.         {
  83.             if(P[i][j-1]!=-1)
  84.             {
  85.                 P[i][j] = P[P[i][j-1]][j-1];
  86.             }
  87.         }
  88.     }
  89. }
  90. int LCA(int p,int q)
  91. {
  92.     int temp ;
  93.     if(depth[p] < depth[q])
  94.         temp=p,p=q,q=temp ;
  95.     int log ;
  96.     for(log=1;(1<<log)<=depth[p];log++) ;
  97.     log--;
  98.     for(int i=log;i>=0;i--)
  99.     {
  100.         if(depth[p] - (1<<i) >= depth[q])
  101.             p=P[p][i];
  102.     }
  103.     if(p==q)return p;
  104.     //now compute lca using dp table(P)
  105.     for(int i=log;i>=0;i--)
  106.     {
  107.         if(P[p][i]!=-1&&P[p][i]!=P[q][i])
  108.             p=P[p][i],q=P[q][i];
  109.     }
  110.     return P[p][0];
  111. }
  112. void compress()
  113. {
  114.     set<int> s ;
  115.     map<int,int> m ;
  116.     rep(i,1,N)s.insert(weight[i]) ;
  117.     int index = 1 ;
  118.     for(auto it : s) m[it]=index++ ;
  119.     rep(i,1,N)
  120.     {
  121.         weight[i] = m[weight[i]] ;
  122.     }
  123.     return ;
  124. }
  125. int BLOCK ,ans = 0;
  126. struct query {
  127.     int index,L,R,flag ;
  128. };
  129. query queries[MAX_M] ;
  130. bool compare(query A , query B)
  131. {
  132.     if(A.L / BLOCK != B.L/BLOCK)
  133.         return A.L/BLOCK < B.L/BLOCK ;
  134.     return A.R < B.R ;
  135. }
  136. int freq[MAX_N] , cnt[MAX_N] ;
  137. void check(int index)
  138. {
  139.     int node = arr[index] ;
  140.     if(freq[node] && (--cnt[weight[node]] == 0))
  141.         ans-- ;
  142.     else if(freq[node]==0 && (cnt[weight[node]]++ == 0))
  143.         ans++;
  144.     freq[node] ^= 1 ;
  145. }
  146. int32_t main()
  147. {
  148.     fast;
  149.     //openin;
  150.     cin >> N >> M ;
  151.     BLOCK = sqrt(N) ;
  152.     rep(i,1,N)cin >> weight[i] ;
  153.     compress() ;
  154.     rep(i,2,N)
  155.     {
  156.         int u,v ;
  157.         cin >> u >> v ;
  158.         graph[u].pb(v) ;
  159.         graph[v].pb(u) ;
  160.     }
  161.     memset(P,-1,sizeof(P));
  162.     DFS() ;
  163.     pre(N) ;
  164.     rep(i,1,M)
  165.     {
  166.         int u,v ;
  167.         cin >> u >> v ;
  168.         queries[i].index = i ;
  169.         int lca = LCA(u,v) ;
  170.         // u should be upper
  171.         if(depth[u] > depth[v])swap(u,v) ;
  172.         if(lca==u || lca==v)
  173.         {
  174.             // first case
  175.             queries[i].L = start[u] ;
  176.             queries[i].R = start[v] ;
  177.             queries[i].flag = -1 ;
  178.         }
  179.         else
  180.         {
  181.             queries[i].L = endd[u] ;
  182.             queries[i].R = start[v] ;
  183.             queries[i].flag = start[lca] ;
  184.         }
  185.     }
  186.     sort(queries+1 , queries+1+M , compare) ;
  187.     ans = 0 ;
  188.     int curl = queries[1].L , curr = queries[1].R ;
  189.     //trace(curl,curr);
  190.     rep(i,curl,curr)
  191.         check(i);
  192.     answers[queries[1].index] = ans ;
  193.     if(queries[1].flag != -1) {
  194.         check(queries[1].flag) ;
  195.         answers[queries[1].index] = ans ;
  196.         check(queries[1].flag) ;
  197.     }
  198.     rep(i,2,M)
  199.     {
  200.         while(curl < queries[i].L)
  201.             check(curl++) ;
  202.         while(curl > queries[i].L)
  203.             check(--curl) ;
  204.         while(curr < queries[i].R)
  205.             check(++curr) ;
  206.         while(curr > queries[i].R)
  207.             check(curr--) ;
  208.         answers[queries[i].index] = ans ;
  209.         if(queries[i].flag != -1) {
  210.             check(queries[i].flag) ;
  211.             answers[queries[i].index] = ans ;
  212.             check(queries[i].flag) ;
  213.         }
  214.     }
  215.     rep(i,1,M)cout << answers[i] << '\n' ;
  216.     return 0;
  217. }
  218.  
Success #stdin #stdout 0s 18168KB
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/xLy3AK
language:
C++14 (gcc 8.3)
created:
8 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!