Submission #29487166

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using ll = long long;
using std::cin;
using std::cout;
using std::endl;
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template <class T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using ll = long long;
using std::cin;
using std::cout;
using std::endl;
std::mt19937 rnd(std::chrono::steady_clock::now().time_since_epoch().count());
template <class T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return 1;
  }
  return 0;
}
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

namespace KKT89
{
template <typename T>
struct Compress
{
  std::vector<T> v;
  Compress() {}
  Compress(std::vector<T> _v) : v(_v) { build(); }

  void add(T x)
  {
    v.emplace_back(x);
  }

  void build()
  {
    std::sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
  }

  int get(T x)
  {
    return std::lower_bound(v.begin(), v.end(), x) - v.begin();
  }

  T &operator[](int i) { return v[i]; }

  int size()
  {
    return (int)v.size();
  }
};
} // namespace KKT89

namespace KKT89
{
template <typename T>
struct BinaryIndexedTree
{
  int n;
  std::vector<T> bit;
  BinaryIndexedTree() : n(0) {}
  BinaryIndexedTree(int _n) : n(_n) { bit = std::vector<T>(n + 1); }
  void add1(int idx, T val)
  {
    for (int i = idx; i <= n; i += i & -i)
      bit[i] += val;
  }
  T sum1(int idx) const
  {
    T res = 0;
    for (int i = idx; i > 0; i -= i & -i)
      res += bit[i];
    return res;
  }
  // 0-indexed
  void add(int idx, T val) { add1(idx + 1, val); }
  // 0-indexed [left, right)
  [[nodiscard]] T sum(int left, int right) const { return sum1(right) - sum1(left); }

  int lower_bound(T x) const
  {
    int res = 0;
    int k = 1;
    while (2 * k <= n)
      k <<= 1;
    for (; k > 0; k >>= 1)
    {
      if (res + k <= n and bit[res + k] < x)
      {
        x -= bit[res + k];
        res += k;
      }
    }
    return res;
  }

  void reset()
  {
    bit.assign(n + 1, 0);
  }
};

} // namespace KKT89

void solve()
{
  int n, Q;
  cin >> n >> Q;
  KKT89::Compress<int> comp;
  std::vector<int> x(n);
  for (int i = 0; i < n; ++i)
  {
    cin >> x[i];
    comp.add(x[i]);
  }
  comp.build();
  std::vector<std::vector<int>> g(n);
  for (int i = 1; i < n; ++i)
  {
    int u, v;
    cin >> u >> v;
    u -= 1, v -= 1;
    g[u].emplace_back(v);
    g[v].emplace_back(u);
  }
  std::vector<int> V(Q), K(Q);
  for (int i = 0; i < Q; ++i)
  {
    cin >> V[i] >> K[i];
    V[i] -= 1;
  }

  // オイラーツアー
  std::vector<int> in(n), out(n);

  // V[i], in[i]
  // V が大きい方からソート
  std::vector<std::pair<int, int>> vp(n);
  {
    int idx = 0;
    auto dfs = [&in, &out, &g, &idx](auto &&self, const int cur, const int pre) -> void
    {
      in[cur] = idx++;
      for (const auto &nxt : g[cur])
      {
        if (nxt == pre)
          continue;
        self(self, nxt, cur);
      }
      out[cur] = idx;
    };
    dfs(dfs, 0, -1);
    for (int i = 0; i < n; ++i)
    {
      vp[i] = {comp.get(x[i]), in[i]};
    }
    std::sort(vp.rbegin(), vp.rend());
  }
  KKT89::BinaryIndexedTree<int> bit(n);
  // 並列二分探索
  std::vector<int> lf(Q), rg(Q, comp.size());
  // V, K, query_id
  std::vector<std::vector<std::tuple<int, int, int>>> query(n);
  while (true)
  {
    bool exit = true;
    query.clear();
    query.resize(comp.size());
    bit.reset();
    for (int i = 0; i < Q; ++i)
    {
      if (rg[i] - lf[i] > 1)
      {
        exit = false;
        const int mid = (lf[i] + rg[i]) >> 1;
        query[mid].emplace_back(V[i], K[i], i);
      }
    }
    if (exit)
      break;

    int cur = 0;
    for (int val = comp.size() - 1; val >= 0; --val)
    {
      while (cur < n and vp[cur].first >= val)
      {
        bit.add(vp[cur].second, 1);
        cur += 1;
      }
      for (const auto &[v, k, id] : query[val])
      {
        const int cnt = bit.sum(in[v], out[v]);
        if (k <= cnt)
        {
          lf[id] = val;
        }
        else
        {
          rg[id] = val;
        }
      }
    }
  }
  for (int i = 0; i < Q; ++i)
  {
    cout << comp[lf[i]] << "\n";
  }
}

int main()
{
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  int I_love_KKT89 = 1;
  while (I_love_KKT89--)
    solve();
  return 0;
}

Submission Info

Judge Result