$Link$

有一棵 $n$ 个节点的树，每条边都被染成黑色或白色，一开始所有的边都是白色。

有 $m$ 次操作，每次操作为以下两种操作之一：

• 给定两个点 $u,v$，对于 $u,v$ 间的路径上的所有的点 $x$（包括 $u$ 和 $v$），把所有和 $x$ 相邻的边染成白色，然后再把 $u,v$ 间的路径上所有的边染成黑色。
• 给定两个点 $u,v$，问 $u,v$ 间的路径上有几条黑色的边。

$T$ 组数据。

$T\le3,1\le n,m\le10^5$。

$Link$

你有 $m$ 个数，值域为 $[1,k]$，其中数 $i$ 有 $a_i$ 个。

你需要构造最小的 $n\times n$ 矩阵，其中包含这 $m$ 个数，剩下的位置为 $0$，并且对于任意的 $2\times2$ 子矩阵：

• 不是 $0$ 的位置数不超过 $3$。
• 对角线上的两个数不同。

$t$ 组数据，输出方案。

$1\le t\le10^4,1\le m,k\le10^5,\sum m,k\le2\times10^5$。

$Link$

你有一棵 $n$ 个点的树，每次操作你可以删除一条边，再添加一条边（删边加边合起来算一种操作）。

问最少需要多少次操作，可以让这棵树变成一条链，输出方案。

$t$ 组数据。

$1\le t\le10^4,2\le n\le10^5,\sum n\le2\times10^5$。

$Link$

本题是一道交互题。

有一个长度为 $n$ 的排列，你有两种询问：

• $\max(\min(x,p_i),\min(x+1,p_j))$。
• $\min(\max(x,p_i),\max(x+1,p_j)$。

其中 $x,i,j$ 由你决定，需要满足 $i\not=j,1\le x\le n-1$。

你可以做出最多 $\lfloor\frac{3n}{2}\rfloor+30$ 次询问，并确定这个排列每个位置上的数。

共有 $t$ 组数据。

$1\le t\le10^4,3\le n\le 10^4,\sum n\le2\times10^4$。

写在前面

啊哈垃圾 $Vxlimo$ 今年第二次参加同步赛！

对同步赛！（ $NOIP$ 又只有二等的屑

知乎：如何评价 $FJOI2021$？ $Vxlimo$ 的回答

$Link$

给定一个 $n$ 个点 $m$ 条边的简单无向连通图，其中图的前 $n-1$ 条边构成了图的一棵生成树。

你需要为每条边分配一个范围在 $[1,m]$ 的权值，且每种权值只能用一次。

定义一种分配方案的得分是这个图的最小生成树的权值和。

求所有可能的分配方案中，前 $n-1$ 条边是图的最小生成树的方案的得分和，对 $10^9+7$ 取模。

$2\le n\le20,n-1\le m\le\frac{n(n-1)}{2}$。

$Link$

给定一棵 $n$ 个点的树，边上有边权 $a_i$。

每次操作可以把一条简单路径上所有边的边权异或上一个数，求把所有边的权值都变成 $0$ 的最小操作次数。

$2\le n\le10^5,0\le a_i\le15$。

$Link$

给你一个长度为 $n$ 的非负整数序列 $a$，保证其中的数两两不同。求从中选择 $1\sim k$ 个数，使得这些数与起来等于 $s$，或起来等于 $t$ 的方案数。

$1\le n\le50,0\le a_i,s,t<2^{18},\forall i\not=j,a_i\not=a_j$。

$Link$

给定一棵 $n$ 个点的树，每个点可以染成黑色或者白色。定义一种染色方案的得分为 $\operatorname{max}($ 最远的一对黑点的距离 $,$ 最远的一对白点的距离 $)$。

求所有可能的染色方案的得分之和，对 $10^9+7$ 取模。

$2\le n\le2\times10^5$。

$Link$

有一个小写字母串 $S$。

有 $n$ 种操作，每种操作可以执行任意次。第 $i$ 种操作是将区间 $[l_i,r_i]$ 的字母变为它在字母表中的后继（$z$ 的后继为 $a$）。

问能否可以通过这些操作将 $S$ 变为一个回文串。

$1\le|S|,n\le10^5$。