fork download
copy 
  1. // ROOT : DRAGON3012009
  2. #include <bits/stdc++.h>
  3. #define ll int
  4. #define ld long double
  5. #define el "\n"
  6. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  7. #define __ROOT__ int main()
  8. #pragma GCC optimize("O2")
  9. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  10. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  11. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  12. #define fi first
  13. #define se second
  14. #define M 1000000007
  15. #define MAXN 80001
  16. #define INF (1ll<<30)
  17. #define BLOCK_SIZE 800
  18. #define MAX_NODE 1001001
  19. #define LOG 19
  20. #define ALPHA_SIZE 26
  21. #define BASE 311
  22. #define NAME "file"
  23. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  24. using namespace std;
  25. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  26. const ll NMOD = 1;
  27. const int dx[] = {-1, 0, 1,0};
  28. const int dy[] = {0, 1, 0, -1};
  29.  
  30. //**Variable**//
  31. ll n, num_color = 0, que ;
  32. ll c[MAXN];
  33. ll high[MAXN] ;
  34. ll deg[MAXN] ;
  35. ll dis[MAXN / BLOCK_SIZE][MAXN] ;
  36. vector<ll> adj[MAXN] ;
  37. vector<ll> color[MAXN] ;
  38. bool heavy[MAXN] ;
  39. vector<ll> cpr;
  40. unordered_map<ll,ll> mp ;
  41.  
  42. // For LCA with RMQ
  43. vector<int> euler, depth, first(MAXN);
  44. int st[LOG+1][2 * MAXN];
  45. int lg[2 * MAXN];
  46.  
  47. //**Function**//
  48. template<class X, class Y >
  49. bool minimize(X & x, const Y &y ) { return x > y ? x = y, 1:0 ; }
  50. template<class X, class Y >
  51. bool maximize(X &x, const Y &y ) { return x < y ? x = y, 1:0 ; }
  52.  
  53. void dfs_euler(int u, int p, int d) {
  54.     first[u] = euler.size();
  55.     euler.push_back(u);
  56.     depth.push_back(d);
  57.     for (int v : adj[u]) if (v != p) {
  58.         dfs_euler(v, u, d + 1);
  59.         euler.push_back(u);
  60.         depth.push_back(d);
  61.     }
  62. }
  63.  
  64. void build_sparse() {
  65.     int m = euler.size();
  66.     for (int i = 0; i < m; ++i) st[0][i] = i;
  67.     for (int i = 2; i <= m; ++i) lg[i] = lg[i / 2] + 1;
  68.     for (int k = 1; (1 << k) <= m; ++k) {
  69.         for (int i = 0; i + (1 << k) <= m; ++i) {
  70.             int x = st[k - 1][i];
  71.             int y = st[k - 1][i + (1 << (k - 1))];
  72.             st[k][i] = (depth[x] < depth[y] ? x : y);
  73.         }
  74.     }
  75. }
  76.  
  77. int LCA(int u, int v) {
  78.     int L = first[u], R = first[v];
  79.     if (L > R) swap(L, R);
  80.     int k = lg[R - L + 1];
  81.     int x = st[k][L], y = st[k][R - (1 << k) + 1];
  82.     return (depth[x] < depth[y]) ? euler[x] : euler[y];
  83. }
  84.  
  85. ll dist(ll u, ll v) {
  86.     return depth[first[u]] + depth[first[v]] - 2 * depth[first[LCA(u, v)]];
  87. }
  88.  
  89. void bfs(ll co) {
  90.     queue<ll> q ;
  91.     for(ll v : color[co ]) {
  92.         dis[co][v] = 0 ;
  93.         q.push(v) ;
  94.     }
  95.     while(!q.empty()) {
  96.         ll u = q.front() ; q.pop() ;
  97.         for(ll v : adj[u]) {
  98.             if(dis[co][v] == 0 && v != u) {
  99.                 dis[co][v] = dis[co][u] + 1 ;
  100.                 q.push(v) ;
  101.             }
  102.         }
  103.     }
  104. }
  105.  
  106. void init() {
  107.     cin>>n >> que ;
  108.     FOR(i,1, n) cin >> c[i], cpr.push_back(c[i]), mp[c[i]]++;
  109.     compare(cpr) ;
  110.     num_color = cpr.size() ;
  111.     FOR(i, 1,n) {
  112.         c[i] = lower_bound(cpr.begin(), cpr.end(), c[i]) - cpr.begin() + 1;
  113.         deg[c[i]] ++ ;
  114.         color[c[i]].push_back(i) ;
  115.     }
  116.     FOR(i, 1, n -1 ) {
  117.         ll x, y ; cin >> x>> y ;
  118.         adj[x].push_back(y) ;
  119.         adj[y].push_back(x) ;
  120.     }
  121.     // LCA preprocess
  122.     dfs_euler(1, 0, 0);
  123.     build_sparse();
  124.     FOR(i, 1, num_color) if(deg[i] >= BLOCK_SIZE ) bfs(i) ;
  125. }
  126.  
  127. void solve() {
  128.     FOR(i, 1,que ) {
  129.         ll u, c ; cin >> u >> c ;
  130.         if(mp[c] == 0 ) {
  131.             cout << -1 << el ;
  132.             continue ;
  133.         }
  134.         c = lower_bound(cpr.begin(), cpr.end(), c  ) - cpr.begin() + 1 ;
  135.         if(deg[c] >= BLOCK_SIZE) cout << dis[c][u] << el ;
  136.         else  {
  137.             ll ans = INF ;
  138.             for(ll v : color[c]) minimize(ans, dist(u, v )) ;
  139.             cout << ans << el ;
  140.         }
  141.     }
  142. }
  143.  
  144. __ROOT__ {
  145.     fast;
  146.     int t =1 ;
  147.     while(t-- ) {
  148.         init();
  149.         solve();
  150.     }
  151. }
Success #stdin #stdout 0.01s 11716KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0XIWxn
language:
C++14 (gcc 8.3)
created:
1 day 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!