先写个 $\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$。

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

• $A(x, y)$ 表示以 $x$ 为根时，结点 $y$ 的仅包含儿子产物的集合；
• 对于树上有向边 $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$ 个集合；
• $P(p)$ 的大小满足单调性。具体地，考虑链 $u \to v \to w$，由于 $P(v \to w)$ 包含了 $P(u \to v)$，故总有 $P(v \to w) > P(u \to v)$。单调性可以传递到满足祖先后代关系的两个有向边；
• 考虑两个结点 $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$ 的部分

考虑路径

$$\green{v_0 - v_1} - v_2 - \dots - v_k$$

并研究 $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}})$。

$$\green{v_0 \to v_1} \to \dots \to \blue{v_i \leftarrow v_{i+1}} \leftarrow \dots$$$$\green{v_0 \to v_1} \to \dots \to \red{v_i \to v_{i+1}} \leftarrow \dots$$

已知 $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+2}} (v_{i+1} \to v_{i+2}) \leq f_{v_{i+1}} (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$：

$$\dots \to y \to x_1 \to x_2 \to \dots \to x_{d-1} \to x_d = s$$

此时需要统计有多少个 $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$ 放在一起考虑。对于路径

$$t = y_0 \to y_1 \to \dots \to y_{k-1} \to y_k = s$$

根据单调性，路径中的某一个前缀满足情况 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[参考答案]

$$\begin{aligned} \{\{\{\varnothing\}\},\ \varnothing,\ \{\varnothing,\varnothing,\{\varnothing\}\}\} \quad &\textcircled{<} \quad \{\{\varnothing,\varnothing\},\ \{\varnothing,\{\varnothing,\varnothing\}\}\}\\ \{\{\varnothing,\{\{\varnothing\}\}\},\ \{\varnothing,\{\varnothing\}\}\} \quad &\textcircled{<} \quad \{\{\{\varnothing,\varnothing,\{\varnothing,\varnothing\}\},\ \varnothing\}\}\\ \{\varnothing,\varnothing,\{\varnothing,\{\{\varnothing,\{\varnothing\}\}\}\}\} \quad &\textcircled{<} \quad \{\{\varnothing,\{\varnothing,\varnothing,\{\varnothing,\{\varnothing\}\}\}\}\}\\ \{\{\varnothing,\{\varnothing\}\},\ \varnothing,\ \{\varnothing,\varnothing,\varnothing\}\} \quad &\textcircled{=} \quad \{\{\varnothing,\varnothing,\varnothing\},\ \{\{\varnothing\},\varnothing\},\ \varnothing\}\\ \{\varnothing,\{\varnothing,\{\varnothing,\varnothing\},\{\{\varnothing\}\}\}\} \quad &\textcircled{<} \quad \{\varnothing,\{\varnothing,\varnothing,\{\varnothing,\{\varnothing,\varnothing\}\}\}\}\\ \end{aligned}$$

::: ::::