description: You are given a tree consisting of n vertices. Recall that a tree is an undirected connected acyclic graph. The given tree is rooted at the vertex 1.
  
  You have to process q queries. In each query, you are given a vertex of the tree v and an integer k.
  
  To process a query, you may delete any vertices from the tree in any order, except for the root and the vertex v. When a vertex is deleted, its children become the children of its parent. You have to process a query in such a way that maximizes the value of c(v) - m ⋅ k (where c(v) is the resulting number of children of the vertex v, and m is the number of vertices you have deleted). Print the maximum possible value you can obtain.
  
  The queries are independent: the changes you make to the tree while processing a query don't affect the tree in other queries.
  
  Input
  
  The first line contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the number of vertices in the tree.
  
  Then n-1 lines follow, the i-th of them contains two integers x_i and y_i (1 ≤ x_i, y_i ≤ n; x_i ≠ y_i) — the endpoints of the i-th edge. These edges form a tree.
  
  The next line contains one integer q (1 ≤ q ≤ 2 ⋅ 10^5) — the number of queries.
  
  Then q lines follow, the j-th of them contains two integers v_j and k_j (1 ≤ v_j ≤ n; 0 ≤ k_j ≤ 2 ⋅ 10^5) — the parameters of the j-th query.
  
  Output
  
  For each query, print one integer — the maximum value of c(v) - m ⋅ k you can achieve.
  
  Example
  
  Input
  
  
  8
  6 7
  3 2
  8 3
  5 7
  7 4
  7 1
  7 3
  6
  1 0
  1 2
  1 3
  7 1
  5 0
  7 200000
  
  
  Output
  
  
  5
  2
  1
  4
  0
  4
  
  Note
  
  The tree in the first example is shown in the following picture:
  
  <image>
  
  Answers to the queries are obtained as follows:
  
    1. v=1,k=0: you can delete vertices 7 and 3, so the vertex 1 has 5 children (vertices 2, 4, 5, 6, and 8), and the score is 5 - 2 ⋅ 0 = 5; 
    2. v=1,k=2: you can delete the vertex 7, so the vertex 1 has 4 children (vertices 3, 4, 5, and 6), and the score is 4 - 1 ⋅ 2 = 2. 
    3. v=1,k=3: you shouldn't delete any vertices, so the vertex 1 has only one child (vertex 7), and the score is 1 - 0 ⋅ 3 = 1; 
    4. v=7,k=1: you can delete the vertex 3, so the vertex 7 has 5 children (vertices 2, 4, 5, 6, and 8), and the score is 5 - 1 ⋅ 1 = 4; 
    5. v=5,k=0: no matter what you do, the vertex 5 will have no children, so the score is 0; 
    6. v=7,k=200000: you shouldn't delete any vertices, so the vertex 7 has 4 children (vertices 3, 4, 5, and 6), and the score is 4 - 0 ⋅ 200000 = 4. 
solution: #include <bits/stdc++.h>
  using namespace std;
  const int INF = 1e9 + 239;
  struct Line {
    int first;
    int step;
    Line() {
      first = -INF;
      step = -INF;
    }
    Line(int k_, int b_) {
      first = k_;
      step = b_;
    }
    bool ok() const { return *this != Line(); }
    Line operator+(const Line &other) const {
      if (!ok()) {
        return other;
      }
      if (!other.ok()) {
        return *this;
      }
      return Line(first + other.first, step + other.step);
    }
    Line skip(int len) const { return Line(first + len * step, step); }
    bool operator==(const Line &other) const {
      return first == other.first && step == other.step;
    }
    bool operator!=(const Line &other) const { return !((*this) == other); }
  };
  struct Segment {
    int l;
    int r;
    int first;
    int step;
    Segment() {
      l = 0;
      r = 0;
      first = 0;
      step = 0;
    }
    Segment(int l_, int r_, int first_, int step_) {
      l = l_;
      r = r_;
      first = first_;
      step = step_;
    }
  };
  const int N = 2e5 + 7;
  const int L = 20;
  const Line NONE = Line();
  namespace ST {
  int a[N];
  Line mod_set[4 * N];
  Line mod_add[4 * N];
  vector<int> mod_points;
  void apply_set(int v, Line x) {
    mod_set[v] = x;
    mod_add[v] = NONE;
  }
  void apply_add(int v, Line x) {
    if (mod_set[v].ok()) {
      mod_set[v] = mod_set[v] + x;
    } else {
      mod_add[v] = mod_add[v] + x;
    }
  }
  void push(int v, int l, int r) {
    assert(l + 1 < r);
    if (mod_set[v].ok()) {
      int m = (r + l) >> 1;
      apply_set(2 * v + 1, mod_set[v]);
      apply_set(2 * v + 2, mod_set[v].skip(m - l));
    }
    mod_set[v] = NONE;
    if (mod_add[v].ok()) {
      int m = (r + l) >> 1;
      apply_add(2 * v + 1, mod_add[v]);
      apply_add(2 * v + 2, mod_add[v].skip(m - l));
    }
    mod_add[v] = NONE;
  }
  void set(int v, int l, int r, int ql, int qr, Line x) {
    if (qr <= l || r <= ql) {
      return;
    } else if (ql <= l && r <= qr) {
      apply_set(v, x);
    } else {
      push(v, l, r);
      int m = (r + l) >> 1;
      set(2 * v + 1, l, m, ql, qr, x);
      set(2 * v + 2, m, r, ql, qr, x.skip(m - l));
    }
  }
  void add(int v, int l, int r, int ql, int qr, Line x) {
    if (qr <= l || r <= ql) {
      return;
    } else if (ql <= l && r <= qr) {
      apply_add(v, x);
    } else {
      push(v, l, r);
      int m = (r + l) >> 1;
      add(2 * v + 1, l, m, ql, qr, x);
      add(2 * v + 2, m, r, ql, qr, x.skip(m - l));
    }
  }
  void eval(int v, int l, int r, int pos, int &ans) {
    if (l + 1 == r) {
      if (mod_set[v].ok()) {
        ans = mod_set[v].first;
      } else {
        if (mod_add[v].ok()) {
          ans = mod_add[v].first;
        } else {
          assert(false);
          ans = 0;
        }
      }
    } else {
      push(v, l, r);
      int m = (r + l) >> 1;
      if (pos < m) {
        eval(2 * v + 1, l, m, pos, ans);
      } else {
        eval(2 * v + 2, m, r, pos, ans);
      }
    }
  }
  void set(int l, int r, Line x) {
    mod_points.push_back(l);
    mod_points.push_back(r);
    x.first -= l * x.step;
    set(0, 0, N, l, r + 1, x);
  }
  void add(int l, int r, Line x) {
    mod_points.push_back(l);
    mod_points.push_back(r);
    x.first -= l * x.step;
    add(0, 0, N, l, r + 1, x);
  }
  int eval(int x) {
    if (x == N) return 0;
    int ans = 0;
    eval(0, 0, N, x, ans);
    return ans;
  }
  void clear() {
    set(0, N - 1, Line(0, 0));
    mod_points.clear();
    mod_points.push_back(0);
  }
  void max_eq(int val) {
    if (eval(N - 1) >= val) {
      return;
    }
    int c = N - 1;
    for (int i = L - 1; i >= 0; i--) {
      if (c - (1 << i) >= 0 && eval(c - (1 << i)) < val) {
        c -= (1 << i);
      }
    }
    set(c, N - 1, Line(val, 0));
  }
  void sub() { add(0, N - 1, Line(0, -1)); }
  void add(Segment f) { add(f.l, f.r, Line(f.first, f.step)); }
  vector<Segment> get_vals() {
    sort(mod_points.begin(), mod_points.end());
    mod_points.resize(unique(mod_points.begin(), mod_points.end()) -
                      mod_points.begin());
    vector<Segment> ans;
    for (int i = 0; i < (int)mod_points.size(); i++) {
      int l = mod_points[i];
      int r = N - 1;
      if (i + 1 < (int)mod_points.size()) {
        r = mod_points[i + 1] - 1;
      }
      ans.push_back(Segment(l, r, eval(l), eval(l + 1) - eval(l)));
    }
    return ans;
  }
  }  // namespace ST
  int sz[N];
  vector<int> fg[N];
  vector<int> sg[N];
  void dfs_init(int cur, int p) {
    sz[cur] = 1;
    for (auto t : fg[cur]) {
      if (t != p) {
        dfs_init(t, cur);
        sz[cur] += sz[t];
        sg[cur].push_back(t);
      }
    }
    sort(sg[cur].begin(), sg[cur].end(),
         [&](int i, int j) { return sz[i] > sz[j]; });
  }
  int ans[N];
  vector<pair<int, int *>> queries[N];
  void dfs_solve(int cur) {
    if (sg[cur].empty()) {
      return;
    }
    vector<Segment> cadd;
    for (int i = 1; i < (int)sg[cur].size(); i++) {
      int t = sg[cur][i];
      ST::clear();
      dfs_solve(t);
      ST::sub();
      ST::max_eq(1);
      auto tmp = ST::get_vals();
      for (auto seg : tmp) {
        cadd.push_back(seg);
      }
    }
    {
      ST::clear();
      dfs_solve(sg[cur][0]);
      ST::sub();
      ST::max_eq(1);
      for (auto seg : cadd) {
        ST::add(seg);
      }
    }
    for (auto t : queries[cur]) {
      *t.second = ST::eval(t.first);
    }
  }
  signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i + 1 < n; i++) {
      int u, v;
      cin >> u >> v;
      u--;
      v--;
      fg[u].push_back(v);
      fg[v].push_back(u);
    }
    dfs_init(0, -1);
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
      int v, k;
      cin >> v >> k;
      v--;
      queries[v].push_back({k, &ans[i]});
    }
    dfs_solve(0);
    for (int i = 0; i < q; i++) {
      cout << ans[i] << '\n';
    }
  }
  