约定记号如下：
- $\operatorname{chn}(x, y)$ 为 $x$ 到 $y$ 的链；
- $\operatorname{chl}(x, y)$ 为以 $x$ 为根时，节点 $y$ 的孩子集合；
- $\operatorname{sub}(x, y)$ 为以 $x$ 为根时，以 $y$ 为根的子树包含的节点集合；
- $\operatorname{dis}(x, y) = |\operatorname{chn}(x, y)|$；
- $S(x, y) = \{ S(x, z) \vert z \in \operatorname{sub}(x, y) \setminus \{y\} \}$；
则有 $f(x, y) = |\{ z : S(x, z) > S(x, y) \}| + 1$。
特殊性质 A
在此特殊构造下，本质不同的 $S(x, y)$ 仅有 $\mathcal{O}(1)$ 种，直接根据特征进行分类讨论即可。
$r = 1$
可以得出 $f(x, y) = 1 \Leftrightarrow x = y$。问题此时转化为求解树上两点距离。
接下来首先讨论 $o_x = o_y = 0$ 的情况。
$n, m \le 10$
直接模拟题意即可。
$n, m \le 2000$
观察 1：对于两个集合 $A, B$，$A \subseteq B \Rightarrow A \le B$。
观察 2：对于三个集合 $A, B, C$，$A < B \Leftrightarrow A \cup C < B \cup C$。
故可修改 $S(x, y)$ 的定义如下，而不影响答案性质：$$S(x, y) = \{ S(x, z) \vert z \in \operatorname{chl}(x, y) \}.$$
因此，本质不同的 $S(x, y)$ 只有 $\mathcal{O}(n)$ 种，可以按定义记忆化地排序所有 $S(\cdot, \cdot)$，再进行换根求解。
特殊性质 B
定义集合的高度如下：$$h(S) = \max(\{0\} \cup \{ h(s) + 1 \vert s \in S \}).$$
观察 3：对于两个基本集合 $A, B$，$h(A) < h(B) \Rightarrow A < B$。
在排序时据此加入剪枝优化，可以通过 $o_x = o_y = 0$ 且树随机生成的部分分。
$r = 2$
根据 观察 3，当 $x$ 为非直径中点的情形较为直接。计算直径中点的情形时，由于数据生成随机，退化使用暴力比对方式亦可满足限制。此子任务主要提示了树的直径中点在问题中的特殊性质。
$o_x = o_y = 0$
考虑固定 $x$，求出所有 $f(x, \cdot)$。利用堆或平衡树，可以自下而上递推出所有 $f(x, \cdot)$。时间复杂度 $\mathcal{O}(n \log n)$。
在上述递推算法中，固定根 $x$ 的作用相对有限。若不固定 $x$，同样能运行该算法，且可以得到一个自然的根 $R$。由 观察 3 可推知，$R$ 应为树 $T$ 的直径中点之一。
考虑将根从 $R$ 变为某个 $x$，则有：
- 对于 $y \in \operatorname{chn}(R, x)$，对应 $h(S(x, y))$ 的值是最大的；
- 对于 $y \notin \operatorname{chn}(R, x)$，有 $S(x, y) = S(R, y)$。
记 $\operatorname{dep}(x) = \operatorname{dis}(R, x)$，进而可得： $$f(x, y) = \begin{cases} \operatorname{dep}(x) - \operatorname{dep}(y) + 1, & x \in \operatorname{sub}(R, y), \\ \left\lvert\operatorname{chn}(R, x) \cup \{ z : S(R, z) > S(R, y) \}\right\rvert + 1, & x \notin \operatorname{sub}(R, y). \end{cases}$$
据此利用倍增算法，即可做到单次询问在线 $\mathcal{O}(\log n)$。
现在考虑 $o_x, o_y$ 不全为 $0$ 的情况。
$o_y = 0$
可将询问拆分成 4 次形如 $X = \operatorname{chn}(R, x_0)$ 的询问。转化后进行处理较为直接。
$o_x = 0$
类似地将询问拆分成 4 次形如 $Y = \operatorname{chn}(R, y_0)$ 的询问。
将 $\operatorname{chn}(R, y_0)$ 按 $\operatorname{LCA}(s, y_0)$ 分为两段：
- 从根到 $\operatorname{LCA}$ 的处理较为直接；
- 对于 $\operatorname{LCA}$ 以下的部分，由于 $f(x, y)$ 具有单调性，应用倍增即可做到 $\mathcal{O}(\log^2 n)$。
特殊性质 B
将 $\operatorname{chn}(s, t)$ 按 $\operatorname{LCA}(s, t)$ 分为两侧。若 $x, y$ 位于同侧，二者必定具有祖先后代关系，通过讨论何者在树的上方即可进行处理。
下面讨论 $x, y$ 位于异侧的情形。记 $a = \operatorname{LCA}(s, t)$。不失一般性，设 $x \in \operatorname{chn}(a, s) \setminus \{a\}, y \in \operatorname{chn}(a, t) \setminus \{a\}$。由于二者必无祖先后代关系，因此需要满足 $f(x, y) \ge f(R, y)$。
首先可通过倍增方式忽略不合法的 $y$。后续假定 $f(R, y) \le r$。
考虑固定某个 $y$，则合法的 $x$ 可划分刻画如下：
- $y$ 确定了一个区域 $L = \{ z : S(R, z) > S(R, y) \}$；
- 该区域内的点作为 $x$ 均合法；
- 除此之外，到该区域距离不超过 $r - f(R, y)$ 的点作为 $x$ 同样合法。
即在固定 $y$ 的前提下，合法 $x$ 的分布主要受限于以下两条限制：
- $\operatorname{dep}(x) \le \operatorname{dep}(s)$；
- $x$ 到前文所述区域的距离不超过 $r - f(R, y)$。
由于 $y$ 越靠下，$f(s, y)$ 越大，故必定存在一分界点 $p$，满足：
- 若 $y$ 在 $p$ 上方，则只需考虑限制 1；
- 若 $y$ 在 $p$ 下方，则只需考虑限制 2。
该分界点 $p$ 同样可通过倍增求得。
只需考虑限制 1 的情形较为直接。对于只需考虑限制 2 的情形，可转化为计算： $$\sum_{y \in \operatorname{chn}(y_1, y_2)} \left\lvert \{ x \in \operatorname{chn}(a, s) \setminus \{a\} : S(R, x) > S(R, y) \} \right\rvert$$
不难看出，上述问题本质上是求解两条链之间的逆序对。
在随机生成的数据中，树的直径的期望长度为 $\mathcal{O}(\sqrt{n})$，由此可以将总复杂度控制在 $\mathcal{O}((n + m) \sqrt{n})$。
一般情况
最终需要优化的即是计算两条链 $(\operatorname{chn}(x_1, x_2), \operatorname{chn}(y_1, y_2))$ 的逆序对问题。对变量 $y$ 应用扫描线，问题可抽象为：给定序列，将权值大于某一阈值的点自增后进行链求和。对权值进行分块，即可将时间复杂度优化至 $\mathcal{O}(n \sqrt{n + m})$。