题解：P15654 [省选联考 2026] 工业系统 / industry

tiger2005 · 2026-03-10 14:02:21 · 题解

先写个 \mathcal{O} ((n + m) \sqrt {n}) 的做法，如果存在 polylog 做法会考虑更新一下。

本题涉及到以下步骤：

• 证明 a_{x, y} 的种类很少，并求出它们的全局排名；
• 观察全局排名满足的性质，从而解决 o_x o_y = 0 的部分；
• 解决 o_x = o_y = 1 的部分。

第一步：确定全局排名

首先，收集所有后代的产物并非必要，实际上只需要收集儿子的产物。原因在于：对于任意一个儿子，其对应产物本身已经递归地编码了整棵子树的信息，因此比较两个结点的产物集合时，只比较儿子产物集合即可。

更具体地，设两个需要比较的后代产物集合分别为 a_{x, y} 和 a_{x, z}。不断从中取出当前最大的元素，分别记为 a_{x, u} 和 a_{x, v}，则 u 和 v 分别是 y 和 z 的儿子。随后从 a_{x, y} 中取出 u 子树内的所有 a_{x, \circ}，对 a_{x, z} 同理。过程不断循环直到比出大小为止。

另外，a_{x, y} 可以看作将结点 y 指向结点 x 的边断开之后，剩余部分的有根树结构。由于树上只有 n-1 条边，并且每条边断开之后只会产生两个连通块，因此在不考虑 a_{x, x} 的前提下，不同的 a_{x, y} 种类数不超过 2 n - 2。

对于后面的讨论，从有向边的视角考虑更加有利。下面约定：

• 对于树上有向边 p = (u \to v)，定义 P(p) = P(u \to v) = A(v, u)；
• 对于根 r，定义 E_r 表示将树上所有边同时指向 r 得到的有向边集合；
• 定义 f_r(p) = 2 + \sum_{q \in E_r} [P(q) > P(p)]

  即固定根为 r 时，比 P(p) 大的集合个数再加上 2。这里加 2 是因为 a_{r, r} 总会是最大的集合。

考虑对所有 P(p) 求出它们的全局排名，也即计算 \# P(p) \in \mathbb{Z}^+，使得 P(p_1) < P(p_2) 当且仅当 \# P(p_1) < \# P (p_2)。在计算 P(u \to v) 时，需要知道 u 的其他入边对应的集合情况，因此可以使用“拓扑排序”的方式，按照从小到大的顺序枚举所有 P(p)，并处理 P(p) 相同的情况。处理步骤如下：

• 将所有叶结点的出边对应的 P(p) 加入到堆中；
• 接下来，不断从堆中取出最小的 P(p)，令 p = u \to v，随后根据它和上次取出的集合大小决定是否将排名加 1。然后：
  • 如果 v 的所有入边中只有一条的排名未知，那么可以将其他入边的集合收集起来，得到对应的出边集合，并加入到堆中；
  • 如果 v 的所有入边排名已知，那么可以直接计算出所有出边的集合（除了上一步已经添加的集合外），并加入到堆中。

可以证明，在上述规则下，所有有向边对应的集合会被枚举恰好一次。另外，集合需要使用恰当的数据结构维护，从而支持如下操作：

• 加入一个正整数；
• 将某个集合中的某个元素去除，形成新的集合，且原集合不受影响；
• 将两个集合排序后比较字典序。

可以使用任意合适的方式处理，包括但不限于字符串哈希、主席树上哈希等。

第二步：o_x o_y = 0 的部分

首先考虑 P(p) 的性质：

• 对于 E_r 内的所有有向边 p，P(p) 共同组成了以 r 为根时，除了最大集合之外的其余 n-1 个集合；
• 考虑两个结点 r_1 和 r_2，当根从 r_1 移动到 r_2 时，E_{r_2} 可以通过在 E_{r_1} 内将 r_2 \to r_1 路径上所有边反向得到；
• 对于路径 y \to v_1 \to \dots \to \red{r_1 \leftarrow \dots \leftarrow r_2}

  如果将根从 r_1 向远处移动到 r_2，需要将路径 r_2 \to r_1 上的有向边反向，变成

  y \to v_1 \to \dots \to \red{r_1 \to \dots \to r_2}

  根据单调性，路径 r_1 \to r_2 上所有有向边对应的集合都大于 P(y \to v_1)，因此

  f_{r_2} (y \to v_1) \geq f_{r_1} (y \to v_1)

  简单而言就是：根远离边时，排名单调不降。

考虑对每个结点 u 计算以 u 为根时所有集合的全局排名，需要注意到对于结点 x 和它的一个相邻结点 v，可以从 x 对应的结果中删去 \# P(v \to x) 并加上 \# P(x \to v)，得到 v 对应的结果。使用主席树完成这部分计算之后，o_x = o_y = 0 的情况就可以 \mathcal{O} (\log n) 计算了。

随后考虑利用单调性计算 o_x 和 o_y 中恰好有一个 1 的情况。

• 如果 o_x = 0，o_y = 1，此时根固定，考虑路径 t - v_1 - v_2 - \dots - s，按照从左到右的方向考虑，由于有向边对应的集合依次增大，那么对应的排名也就依次减小，使用二分算法即可得到答案；

• 如果 o_x = 1，o_y = 0，此时有向边固定，考虑路径 t - v_1 - v_2 - \dots - s，按照从左到右的方向考虑，由于根不断远离结点 t，那么集合 P(t \to v_1) 对应的排名会不断上升，依然可以使用二分算法得到答案。

上述部分可以做到单次询问 \mathcal{O} (\log^2 n)。

第三步：o_x = o_y = 1 的部分

考虑路径

并研究 f_{v_i} (\green{v_{0} \to v_{1}}) 和 f_{v_{i+1}} (v_i \to v_{i+1}) 满足的性质。

根据上一步得到的性质，随着 i 的增大，v_i 不断远离 v_0，因此 f_{v_i} (\green{v_0 \to v_1}) 单调不降。进一步考虑将根从 v_i 移动到 v_{i+1} 的过程，此时二者的差别仅在于：集合 P(\blue{v_{i+1} \to v_i}) 被替换为 P(\red{v_i \to v_{i+1}})。

已知 P(\red{v_i \to v_{i+1}}) > P(\green{v_0 \to v_1})，因此：

• 如果 P(\blue{v_{i+1} \to v_i}) > P(\green{v_0 \to v_1})，则 f_{v_{i+1}} (\green{v_0 \to v_1}) = f_{v_i} (\green{v_0 \to v_1})
• 否则， f_{v_{i+1}} (\green{v_0 \to v_1}) = f_{v_i} (\green{v_0 \to v_1}) + 1

进一步结合 P(v_{i+1} \to v_i) 的单调性，可以得到如下结论：存在一个边界值，当 i 小于该边界值时满足上述第一个条件，否则满足上述第二个条件。因此，序列 f_{v_i} (\green{v_0 \to v_1}) 的前缀为恒定值，而后缀为一个公差为 1 的等差数列。

接下来考虑序列 f_{v_{i+1}} (v_i \to v_{i+1})。需要注意到：

• f_{\underline{v_{i+2}}} (v_i \to v_{i+1}) \leq f_{\underline{v_{i+1}}} (v_i \to v_{i+1}) + 1
• f_{v_{i+2}} (\underline{v_{i+1} \to v_{i+2}}) < f_{v_{i+2}} (\underline{v_i \to v_{i+1}})

  （这个不等式是不取等的，因为 P(v_{i+1} \to v_{i+2}) > P(v_i \to v_{i+1})，比较二者时 f_{v_{i+2}} (v_i \to v_{i+1}) 会带来额外的贡献。）

综合上述两个不等式可以得到

因此序列 f_{v_{i+1}} (v_i \to v_{i+1}) 是单调不升的。

接下来，考虑满足 o_x = o_y = 1 的询问，不妨假设 x 相较于 y 更靠近 s，另一种情况完全对称。接下来固定 y，并考虑所有可以取到的 x：

此时需要统计有多少个 x_i 满足 f_{x_i} (y \to x_1) \leq r。

如果 f_{x_i} (y \to x_1) 仅满足单调性，那么统计起来仍然比较困难；但是根据前面的讨论，f_{x_i} (y \to x_1) 形成了“前缀恒定，后缀递增”的序列，在这个前提下就可以根据首尾两个值直接确定数量：

• 情况 1：如果 f_{x_1} (y \to x_1) > r，则没有满足条件的 x_i；
• 情况 2：否则，如果 f_s (y \to x_1) \leq r，则所有 x_i 均满足条件；
• 情况 3：否则，x_i 满足条件当且仅当 1 \leq i \leq d - f_s (y \to x_1) + r。

这样就对每个 y 确定了其产生的贡献，随后将所有 y 放在一起考虑。对于路径

根据单调性，路径中的某一个前缀满足情况 1，某一个后缀满足情况 2，而情况 3 可以看作中间的一个区间，不妨表示为 [y_L, y_R]。情况 1 和情况 2 对应的贡献可以使用简单的数学运算得到，而为了计算情况 3 的总贡献，需要解决如下问题：对于所有 L \leq i \leq R，计算 \sum f_s (y_i \to y_{i+1})。

对于这个问题，可以对所有有向边预处理 f_1 (p)，并借助这一结果得到 f_s (p)。此时，只有 s \to 1 路径上的有向边会被反转，变成 1 \to s。为了计算反转带来的贡献，需要实现这样的问题：

• 给定两条有向路径 a \to b 和 c \to d，分别取出两个有向边 p 和 q，有多少组 (p, q) 满足 P(p) < P(q)？

在将询问拆成若干个端点为 1 号点的询问之后，可以通过一些根号相关算法解决，包括但不限于使用树分块将路径拆分为若干段，或者将询问离线后使用树上莫队加二次离线处理。

因此，本题最终的时间复杂度为 \mathcal{O} ((n + m) \sqrt n)，树分块做法可能需要额外注意常数问题。

::::info[代码（树分块）]

// https://qoj.ac/submission/2116021

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

using i64 = long long;
using u64 = unsigned long long;

int MAX_RK;
// 第零部分：树上的基础操作
int n;
int m;
vector<int> g[100010], sons[100010];
int dep[100010], sz[100010];

int dfn[100010], ord[100010], hv[100010], idx;
int tp[100010];

int fa[100010];
void dfs1(int x, int f) {
  sz[x] = 1;
  fa[x] = f;
  dep[x] = dep[f] + 1;
  for (auto v : g[x]) if (v != f) {
    dfs1(v, x);
    sz[x] += sz[v];
    if (hv[x] == 0 || sz[v] > sz[hv[x]])
      hv[x] = v;
    sons[x].push_back(v);
  }
}

void dfs2(int x, int t) {
  dfn[x] = ++ idx;
  ord[idx] = x;
  tp[x] = t;
  if (hv[x]) dfs2(hv[x], t);
  for (auto v : sons[x])
    if (v != hv[x]) dfs2(v, v);
}

inline bool inside(int x, int v) {
  return dfn[v] >= dfn[x] && dfn[v] < dfn[x] + sz[x];
}

inline int climb(int x, int d) {
  while (dep[tp[x]] > d) x = fa[tp[x]];
  return ord[dfn[x] - dep[x] + d];
}

inline int lca(int x, int y) {
  while (tp[x] != tp[y]) {
    if (dep[tp[x]] > dep[tp[y]])
      x = fa[tp[x]];
    else
      y = fa[tp[y]];
  }
  return dep[x] > dep[y] ? y : x;
}

inline int toward(int from, int lca, int to, int dist) {
  int a = dep[from] - dist;
  if (a >= dep[lca]) return climb(from, a);
  return climb(to, 2 * dep[lca] - a);
}

inline int direction(int f, int t) {
  if (f == t)
    return 0;
  if (inside(f, t))
    return climb(t, dep[f] + 1);
  return f;
}

// 主席树
namespace President {
bool ban_hash = false;
struct Node {
  int ls, rs;
  int sz;
  u64 hsh;
} tr[600010 * 18];
int nn;

void pu(int x) {
  tr[x].sz = tr[tr[x].ls].sz + tr[tr[x].rs].sz;
  if (!ban_hash)
    tr[x].hsh = (
        (tr[tr[x].ls].hsh * 0xbf58476d1ce4e5b9ULL)
      ^ (tr[tr[x].rs].hsh * 0x94d049bb133111ebULL)
      ^ tr[x].sz
    );
}

void ins(int &rt, int l, int r, int k, int v) {
  int old = rt;
  rt = ++ nn;
  tr[rt] = tr[old];
  if (l == r) {
    tr[rt].sz += v;
    tr[rt].hsh = tr[rt].sz;
    return;
  }
  int m = (l + r) >> 1;
  if (k <= m)
    ins(tr[rt].ls, l, m, k, v);
  else
    ins(tr[rt].rs, m + 1, r, k, v);
  pu(rt);
}

bool cmp_iter(int r1, int r2) {
  int l = 1, r = MAX_RK;
  while (true) {
    if (r1 == 0) return true;
    if (r2 == 0) return false;
    if (l == r) return tr[r1].sz < tr[r2].sz;
    int m = (l + r) >> 1;
    int rr1 = tr[r1].rs, rr2 = tr[r2].rs;
    if (tr[rr1].hsh != tr[rr2].hsh) {
      r1 = rr1; r2 = rr2; l = m + 1;
    } else {
      r1 = tr[r1].ls; r2 = tr[r2].ls; r = m;
    }
  }
}

int cmp(int r1, int r2) {
  if (tr[r1].hsh == tr[r2].hsh)
    return 0;
  return cmp_iter(r1, r2) ? -1 : 1;
}

int que(int rt, int l, int r, int ll) {
  if (ll <= l) return tr[rt].sz;
  int m = (l + r) >> 1;
  return (ll <= m) ?
         que(tr[rt].ls, l, m, ll) + tr[tr[rt].rs].sz :
         que(tr[rt].rs, m + 1, r, ll);
}

struct Root {
  int rt;
  Root() { rt = 0; }
  Root(int rt): rt(rt) {}
  void delta(int k, int v) {
    ins(rt, 1, MAX_RK, k, v);
  }
  int query(int l) {
    if (l == MAX_RK) return 0;
    return que(rt, 1, MAX_RK, l + 1);
  }
  bool operator < (const Root &rw) const {
    return cmp(rt, rw.rt) == 1;
  }
  bool operator == (const Root &rw) const {
    return tr[rt].hsh == tr[rw.rt].hsh;
  }
};
}
using President::Root;

// 第一部分：计算排名
int rk_up[100010], rk_dw[100010];
namespace Step1 {
/* 
  stg[x] = 1 代表周围只有一个子树未知，
    进入第一阶段，向未知方向 exclude[x] 提供结果
  stg[x] = 2 代表周围所有方向已知
    进入第二阶段，向除 exclude[x] 之外的方向提供结果
*/
int stg[100010], exclude[100010];
int ready[100010];

priority_queue<pair<Root, int>> pq;
Root rt_near[100010];

void do_stage(int x) {
  if (sons[x].empty()) return;
  if (stg[x] == 0) {
    ++ stg[x];
    if (x != 1 && rk_dw[x] == 0) {
      exclude[x] = x;
      pq.push({rt_near[x], x});
    } else {
      for (auto v : sons[x]) if (rk_up[v] == 0) {
        exclude[x] = -v;
        pq.push({rt_near[x], -v});
        break;
      }
    }
  } else {
    ++ stg[x];
    if (x != 1 && exclude[x] != x) {
      Root tmp = rt_near[x];
      tmp.delta(rk_dw[x], -1);
      pq.push({tmp, x});
    }
    for (auto v : sons[x]) if (exclude[x] != -v) {
      Root tmp = rt_near[x];
      tmp.delta(rk_up[v], -1);
      pq.push({tmp, -v});
    }
  }
}

void calc_rk() {
  for (int i = 1; i <= n; i ++)
    if ((ready[i] = sons[i].size()) == 0)
      pq.push({Root(), i});

  if (-- ready[1] == 0)
    do_stage(1);

  Root last;
  int id = 1;
  while (!pq.empty()) {
    auto [rt, x] = pq.top();
    pq.pop();
    if (!(last == rt))
      ++ id, last = rt;
    if (x > 0) {
      rk_up[x] = id;
      rt_near[fa[x]].delta(id, 1);
      if (-- ready[fa[x]] <= 0)
        do_stage(fa[x]);
    } else {
      x = -x;
      rk_dw[x] = id;
      rt_near[x].delta(id, 1);
      if (-- ready[x] <= 0)
        do_stage(x);
    }
  }

  MAX_RK = id;
}
}

// 第二部分：计算以 1 或相邻点为根时的 f 函数值
int f_up[100010], f_dw[100010];
i64 pre_up[100010], pre_dw[100010];
Root rt_total[100010];

namespace Step2 {
void dfs(int x) {
  for (auto v : sons[x]) {
    pre_up[v] = pre_up[x] + f_up[v];
    pre_dw[v] = pre_dw[x] + f_dw[v];
    rt_total[v] = rt_total[x];
    rt_total[v].delta(rk_up[v], -1);
    rt_total[v].delta(rk_dw[v], 1);
    dfs(v);
  }
}

void precalc_f() {
  President::nn = 0;
  President::ban_hash = true;
  for (int i = 2; i <= n; i ++)
    rt_total[1].delta(rk_up[i], 1);
  for (int i = 2; i <= n; i ++)
    f_up[i] = 2 + rt_total[1].query(rk_up[i]),
    f_dw[i] = 2 + rt_total[1].query(rk_dw[i]);
  dfs(1);
}
}

// 第三部分：对树结构分块，维护两个路径“笛卡尔积的偏序”
const int B = 400, NB = (100000 + B - 1) / B + 1;
namespace Step3 {

int nb, bs[NB + 10], bid[100010];
vector<int> sons2[NB + 10];
vector<int> stk;

int dfs(int x) {
  int tot = 1;
  for (auto v : sons[x])
    tot += dfs(v);

  if (tot >= B || x == 1) {
    bid[x] = ++ nb;
    bs[nb] = x;
    while (!stk.empty() && inside(x, stk.back()))
      sons2[nb].push_back(bid[stk.back()]), stk.pop_back();
    stk.push_back(x);
    return 0;
  }
  return tot;
}

// 计算 sum_(i in P) sum_(j in Q) A[i] < B[i]
int pre_up[NB + 10][200010];
int pre_dw[NB + 10][200010];
int val_up[100010][B + 10];
int val_dw[100010][B + 10];
int LEN[100010];

void dfs2(int x, int f) {
  if (bid[x] == 0)
    bid[x] = f;
  else {
    if (f != 0) {
      int id = bid[x];
      memcpy(pre_up[id], pre_up[f], sizeof pre_up[0]);
      memcpy(pre_dw[id], pre_dw[f], sizeof pre_dw[0]);
      for (int y = x; y != bs[f]; y = fa[y])
        ++ pre_up[id][rk_up[y]], ++ pre_dw[id][rk_dw[y]];
    }
    f = bid[x];
  }
  for (auto v : sons[x]) {
    if (bid[v] == 0) {
      LEN[v] = LEN[x] + 1;
      memcpy(val_up[v] + 1, val_up[x], LEN[x] * sizeof(int));
      memcpy(val_dw[v], val_dw[x], LEN[x] * sizeof(int));
      val_up[v][0] = rk_up[v];
      val_dw[v][LEN[x]] = rk_dw[v];
    }
    dfs2(v, f);
  }
}

struct BlockAbstract {
  int *A, *B;
  int (*fA)[200010], (*fB)[200010];
  int (*vA)[::B + 10], (*vB)[::B + 10];
  i64 fAB[NB + 1][NB + 1];

  void dfs(int x) {
    for (auto v : sons2[x]) {
      for (int i = 1; i <= nb; i ++)
        fAB[i][v] = fAB[i][x];
      for (int y = bs[v]; y != bs[x]; y = fa[y])
        for (int i = 1; i <= nb; i ++)
          fAB[i][v] += fA[i][B[y] - 1];
      dfs(v);
    }
  }

  void init() {
    dfs(bid[1]);
  }

  inline i64 query(int u, int v) {
    int idu = bid[u], idv = bid[v];
    i64 res = fAB[idu][idv];
    for (int p = 0, q = 0; q < LEN[v]; q ++) {
      int num = vB[v][q];
      while (p < LEN[u] && vA[u][p] < num)
        ++ p;
      res += p + fA[idu][num - 1];
    }
    for (int p = 0; p < LEN[u]; p ++)
      res += fB[idv][MAX_RK] - fB[idv][vA[u][p]];
    return res;
  }
} up_up, up_dw, dw_up;

void init() {
  dfs(1);
  dfs2(1, 0);
  for (int i = 1; i <= nb; i ++)
    for (int j = 1; j <= MAX_RK; j ++)
      pre_up[i][j] += pre_up[i][j - 1],
      pre_dw[i][j] += pre_dw[i][j - 1];

  up_up.A   = rk_up; up_up.B   = rk_up;
  up_up.fA = pre_up; up_up.fB = pre_up;
  up_up.vA = val_up; up_up.vB = val_up;

  up_dw.A   = rk_up; up_dw.B   = rk_dw;
  up_dw.fA = pre_up; up_dw.fB = pre_dw;
  up_dw.vA = val_up; up_dw.vB = val_dw;

  dw_up.A =   rk_dw; dw_up.B   = rk_up;
  dw_up.fA = pre_dw; dw_up.fB = pre_up;
  dw_up.vA = val_dw; dw_up.vB = val_up;
  up_up.init(); up_dw.init(); dw_up.init();
}
}

using Step3::up_up;
using Step3::up_dw;
using Step3::dw_up;

// 第四步：ox = oy = 0 的询问
inline int query_00(int s, int t) {
  if (s == t) return 1;
  int base = (inside(t, s) ? rk_dw[climb(s, dep[t] + 1)] : rk_up[t]);
  return 2 + rt_total[s].query(base);
}

// 第五步：ox = oy = 1 的询问
i64 query_11(int s, int t, int r) {
  int l = lca(s, t);
  int dist = dep[s] + dep[t] - 2 * dep[l];

  int du = [&] () {
    int L = 0, R = dist + 1;
    while (L < R - 1) {
      int M = (L + R) >> 1;
      if (query_00(s, toward(s, l, t, M)) <= r)
        L = M;
      else
        R = M;
    }
    return R;
  }();

  int dv = [&] () {
    int L = du - 1, R = dist + 1;
    while (L < R - 1) {
      int M = (L + R) >> 1;
      if (query_00(toward(s, l, t, M - 1), toward(s, l, t, M)) <= r)
        L = M;
      else
        R = M;
    }
    return L;
  }();

  // s ... u | <-  . <- ... <-  v | <- ...
  // 0 ...   |    du    ...    dv |
  //     pt1                  pt2
  // len(pt1) = du - 1
  // len(pt2) = dv - du + 1

  i64 res = 1ll * (du - 1) * du / 2;
  if (du > dv)
    return res;
  res += 1ll * (dv - du + 1) * (dv + du) / 2;
  res += 1ll * r * (dv - du + 1);

  // sum_(p in path(v --> u)) f(s, p)
  int u = toward(s, l, t, du - 1);
  int v = toward(s, l, t, dv);
  int luv = lca(u, v);
  i64 tot = pre_up[v] - pre_up[luv] + pre_dw[u] - pre_dw[luv];

  if (inside(luv, s)) {
    // up[luv -> v] < up[1 -> s]
    tot -= up_up.query(v, s) - up_up.query(luv, s);
    // up[luv -> v] < dw[1 -> s]
    tot += up_dw.query(v, s) - up_dw.query(luv, s);
    // dw[luv -> u] < up[1 -> s]
    tot -= dw_up.query(u, s) - dw_up.query(luv, s);
    // dw[luv -> u] < dw[1 -> s]
    // s --- u --- luv --- 1
    int p = dep[s] - dep[u], q = dep[u] - dep[luv];
    tot += 1ll * p * q + 1ll * q * (q - 1) / 2;
  } else if (inside(s, luv)) {
    // up[u -> v] < up[1 -> s]
    tot -= 1ll * (dep[s] - dep[1]) * (dv - du + 1);
    // up[u -> v] < dw[1 -> s]
    tot += up_dw.query(v, s) - up_dw.query(u, s);
  } else {
    // up[u -> v] < up[1 -> s]
    tot -= up_up.query(v, s) - up_up.query(u, s);
    // up[u -> v] < dw[1 -> s]
    tot += up_dw.query(v, s) - up_dw.query(u, s);
  }

  return res - tot;
}

int main() {
  int _;
  scanf("%d%d", &_, &n);
  MAX_RK = 2 * n;
  for (int i = 1, a, b; i < n; i ++) {
    scanf("%d%d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }

  dfs1(1, 0);
  dfs2(1, 1);
  Step1::calc_rk();
  Step2::precalc_f();
  Step3::init();

  scanf("%d", &m);
  while (m --) {
    int s, t, ox, oy, r;
    scanf("%d%d%d%d%d", &s, &t, &ox, &oy, &r);
    if (ox == 0 && oy == 0) {
      printf("%d\n", query_00(s, t) <= r);
    } else if (ox == 0 && oy == 1) {
      int l = lca(s, t);
      int dist = dep[s] + dep[t] - 2 * dep[l];
      int L = 0, R = dist + 1;
      while (L < R - 1) {
        int M = (L + R) >> 1;
        if (query_00(s, toward(s, l, t, M)) <= r)
          L = M;
        else
          R = M;
      }
      printf("%d\n", R);
    } else if (ox == 1 && oy == 0) {
      int l = lca(s, t);
      int dist = dep[s] + dep[t] - 2 * dep[l];
      int L = 0, R = dist + 1;
      while (L < R - 1) {
        int M = (L + R) >> 1;
        if (query_00(toward(t, l, s, M), t) <= r)
          L = M;
        else
          R = M;
      }
      printf("%d\n", R);
    } else {
      int l = lca(s, t);
      int dist = dep[s] + dep[t] - 2 * dep[l];
      printf("%lld\n", query_11(s, t, r) + query_11(t, s, r) + dist + 1);
    }
  }
}

::::

::::info[代码（树上莫队 + 二次离线）]

// https://qoj.ac/submission/2117995

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <queue>
#include <cassert>

using namespace std;

using i64 = long long;
using u64 = unsigned long long;

int MAX_RK;
// 第零部分：树上的基础操作
int n;
int m;
vector<int> g[100010], sons[100010];
int dep[100010], sz[100010];

int dfn[100010], ord[100010], hv[100010], idx;
int tp[100010];

int fa[100010];
int euler_in[100010], euler_out[100010];
int euler[200010], euler_idx;
bool euler_is_in[200010];

void dfs1(int x, int f) {
  sz[x] = 1;
  fa[x] = f;
  dep[x] = dep[f] + 1;
  euler[euler_in[x] = ++euler_idx] = x;
  euler_is_in[euler_idx] = true;
  for (auto v : g[x]) if (v != f) {
    dfs1(v, x);
    sz[x] += sz[v];
    if (hv[x] == 0 || sz[v] > sz[hv[x]])
      hv[x] = v;
    sons[x].push_back(v);
  }
  euler[euler_out[x] = ++euler_idx] = x;
}

void dfs2(int x, int t) {
  dfn[x] = ++ idx;
  ord[idx] = x;
  tp[x] = t;
  if (hv[x]) dfs2(hv[x], t);
  for (auto v : sons[x])
    if (v != hv[x]) dfs2(v, v);
}

inline bool inside(int x, int v) {
  return dfn[v] >= dfn[x] && dfn[v] < dfn[x] + sz[x];
}

inline int climb(int x, int d) {
  while (dep[tp[x]] > d) x = fa[tp[x]];
  return ord[dfn[x] - dep[x] + d];
}

inline int lca(int x, int y) {
  while (tp[x] != tp[y]) {
    if (dep[tp[x]] > dep[tp[y]])
      x = fa[tp[x]];
    else
      y = fa[tp[y]];
  }
  return dep[x] > dep[y] ? y : x;
}

inline int toward(int from, int lca, int to, int dist) {
  int a = dep[from] - dist;
  if (a >= dep[lca]) return climb(from, a);
  return climb(to, 2 * dep[lca] - a);
}

inline int direction(int f, int t) {
  if (f == t)
    return 0;
  if (inside(f, t))
    return climb(t, dep[f] + 1);
  return f;
}

// 主席树
namespace President {
bool ban_hash = false;
struct Node {
  int ls, rs;
  int sz;
  u64 hsh;
} tr[400010 * 18];
int nn;

void pu(int x) {
  tr[x].sz = tr[tr[x].ls].sz + tr[tr[x].rs].sz;
  if (!ban_hash)
    tr[x].hsh = (
        (tr[tr[x].ls].hsh * 0xbf58476d1ce4e5b9ULL)
      ^ (tr[tr[x].rs].hsh * 0x94d049bb133111ebULL)
      ^ tr[x].sz
    );
}

void ins(int &rt, int l, int r, int k, int v) {
  int old = rt;
  rt = ++ nn;
  tr[rt] = tr[old];
  if (l == r) {
    tr[rt].sz += v;
    tr[rt].hsh = tr[rt].sz;
    return;
  }
  int m = (l + r) >> 1;
  if (k <= m)
    ins(tr[rt].ls, l, m, k, v);
  else
    ins(tr[rt].rs, m + 1, r, k, v);
  pu(rt);
}

bool cmp_iter(int r1, int r2) {
  int l = 1, r = MAX_RK;
  while (true) {
    if (r1 == 0) return true;
    if (r2 == 0) return false;
    if (l == r) return tr[r1].sz < tr[r2].sz;
    int m = (l + r) >> 1;
    int rr1 = tr[r1].rs, rr2 = tr[r2].rs;
    if (tr[rr1].hsh != tr[rr2].hsh) {
      r1 = rr1; r2 = rr2; l = m + 1;
    } else {
      r1 = tr[r1].ls; r2 = tr[r2].ls; r = m;
    }
  }
}

int cmp(int r1, int r2) {
  if (tr[r1].hsh == tr[r2].hsh)
    return 0;
  return cmp_iter(r1, r2) ? -1 : 1;
}

int que(int rt, int l, int r, int ll) {
  if (ll <= l) return tr[rt].sz;
  int m = (l + r) >> 1;
  return (ll <= m) ?
         que(tr[rt].ls, l, m, ll) + tr[tr[rt].rs].sz :
         que(tr[rt].rs, m + 1, r, ll);
}

struct Root {
  int rt;
  Root() { rt = 0; }
  Root(int rt): rt(rt) {}
  void delta(int k, int v) {
    ins(rt, 1, MAX_RK, k, v);
  }
  int query(int l) {
    if (l == MAX_RK) return 0;
    return que(rt, 1, MAX_RK, l + 1);
  }
  bool operator < (const Root &rw) const {
    return cmp(rt, rw.rt) == 1;
  }
  bool operator == (const Root &rw) const {
    return tr[rt].hsh == tr[rw.rt].hsh;
  }
};
}
using President::Root;

// 第一部分：计算排名
int rk_up[100010], rk_dw[100010];
namespace Step1 {
/* 
  stg[x] = 1 代表周围只有一个子树未知，
    进入第一阶段，向未知方向 exclude[x] 提供结果
  stg[x] = 2 代表周围所有方向已知
    进入第二阶段，向除 exclude[x] 之外的方向提供结果
*/
int stg[100010], exclude[100010];
int ready[100010];

priority_queue<pair<Root, int>> pq;
Root rt_near[100010];

void do_stage(int x) {
  if (sons[x].empty()) return;
  if (stg[x] == 0) {
    ++ stg[x];
    if (x != 1 && rk_dw[x] == 0) {
      exclude[x] = x;
      pq.push({rt_near[x], x});
    } else {
      for (auto v : sons[x]) if (rk_up[v] == 0) {
        exclude[x] = -v;
        pq.push({rt_near[x], -v});
        break;
      }
    }
  } else {
    ++ stg[x];
    if (x != 1 && exclude[x] != x) {
      Root tmp = rt_near[x];
      tmp.delta(rk_dw[x], -1);
      pq.push({tmp, x});
    }
    for (auto v : sons[x]) if (exclude[x] != -v) {
      Root tmp = rt_near[x];
      tmp.delta(rk_up[v], -1);
      pq.push({tmp, -v});
    }
  }
}

void calc_rk() {
  for (int i = 1; i <= n; i ++)
    if ((ready[i] = sons[i].size()) == 0)
      pq.push({Root(), i});

  if (-- ready[1] == 0)
    do_stage(1);

  Root last;
  int id = 1;
  while (!pq.empty()) {
    auto [rt, x] = pq.top();
    pq.pop();
    if (!(last == rt))
      ++ id, last = rt;
    if (x > 0) {
      rk_up[x] = id;
      rt_near[fa[x]].delta(id, 1);
      if (-- ready[fa[x]] <= 0)
        do_stage(fa[x]);
    } else {
      x = -x;
      rk_dw[x] = id;
      rt_near[x].delta(id, 1);
      if (-- ready[x] <= 0)
        do_stage(x);
    }
  }

  MAX_RK = id;
}
}

// 第二部分：计算以 1 或相邻点为根时的 f 函数值
int f_up[100010], f_dw[100010];
i64 pre_up[100010], pre_dw[100010];
Root rt_total[100010];

namespace Step2 {
void dfs(int x) {
  for (auto v : sons[x]) {
    pre_up[v] = pre_up[x] + f_up[v];
    pre_dw[v] = pre_dw[x] + f_dw[v];
    rt_total[v] = rt_total[x];
    rt_total[v].delta(rk_up[v], -1);
    rt_total[v].delta(rk_dw[v], 1);
    dfs(v);
  }
}

void precalc_f() {
  President::nn = 0;
  President::ban_hash = true;
  for (int i = 2; i <= n; i ++)
    rt_total[1].delta(rk_up[i], 1);
  for (int i = 2; i <= n; i ++)
    f_up[i] = 2 + rt_total[1].query(rk_up[i]),
    f_dw[i] = 2 + rt_total[1].query(rk_dw[i]);
  dfs(1);
}
}

// ox = oy = 0 的询问
inline int query_00(int s, int t) {
  if (s == t) return 1;
  int base = (inside(t, s) ? rk_dw[climb(s, dep[t] + 1)] : rk_up[t]);
  return 2 + rt_total[s].query(base);
}

// 第三部分：ox = oy = 1 的询问
int QUERY_11_ID;
i64 query_11_ans[100010];

namespace Step3 {

// 均摊的单点修改前缀查询
int st[510], ed[510], bid[200010], bcnt = 0;
struct Block_Query {
  int b1[510], b2[200010];
  void delta(int k, int v) {
    int id = bid[k];
    for (int i = id; i <= bcnt; i ++)
      b1[i] += v;
    for (int i = k; i <= ed[id]; i ++)
      b2[i] += v;
  }
  int query(int k) {
    if (k == 0) return 0;
    int id = bid[k];
    return b1[id - 1] + b2[k];
  }
} blk_up, blk_dw;

const int Q_BCNT = 400;
struct Query_Ty {
  int *A, *B;
  vector<tuple<int, int, int, int>> askA[200010], askB[200010];
  struct Query {
    int l, r, delta, id;
    bool operator < (const Query &q) const {
      int ba = l / Q_BCNT, bb = q.l / Q_BCNT;
      if (ba != bb) return ba < bb;
      return (ba & 1) ? r > q.r : r < q.r;
    }
  };
  vector<Query> qs;
  inline void query(int u, int v, int delta) {
    if (u != 1 && v != 1)
      qs.push_back({euler_in[u], euler_in[v], delta, QUERY_11_ID});
  }

  vector<i64> temp;
  bool meet_a[100010], meet_b[100010];
  int cnt_b = 0, pl = 1, pr = 1;
  i64 collect = 0;

  inline void modify_a(int x, int idx) {
    if (meet_a[x])  collect -= cnt_b;
    else            collect += cnt_b;
    meet_a[x] ^= 1;
  }
  inline void modify_b(int x, int idx) {
    if (meet_b[x])  -- cnt_b;
    else            ++ cnt_b;
    meet_b[x] ^= 1;
  }

  void prework() {
    int sz = qs.size();
    sort(qs.begin(), qs.end());
    temp.resize(sz);
    for (int i = 0; i < sz; i ++) {
      auto ele = qs[i];
      collect = 0;

      if (pl < ele.l)
        askB[pr].push_back({pl + 1, ele.l, -1, i});
      while (pl < ele.l)
        modify_a(euler[++ pl], i);

      if (pr < ele.r)
        askA[pl].push_back({pr + 1, ele.r, 1, i});
      while (pr < ele.r)
        modify_b(euler[++ pr], i);

      if (pl > ele.l)
        askB[pr].push_back({ele.l + 1, pl, 1, i});
      while (pl > ele.l)
        modify_a(euler[pl --], i);

      if (pr > ele.r)
        askA[pl].push_back({ele.r + 1, pr, -1, i});
      while (pr > ele.r)
        modify_b(euler[pr --], i);

      temp[i] = collect;
    }
  }

  void postwork() {
    int sz = qs.size();
    for (int i = 1; i < sz; i ++)
      temp[i] += temp[i - 1];
    for (int i = 0; i < sz; i ++)
      query_11_ans[qs[i].id] += qs[i].delta * temp[i];
  }
} up_up, up_dw, dw_up;

void init() {
  up_up.A = rk_up; up_up.B = rk_up;
  up_dw.A = rk_up; up_dw.B = rk_dw;
  dw_up.A = rk_dw; dw_up.B = rk_up;

  int blen = sqrt(2 * n);
  bcnt = (MAX_RK + blen - 1) / blen;
  for (int i = 1; i <= bcnt; i ++) {
    st[i] = blen * (i - 1) + 1;
    ed[i] = min(MAX_RK, blen * i);
    for (int j = st[i]; j <= ed[i]; j ++)
      bid[j] = i;
  }
}

void work_offline() {
  up_up.prework();
  up_dw.prework();
  dw_up.prework();

  for (int i = 2; i <= 2 * n - 1; i ++) {
    if (euler_is_in[i]) {
      blk_up.delta(rk_up[euler[i]], 1);
      blk_dw.delta(rk_dw[euler[i]], 1);
    } else {
      blk_up.delta(rk_up[euler[i]], -1);
      blk_dw.delta(rk_dw[euler[i]], -1);
    }

    for (auto &[l, r, contri, id] : up_up.askA[i])
      for (int pos = l; pos <= r; pos ++)
        up_up.temp[id] += (euler_is_in[pos] ? contri : -contri) * blk_up.query(rk_up[euler[pos]] - 1);
    for (auto &[l, r, contri, id] : up_up.askB[i])
      for (int pos = l; pos <= r; pos ++)
        up_up.temp[id] += (euler_is_in[pos] ? contri : -contri) * blk_up.query(rk_up[euler[pos]]);

    for (auto &[l, r, contri, id] : up_dw.askA[i])
      for (int pos = l; pos <= r; pos ++)
        up_dw.temp[id] += (euler_is_in[pos] ? contri : -contri) * blk_up.query(rk_dw[euler[pos]] - 1);
    for (auto &[l, r, contri, id] : up_dw.askB[i])
      for (int pos = l; pos <= r; pos ++)
        up_dw.temp[id] += (euler_is_in[pos] ? contri : -contri) * blk_dw.query(rk_up[euler[pos]]);

    for (auto &[l, r, contri, id] : dw_up.askA[i])
      for (int pos = l; pos <= r; pos ++)
        dw_up.temp[id] += (euler_is_in[pos] ? contri : -contri) * blk_dw.query(rk_up[euler[pos]] - 1);
    for (auto &[l, r, contri, id] : dw_up.askB[i])
      for (int pos = l; pos <= r; pos ++)
        dw_up.temp[id] += (euler_is_in[pos] ? contri : -contri) * blk_up.query(rk_dw[euler[pos]]);
  }

  up_up.postwork();
  up_dw.postwork();
  dw_up.postwork();
}

void query_11(int s, int t, int r) {
  int l = lca(s, t);
  int dist = dep[s] + dep[t] - 2 * dep[l];

  int du = [&] () {
    int L = 0, R = dist + 1;
    while (L < R - 1) {
      int M = (L + R) >> 1;
      if (query_00(s, toward(s, l, t, M)) <= r)
        L = M;
      else
        R = M;
    }
    return R;
  }();

  int dv = [&] () {
    int L = du - 1, R = dist + 1;
    while (L < R - 1) {
      int M = (L + R) >> 1;
      if (query_00(toward(s, l, t, M - 1), toward(s, l, t, M)) <= r)
        L = M;
      else
        R = M;
    }
    return L;
  }();

  i64 res = 1ll * (du - 1) * du / 2;
  if (du <= dv) {
    res += 1ll * (dv - du + 1) * (dv + du) / 2;
    res += 1ll * r * (dv - du + 1);

    int u = toward(s, l, t, du - 1);
    int v = toward(s, l, t, dv);
    int luv = lca(u, v);
    res -= pre_up[v] - pre_up[luv] + pre_dw[u] - pre_dw[luv];

    if (inside(luv, s)) {
      up_up.query(v, s, 1);
      up_up.query(luv, s, -1);
      up_dw.query(v, s, -1);
      up_dw.query(luv, s, 1);
      dw_up.query(u, s, 1);
      dw_up.query(luv, s, -1);
      int p = dep[s] - dep[u], q = dep[u] - dep[luv];
      res -= 1ll * p * q + 1ll * q * (q - 1) / 2;
    } else if (inside(s, luv)) {
      res += 1ll * (dep[s] - dep[1]) * (dv - du + 1);
      up_dw.query(v, s, -1);
      up_dw.query(u, s, 1);
    } else {
      up_up.query(v, s, 1);
      up_up.query(u, s, -1);
      up_dw.query(v, s, -1);
      up_dw.query(u, s, 1);
    }
  }
  query_11_ans[QUERY_11_ID] += res;
}

}

using Step3::query_11;

int main() {
  int _;
  scanf("%d%d", &_, &n);
  MAX_RK = 2 * n;
  for (int i = 1, a, b; i < n; i ++) {
    scanf("%d%d", &a, &b);
    g[a].push_back(b);
    g[b].push_back(a);
  }

  dfs1(1, 0);
  dfs2(1, 1);
  Step1::calc_rk();
  Step2::precalc_f();
  Step3::init();

  scanf("%d", &m);
  vector<i64> ans(m);
  vector<int> query_11_pos;

  for (int p = 0; p < m; p ++) {
    int s, t, ox, oy, r;
    scanf("%d%d%d%d%d", &s, &t, &ox, &oy, &r);
    if (ox == 0 && oy == 0) {
      ans[p] = query_00(s, t) <= r;
    } else if (ox == 0 && oy == 1) {
      int l = lca(s, t);
      int dist = dep[s] + dep[t] - 2 * dep[l];
      int L = 0, R = dist + 1;
      while (L < R - 1) {
        int M = (L + R) >> 1;
        if (query_00(s, toward(s, l, t, M)) <= r)
          L = M;
        else
          R = M;
      }
      ans[p] = R;
    } else if (ox == 1 && oy == 0) {
      int l = lca(s, t);
      int dist = dep[s] + dep[t] - 2 * dep[l];
      int L = 0, R = dist + 1;
      while (L < R - 1) {
        int M = (L + R) >> 1;
        if (query_00(toward(t, l, s, M), t) <= r)
          L = M;
        else
          R = M;
      }
      ans[p] = R;
    } else {
      int l = lca(s, t);
      int dist = dep[s] + dep[t] - 2 * dep[l];
      query_11_ans[QUERY_11_ID] = dist + 1;
      query_11_pos.push_back(p);
      query_11(s, t, r);
      query_11(t, s, r);
      ++ QUERY_11_ID;
    }
  }

  Step3::work_offline();
  for (int i = 0; i < QUERY_11_ID; i ++)
    ans[query_11_pos[i]] = query_11_ans[i];
  for (int i = 0; i < m; i ++)
    printf("%lld\n", ans[i]);

  return 0;
}

:::info[参考答案]

::: ::::