Multihedgehog
定义一棵树 k-multihedgehog：
对于 1-multihedgehog，其中一个点度数 $\ge3$ ，其它点度数均为 $1$.
k-multihedgehog 是在 k-1-multihedgehog 的基础上，把所有度为 $1$ 的点替换成一个 1-multihedgehog 并与原图相连。
给出一颗树以及一个数k，问是否为k-multihedgehog。
0%
String Coloring (hard version)
给你一串长度为 $n$ 的字符串，你可以给每个位置上染上一种不大于 $n$ 的颜色
对于相邻的两个位置，如果他们的颜色不同则可以交换他们的位置
现在需要交换若干次后按照字典序排序
你需要找到最少满足条件的颜色数并输出方案
Boboniu Chats with Du
你用过 QQ 吗？在 QQ 群里，管理员可以禁言用户。
在 Boboniu 的 QQ 群里，小D 每天都开 Boboniu 的玩笑。
小D 会在群里待 $n$ 天，Boboniu 的心情是 $m$。在第 $i$ 天，如果 小D 没被禁言，他会开一个严重程度为 $a_i$ 的玩笑；如果开的玩笑严重程度大于 $m$，他就会被 Boboniu 禁言 $d$ 天，也就是说，在第 $i+1,i+2,\dots,\min(i+d,n)$ 天，他都会被禁言。
请求出 $a$ 所有置换中严重程度之和的最大值。
TediousLee
如果 $x$ 没有孩子，那么给他加上一个孩子。
如果 $x$ 只有一个孩子，那么给他加上两个孩子。
如果 $x$ 已经有了超过一个孩子，那么我们跳过节点 $x$。
首先，我们定义 RDB 为一棵具有特殊性质的树，它有一个级别 $level$。
一个级别为 $1$ 的 RDB 是一个单独的节点。
接着，对于所有 $i>1$，级别为 $i$ 的 RDB 的构成方法如下。
先求出级别为 $i-1$ 的 RDB，然后对于该 RDB 中的每个节点 $x$。
以下是 $1\le n \le 3$ 的所有 RDB
接下来，我们定义一个 claw （见下图），它也是一棵具有特殊性质的树，并且将节点 $1$ 称为这个 claw 的中心，其他的称为底部节点。
现在，给出一个级别为 $n$ 的 RDB，初始时他上面的所有节点都为绿色，你可以进行一些操作。
对于每次操作，你需要在给出的 RDB 中找到一个 claw，满足所有底部节点在 RDB 中都是中心节点的儿子，且这四个节点在 RDB 中都是绿色。然后将这四个节点染为黄色。
问最多可以将多少个节点染成黄色。
输入格式
第一行一个整数 $T$，表示数据的组数。
接下来 $T$ 行，每行一个正整数 $n$，表示有一棵级别为 $n$ 的 RDB。
输出格式
输出有 $n$ 行，每行一个整数，对应每组数据的答案。
这个答案可能很大，所以输出它对 $10^9+7$ 取模后的结果。
说明与提示
$1\le T\le 10^4$
$1\le n \le 2\cdot 10^6$
感谢 @_Wolverine 提供的翻译
MinOr Tree
给定 $n$ 个点 ， $m$ 条边 $(3 \le n \le 2 \times 10^5,n - 1 \le m \ \le 2 \times 10^5)$ , 求在或运算下的最小生成树。
保证图联通。