给出一棵包含 $n$ 个节点的树，以 $1$ 为根，边带权。

定义 $\mathrm{dep}_x$ 表示节点 $x$ 到根的简单路径上的边权和。

有 $Q$ 次查询，每次查询给出两个参数 $l, r$，对于所有满足 $l \leq i, j \leq r$ 的二元组 $(i, j)$，你需要求出有多少种不同的 $\mathrm{dep}_{\mathrm{LCA}(i, j)}$。

数据范围：$1 \leq n \leq 10^5$，$1 \leq Q \leq 5 \times 10^5$，$-10^9 \leq w \leq 10^9$，$1 \leq l \leq r \leq n$。

时空限制：$500$ms / $512$MiB。

给出一个长度为 $n$ 的字符串 $S$。定义字典为 $S$ 的所有本质不同的子串构成的集合，定义单词为字典中的字符串。

有 $Q$ 次操作，每次操作会给出两个参数 $l, r$，你将会在字典中，学习以 $S[l : r]$ 为前缀的所有单词。每次操作结束后，你需要求出有多少个单词被你学习过。

数据范围：$1 \leq n, Q \leq 2 \times 10^5$，$1 \leq l \leq r \leq n$。

数据范围：$4$s / $1024$MiB。

给出一棵包含 $n$ 个节点的树，以 $1$ 为根。

定义 $\mathrm{dep}_u$ 表示节点 $u$ 的深度，定义 $\mathrm{LCA}^{*}(l, r)$ 表示区间 $[l, r]$ 中所有节点的最近公共祖先。

有 $Q$ 次查询，每次查询给出三个整数 $l, r, k$，你需要求出

$$\max\limits_{l \leq l' \leq r' \leq r \land r' - l' + 1 \geq k} \mathrm{dep}_{\mathrm{LCA}^{*}(l', r')}$$

数据范围：$1 \leq n, Q \leq 5 \times 10^5$，$1 \leq l \leq r \leq n$，$1 \leq k \leq r - l + 1$。

时空限制：$2$s / $1024$MiB。

给出一个长度为 $n$ 仅包含小写字符的字符串 $s$。

定义后缀 $i$ 的权值为 $w_i$，定义两个不同后缀 $i, j(i \neq j)$ 的贡献为 $\mathrm{LCP}(i, j) + (w_i \operatorname{xor} w_j)$。其中 $\mathrm{LCP}(i, j)$ 表示后缀 $i$ 和后缀 $j$ 的最长公共前缀长度。

你需要求出任意两个不同后缀 $i, j(i \neq j)$ 的贡献最大值。

数据范围：$1 \leq n \leq 10^5$，$0 \leq w_i < n$。

时空限制：$1$s / $512$MiB。