给出一棵包含 $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。

给出一个包含 $n$ 个字符串的集合 $D$ 以及一个字符串 $s$，你需要找出集合 $D$ 中字典序小于 $s$ 的字符串数量。

字符串 $s$ 会经过 $Q$ 次修改，每次修改会给出一个整数 $k$ 以及一个字符 $c$，表示将字符串 $s$ 从第 $k$ 个字符开始到字符串末尾的所有字符替换成 $c$。每次修改完字符串 $s$ 之后，你都需要求出集合 $D$ 中字典序小于 $s$ 的字符串数量。

数据范围：$1 \leq n, Q \leq 10^6$，$1 \leq |s| \leq 10^6$，字符串集合 $D$ 的总长不超过 $10^6$。

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

给出一棵大小为 $n$ 的树。

对于每个 $k$ ($0 \leq k \leq n - 1$)，你需要求出有多少个大小为 $n$ 的带标号树与原树有恰好 $k$ 条重合的边。答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n \leq 100$。

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

给出一棵包含 $n$ 个节点的树。你需要给每个节点染上数字 $0$ 或 $1$。

路径 $(u, v)$ 的权值，等于从 $u$ 到 $v$ 的最短路径上所有节点数字的 MEX。一种染色方案的权值等于所有 $1 \leq u \leq v \leq n$ 的路径 $(u, v)$ 的权值之和。

请求出所有的染色方案中，可能的最大权值。

数据范围：$1 \leq n \leq 2 \times 10^5$。

时空限制：$3$s / $256$MiB。

给出一张包含 $n$ 个点 $m$ 条边的无向图，每个点有一个颜色 $c_i$ ($1 \leq c_i \leq k$)，求有多少组颜色对 $a, b$ ($a < b$) 满足保留颜色为 $a$ 或 $b$ 的节点的导出子图是二分图。

数据范围：$1 \leq n \leq 5 \times 10^5$，$0 \leq m \leq 5 \times 10^5$，$2 \leq k \leq 5 \times 10^5$。

时空限制：$3$s / $500$MiB。

给出一个长度为 $n$ 的数组 $a$，你需要找出字典序最大的子序列 $s$，使得 $s$ 可以作为多边形的边长。

当且仅当 $|s| \geq 3$ 且满足以下条件时，$s$ 可以作为多边形的边长

$$2 \cdot \max(s_1, \dots, s_{|s|}) < s_1 + \dots + s_{|s|}$$

数据范围：$3 \leq n \leq 2 \times 10^5$，$1 \leq a_i \leq 10^9$。

时空限制：$3$s / $250$MiB。