给出一棵包含 $n$ 个点的树，编号 $1 \sim n$。第 $i$ 个点的高度为 $h_i$。

你可以在任意点放置任意数量的塔，对于每个塔，你可以选择放在哪个点，并且可以选择它的效率。设置一个效率为 $e$ 的塔需要花费 $e$ 金币，其中 $e > 0$。

如果存在一对分别位于 $u, v$ ($u \neq v$) 的信号塔，它们的效率分别为 $e_u, e_v$，且满足 $\min(e_u, e_v) \geq h_x$，且点 $x$ 位于从 $u$ 到 $v$ 的路径上，则我们认为 $x$ 能够收到信号。

请你求出使得所有顶点都接收到信号，所需的最小金币数。

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

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

给出一个长度为 $n$ 的序列 $a$，仅由 $0$ 或 $1$ 构成。

你需要对序列进行至多 $n$ 次操作（或者说明这是不可能的），每次操作你可以选择一个下标 $i$ ($1 \leq i \leq n - 2$)，然后将 $a_i, a_{i + 1}, a_{i + 2}$ 均改成 $a_i \oplus a_{i + 1} \oplus a_{i + 2}$。

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

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

有 $p$ 个人玩一个游戏，第 $i$ 个人的得分为 $a_i$。

已知 $\sum a_i = s$ 且 $a_1 \geq r$，得分最高的人可以获胜，若多个人得分最高，则等概率随机其中一个人获胜。

求第一个人获胜的概率，答案对 $998244353$ 取模。

数据范围：$1 \leq p \leq 100$，$0 \leq r \leq s \leq 5000$。

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

给出一棵包含 $n$ 个点的树。

有 $Q$ 次询问，每次询问给出三个整数 $k, m, r$，随后给出 $k$ 个树上的节点 $a_1, a_2, \dots, a_k$。假设树的根为 $r$，我们需要将这 $k$ 个节点划分成至多 $m$ 组，并且：

• 每个节点必须恰好属于一个组，每个组至少包含一个节点。
• 在任意组内，不能存在两个不同的节点，使得其中一个点是另一个点的祖先。

你需要求出分组的方案数，答案对 $10^9 + 7$ 取模。

数据范围：$1 \leq n, Q \leq 10^5$，$1 \leq k, r \leq n$，$1 \leq m \leq \min(300, k)$，$1 \leq \sum k \leq 10^5$。

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

维护 $n$ 个初始为空的可重集。有 $Q$ 次操作，每次操作形如以下四种之一：

• 1 x v：令集合 $x$ 等于 $\{v\}$。
• 2 x y z：令集合 $x$ 等于集合 $y$ 与 $z$ 的并。
• 3 x y z：令集合 $x$ 等于集合 $y$ 与 $z$ 的积，$A \times B = \{\gcd(a, b) \mid a \in A, b \in B\}$。
• 4 x v：询问 $v$ 在集合 $x$ 中出现次数模 $2$ 的结果。

数据范围：$1 \leq n \leq 10^5$，$1 \leq q \leq 10^6$，$1 \leq v \leq 7000$。

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

给出一个长度为 $n$ 的数组 $a$，记 $s_i = \sum_{j = 1}^i a_j$。

有 $Q$ 次操作，每次操作给出两个整数 $p, x$，表示将 $a_p$ 赋成 $x$。每次操作后，你都需要判断是否存在一个位置 $i$ 满足 $a_i = s_{i - 1}$。若存在，输出任意一个满足条件的 $i$。

数据范围：$1 \leq n, Q \leq 2\times 10^5$，$0 \leq a_i \leq 10^9$，$1 \leq p \leq n$，$0 \leq x \leq 10^9$。

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

对于一个长度为 $n$ 的排列 $p$，定义 $f(p)$ 表示：令 $g_i$ 表示 $p_1, \dots, p_i$ 的最大公约数，则 $f(p)$ 表示 $g_1, g_2, \dots, g_n$ 中不同元素的个数。

令 $f_{\max}(n)$ 表示所有关于 $n$ 的排列 $p$ 中的 $f(p)$ 最大值，求有多少个关于 $n$ 的排列 $p$ 满足 $f(p) = f_{\max}(n)$。答案对 $10^9 + 7$ 取模。

数据范围：$2 \leq n \leq 10^6$。

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

给出一棵包含 $n$ 个点的树，编号 $1 \sim n$。根节点为 $1$。

有 $Q$ 次操作，每次操作形如以下的三种之一：

• 1 u：设本次操作之前共有 $n'$ 个点，则新加入一个编号为 $n' + 1$ 的点，并且新点有一条连向 $u$ 的无向边。
• 2 u v c k：对于在从 $u$ 到 $v$ 的简单路径上的所有点，都会增加 $k$ 个类型 $c$ 的物品。
• 3 u c：查询点 $u$ 的子树内，有多少个物品的类型 $\leq c$。

本题强制在线。

数据范围：$1 \leq n \leq 3 \times 10^4$，$0 \leq Q \leq 10^5$，节点总数不超过 $5 \times 10^4$，$1 \leq k \leq 10^7$，$1 \leq c \leq 10^9$。

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

给出一棵包含 $n$ 个点的树，初始时所有点均为白色。

有 $Q$ 次操作，每次操作形如一下的两种：

• 1 x：将点 $x$ 改成黑色。
• 2 x：对于点 $x$，找出编号最小的点 $y$，使得 $y$ 位于 $x$ 到某个黑色顶点的简单路径上。

本题强制在线。保证第一次操作的类型为操作 1。

数据范围：$3 \leq n, Q \leq 10^6$。

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

有 $n$ 个元素，第 $i$ 个元素有五个参数 $x_i, a_i, b_i, c_i, d_i$。

你需要求出一个 $1 \sim n$ 的排列 $p$，满足 $p_1 = s, p_n = e$，同时最小化这个排列的权值。一个排列的权值定义为 $\sum_{i = 1}^{n - 1} f(p_i, p_{i + 1})$，其中

• 若 $i > j$，则 $f(i, j) = x_i - x_j + c_i + b_j$。
• 若 $i < j$，则 $f(i, j) = x_j - x_i + d_i + a_j$。

你只需要求出排列的最小权值即可。

数据范围：$1 \leq n \leq 5 \times 10^3$，$s \neq e$，$1 \leq x_1 < x_2 < \dots < x_n \leq 10^9$，$1 \leq a_i, b_i, c_i, d_i \leq 10^9$。

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