fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define el "\n"
  5. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define __ROOT__ int main()
  7. #define fi first
  8. #define se second
  9. #define M 1000000007
  10. #define MAXN 100001
  11. #define GIOIHAN 1000001
  12. #define BLOCK_SIZE 425
  13. #define MAX_NODE 1001001
  14. #define LOG 19
  15. #define ALPHA_SIZE 26
  16. #define BASE 311
  17. #define NAME "file"
  18. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); // dùng để nén sort mảng compare
  19. using namespace std;
  20. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  21. const ll NMOD = 1;
  22. const int dx[] = {-1, 0, 1,0};
  23. const int dy[] = {0, 1, 0, -1};
  24. //**Variable**//
  25. ll n, q  ;
  26. ll c[MAXN];
  27. ll chainID[MAXN] ;
  28. ll chainHead[MAXN] ;
  29. ll sz[MAXN]  ;
  30. ll high[MAXN] ;
  31. ll par[MAXN] ;
  32. ll st[MAXN] ;
  33. ll fin[MAXN]  ;
  34. ll res[MAXN] ;
  35. ll tour[MAXN] ;
  36. ll timedfs = 0, curchain = 1 ;
  37. vector<ll> adj[MAXN];
  38. //**Struct**//
  39. struct query {
  40.     ll u, v,color, id  ;
  41.     bool operator < (const query & other   ) const {
  42.         return color < other.color  ;
  43.     }
  44. } que[MAXN];
  45.  
  46. struct Seg {
  47.     ll val[MAXN<<2]  ;
  48.     void update(ll id,ll l, ll r, ll pos, ll value) {
  49.         if(l ==r ) {
  50.             val[id]+= value ;
  51.         } else {
  52.             ll m = l + r >> 1 ;
  53.             if(m >= pos )update(id<<1, l, m, pos, value ) ;
  54.             else update(id<<1|1, m + 1, r, pos,value     ) ;
  55.             val[id] = val[id<<1] + val[id<<1|1] ;
  56.         }
  57.     }
  58.     ll get(ll id, ll l, ll r, ll u, ll v ) {
  59.         if(v < l || u > r ) return 0  ;
  60.         if(u <= l && v >=r ) return val[id] ;
  61.         ll m = l + r >> 1;
  62.         return get(id<<1, l, m, u, v) + get(id<<1|1, m + 1, r, u, v    ) ;
  63.     }
  64. } seg;
  65. //**Function**//
  66.  
  67. struct Data {
  68.     ll color, pos ;
  69.     bool operator < (const Data & other ) const {
  70.         return color < other.color ;
  71.     }
  72. };
  73. multiset<Data> ms ;
  74. void dfs(ll u, ll p  ) {
  75.     sz[u] = 1 ;
  76.     for(ll v : adj[u]) {
  77.         if(v == p ) continue ;
  78.         par[v] = u  ;
  79.         high[v]= high[u] + 1 ;
  80.         dfs(v,  u) ;
  81.         sz[u] += sz[v] ;
  82.     }
  83. }
  84. void hld(ll u, ll p ) {
  85.     if(!chainHead[curchain]) {
  86.         chainHead[curchain ]  = u  ;
  87.     }
  88.     st[u] = ++ timedfs ;
  89.     tour[timedfs ]  = u ;
  90.     chainID[u] = curchain ;
  91.     ll nxt = 0 ;
  92.     for(ll v : adj[u]) {
  93.         if(p == v ) continue ;
  94.         if(!nxt || sz[v]> sz[nxt ] ) nxt = v ;
  95.     }
  96.     if(nxt ) hld(nxt, u) ;
  97.     for(ll v : adj[u]) {
  98.         if(v != p && v != nxt ) {
  99.             curchain ++ ;
  100.             hld(v, u ) ;
  101.         }
  102.     }
  103.     fin[u]= timedfs ;
  104. }
  105. void init() {
  106.     cin>>n>> q ;
  107.     for(ll i = 1 ; i <= n ; i ++ ) {
  108.         cin>>c[i];
  109.         ms.insert({c[i], i  }) ;
  110.     }
  111.     for(ll i =1 ; i <= n - 1;  i ++  ) {
  112.         ll x,  y ;
  113.         cin>>x>> y ;
  114.         adj[x].push_back(y) ;
  115.         adj[y].push_back(x) ;
  116.     }
  117.     for(ll i = 1 ; i <= q;  i ++ ) {
  118.         cin>>que[i].u >> que[i].v >> que[i].color ;
  119.         que[i].id = i  ;
  120.     }
  121.     sort(que + 1, que + q + 1) ;
  122.     dfs(1, 1 ) ;
  123.     hld(1, 1 ) ;
  124. }
  125. ll LCA(ll u, ll v) {
  126.     while(chainID[u] != chainID[v]) {
  127.         if(chainID[u] > chainID[v]) u = par[chainHead[chainID[u]]];
  128.         else  v = par[chainHead[chainID[v]]];
  129.     }
  130.     return high[u] > high[v] ? v : u ;
  131. }
  132. bool query(ll u, ll v ) {
  133.     ll lca = LCA(u, v ) ;
  134.     while(chainID[u] != chainID[lca]) {
  135.         if(seg.get(1,1, n, st[chainHead[chainID[u]]], st[u])) return true ;
  136.         u = par[chainHead[chainID[u]]] ;
  137.     }
  138.     while(chainID[v] != chainID[lca]) {
  139.         if(seg.get(1,1, n, st[chainHead[chainID[v]]], st[v])) return true ;
  140.         v = par[chainHead[chainID[v]]] ;
  141.     }
  142.     if(high[u] > high[v]) swap(u, v);
  143.     return seg.get(1, 1, n, st[u], st[v]) ;
  144. }
  145. stack<Data > sta ;
  146. void solve() {
  147.     ll cur_color =  que[1].color ;
  148.     for(ll i =1 ; i <= q ; i ++ ) {
  149.         if(cur_color != que[i].color ) {
  150.             while(!sta.empty()) {
  151.                 Data t = sta.top() ;
  152.                 sta.pop() ;
  153.                 seg.update(1, 1, n,st[t.pos],-1  ) ;
  154.             }
  155.         }
  156.         cur_color = que[i].color ;
  157.         while(!ms.empty() ) {
  158.             Data t = *ms.begin() ;
  159.             if(cur_color > t.color )ms.erase(ms.begin());
  160.             else break ;
  161.         }
  162.         while(!ms.empty()) {
  163.             Data t = * ms.begin() ;
  164.             if(t.color == cur_color) {
  165.                 seg.update(1,  1, n, st[t.pos], 1);
  166.                 sta.push(t) ;
  167.                 ms.erase(ms.begin()) ;
  168.             } else break;
  169.         }
  170.         res[que[i].id] = query(que[i].u, que[i].v) ;
  171.     }
  172.     for(ll i = 1 ; i <= q ; i ++  ) cout<<res[i] ;
  173. }
  174.  
  175. __ROOT__ {
  176. //     freopen(NAME".inp" , "r" , stdin);
  177. //     freopen(NAME".out" , "w", stdout) ;
  178.     fast;
  179.     init();
  180.     solve();
  181. }
  182.  
  183.  
Success #stdin #stdout 0.01s 15944KB
comments (?)
stdin
copy 
6 4
1 2 3 3 3 3
1 2
2 3
3 4
2 5
5 6
4 6 1
4 6 2
4 6 3
4 6 4
stdout
copy 
0110
https://ideone.com/qX9QVM
language:
C++14 (gcc 8.3)
created:
241 days 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!