给出一个大小为 $n$ 的树，定义点对 $(u, v)$ ($1 \leq u \leq v \leq n$) 的价值为：删除从 $u$ 到 $v$ 的路径上的所有边之后，最大连通块的大小。

对于每个 $i$ ($1 \leq i \leq n$)，求出价值等于 $i$ 的点对 $(u, v)$ 的数量。

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

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

给出一个包含 $n$ 个点 $m$ 条边的无向图，边带权。

对于任意路径，设其边权集合为 $S$，则该路径的长度为 $\mathrm{mex}(S)$。记 $\mathrm{dis}(u, v)$ 表示所有从 $u$ 到 $v$ 的路径中的最小路径长度。

现在有 $q$ 个关键点 $c_1, \dots, c_q$，连接 $c_u, c_v$ 的代价是 $\mathrm{dis}(c_u, c_v)$，求让这 $q$ 个关键点连通的最小代价总和。

数据范围：$1 \leq n, m \leq 3 \times 10^5$，$1 \leq q \leq n$，$0 \leq w \leq m$。

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

给出两棵大小均为 $n$ 的树，节点编号均为 $1 \sim n$，边带正权。

有 $Q$ 次询问，每次询问给出两个正整数 $a, b$ ($1 \leq a, b \leq n$)，你需要找到一个节点 $x$，使得 $x$ 在第一棵树上到 $a$ 的距离加上 $x$ 在第二棵树上到 $b$ 的距离之和最大，你只需要求出这个最大值即可。

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

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

给出一棵包含 $n$ 个点的有根树 $T$，根节点为 $1$。给出一个大小为 $m$ 的关键点集合 $S$。

你需要求出有多少个不同的有根树 $T'$，满足对于任意 $x, y \in S$，均有 $\mathrm{LCA}_T(x, y) = \mathrm{LCA}_{T'}(x, y)$。答案对 $998244353$ 取模。

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

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

对于一棵树 $T$，定义 $P(T)$ 表示对 $T$ 生成 Prufer 序列时，最后剩下的两个节点之中不是 $n$ 的那一个。

给出一个包含 $n$ 个点 $m$ 条边的森林。对于每一个 $v$ ($1 \leq v \leq n$)，计算有多少种加边方式，使得原图变成一棵树 $T$，且 $P(T) = v$。答案对 $998244353$ 取模。

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

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

有三种类型的礼物，价值分别为 $a, b, c$。初始时，恰好拥有每一种礼物各一份。

给出两个整数 $m$ 与 $k$。你可以进行若干次操作，每次操作形如以下的两种：

• 创造：选择一种礼物类型，并额外制作一份该类型的礼物。消耗 $x$ 点法力值，其中 $x \in \{ a, b, c \}$ 为所选礼物类型的价值。
• 复制：选择一种礼物类型，并复制该类型的所有礼物。消耗 $k$ 点法力值。

你需要求出，使得礼物价值总和是 $m$ 的倍数时，所需的最小法力值。

数据范围：$1 \leq a < b < c < m \leq 5 \times 10^5$，$1 \leq k \leq 5 \times 10^5$，$1 \leq \sum m, \sum k \leq 5 \times 10^5$。

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

圆环上有 $2n$ 个等间距的点，按顺时针顺序标记为 $1, 2, \dots, 2n$。有 $n$ 条具有不同端点的弦，其中第 $i$ 条弦连接 $a_i, b_i$。现在按照顺序依次连接这 $n$ 条弦。

每当连接完前 $\ell$ 条弦以后，考虑这 $\ell$ 条弦的任意非空子集 $S$。设 $S$ 中元素的索引分别为 $c_1, c_2, \dots, c_m$，若对于所有的 $1 \leq i < m$，都满足弦 $c_i$ 与弦 $c_{i + 1}$ 相交，则称 $S$ 为一条链。

当且仅当，每一条弦在前 $\ell$ 条弦的所有子集链中出现偶数次时，称这些弦是紧密连接的。

对于 $1$ 到 $n$ 的每一个 $\ell$，你都需要判断前 $\ell$ 条弦是否紧密连接。

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

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

This is an interactive problem.

对于 $1, \dots, n$，有一个隐藏的序列 $a_i$，其中 $a_i$ 表示数字 $i$ 的颜色。

有一个队列（初始为空），可以进行以下两种操作：

• + id：将元素 $\mathrm{id}$ 加入队列末尾。
• -：将队列开头的元素弹出。

每次操作之后，你都会得知当前队列中共有多少种不同的元素。

你的目标是，将所有元素按照颜色分组，依次给出每个组中的元素。

数据范围：$1 \leq n \leq 500$，操作至多进行 $35000$ 次。交互器不自适应。

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

给出一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$。有一个指针 $p$（初始时 $p = 1$）。

有 $Q$ 次操作，每次操作为以下三种之一：

• <：令 $p \gets p - 1$。
• >：令 $p \gets p + 1$。
• ! v：令 $a_p \gets v$，求出整个序列的严格最长上升子序列（LIS）。

数据范围：$2 \leq n \leq 2\times 10^5$，$1 \leq Q \leq 5 \times 10^5$，$1\leq a_i, v \leq 10^6$。

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

已知一个字符串 $S$ 的长度为 $n$，字符集大小为 $m$。现在均匀随机地生成该字符串 $S$。

记随机变量 $X$ 表示该字符串 $S$ 中回文子串的数量，求 $E(X^2)$。答案对给定质数 $p$ 取模。

数据范围：$1 \leq n \leq 2 \times 10^5$，$1 \leq m \leq 10^7$，$m < p < 10^9$。

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