前言
出题人个人认为的题目难度排序是（难度从小到大）：第二题，第三题，第一题。为了防止部分选手卡题，所以特意添加了提示，是不是很良心？（雾）
小D与迷宫(maze)
问题转化
可以发现，题目等价于求，有多少个$n$个点（带标号）的深度不超过$k$（根节点深度为$1$）的森林。
Algorithm 1
当$k=1$时，那么显然所有点都得要是汇点，也就是没有边。因此此时答案为$1$。
时间复杂度：$\Theta (T)$，空间复杂度：$\Theta (1)$，期望得分：$5$分。
Algorithm 2
当$k=2$时，我们可以枚举汇点个数，那么其他点可以随意的挂在这些点上面。即，答案为：$\sum_{i=1}^n(n-i)^i\cdot {n\choose i}$。
时间复杂度：$\Theta (T\cdot n\log_2n)$，空间复杂度：$\Theta (1)$，期望得分：$10$分，结合Algorithm 1可以得到$15$分。
Algorithm 3
在Algorithm 2的基础上进行优化，我们可以改为枚举深度为$2$的点，那么答案为$\sum_{i=0}^{n-1}i^{n-i}\cdot {n\choose i}$，我们预处理阶乘、阶乘的逆元以及逆元即可做到$\Theta (n)$计算。
时间复杂度：$\Theta (T\cdot n)$，空间复杂度：$\Theta (n)$，期望得分：$25$分，结合Algorithm 1可以得到$30$分。
Algorithm 4
当$k=n$时，我们就是要求迷宫的个数。那么可以由$Matrix\ Tree$定理算出答案即为：$(n+1)^{n-1}$。
时间复杂度：$\Theta (T\cdot \log_2n)$，空间复杂度：$\Theta (1)$，期望得分：$20$分，结合Algorithm 1 & 3可以得到$50$分。
看起来有特殊性质的点都基本上用完了，我们来想一想通用的解法。
Algorithm 5
由Algorithm 4可知，迷宫个数不超过$(n+1)^{n-1}$，那么暴力枚举每一个迷宫并进行判断的复杂度为$\Theta ((n+1)^{n-1}\cdot n)$。
时间复杂度：$\Theta (T\cdot (n+1)^{n-1}\cdot n)$，空间复杂度：$\Theta (n)$或$\Theta ((n+1)^{n-1})$，期望得分：$10$分，结合Algorithm 1 & 3 & 4可以得到$60$分。
Algorithm 6
考虑$dp$，设$f_{k,n}$表示深度$\le k$的$n$个点带标号森林的个数。
设$g_{k,n}$表示深度$\le k$的$n$个点带标号树的个数。
那么我们考虑把一个树去掉根节点，他就变成了一个深度$-1$的森林，因此：$g_{k,n}=f_{k-1,n-1}\cdot n$。而森林是由一群树组成的，那么这里也是利用组合数加以转移的。
时间复杂度：$\Theta (n^2\cdot k+T)$，空间复杂度：$\Theta (n^2\cdot k)$，期望得分：$40$分，结合Algorithm 1 & 3 & 4可以得到$80$分。
Algorithm 7
考虑指数型生成函数。设$\hat F_k=\sum_{i=0}^{+\infty}f_{k,i}\cdot \dfrac{x^i}{i!},\hat G_k=\sum_{i=0}^{+\infty}g_{k,i}\cdot \dfrac{x^i}{i!}$。
那么有：$\hat G_k=\hat F'_{k-1}$，其中$\hat F'_k=\sum_{i=1}^{+\infty}f_{k,i-1}\cdot \dfrac{x^i}{i!}$。
因为森林可以表示成树的无序不交并，所以由泰勒展开式可知$\hat F_k=e^{\hat G_k}=e^{\hat F'_{k-1}}$，写一个多项式$exp$就好了。
时间复杂度：$\Theta (n\cdot k\cdot \log_2k)$，空间复杂度：$\Theta (n\cdot k)$，期望得分$75$分或$80$分（取决于常数），结合Algorithm 4可以得到$95$或$100$分。
小D与道路(road)
Algorithm 1
信仰法：直接输出所有边权和，可以通过第一个子任务。
时间复杂度：$\Theta (m)$，空间复杂度：$\Theta (1)$，期望得分：$5$分。
Algorithm 2
暴力枚举每一条边是否保留，然后通过$dfs$或者$bfs$判断是否美观。
时间复杂度：$\Theta (2^m\cdot n)$，空间复杂度：$\Theta (n+m)$，期望得分：$30$分，结合Algorithm 1可以得到$35$分。
问题转化
考虑$1\sim n$的路径上的点，称他们为关键点，则美观的图的形态一定是：关键点下面挂着一个子图（可以为空，也可以不联通），而且不同点下面的子图互不连通。
Algorithm 3
那么考虑$dp$：$dp_{S,u}$表示现在考虑点集$S$，他们之间的连边已经确定了，且$1\sim u$的路径唯一。
于是转移有两种：
- 新增一个关键点，设这个点是$v$，则$v\not \in S$。
因为他得要接在$u$后面，所以$(u,v)\in E$。
那么转移就是$dp_{S\cup \{v\},v}\gets dp_{S,u}+w(u,v)$，其中$w(u,v)$表示$u,v$之间的边的边权；
- 给$u$下面挂上一个子图，设这个子图的点集为$T$，则$S\cap T=\phi$。
那么我们可以保留$T\cup \{u\}$中的所有边，而其他边一条不能有，否则就违反上面加粗的条件了。
则转移就是$dp_{S\cup T,u}\gets dp_{S,u}+sum_{T\cup \{u\}}$，其中$sum_S$表示点集$S$内部的边权和。
那么转移的复杂度就是$\Theta (n+2^n)$，而状态数为$\Theta (2^n\cdot n)$，因此总时间复杂度为$\Theta (4^n\cdot n)$，空间复杂度为$\Theta (2^n\cdot n)$，期望得分：$50$或$68$分（取决于算法实现中的常数），结合Algorithm 1可以得到$55$或$73$分。
Algorithm 4
注意到Algorithm 3的时间瓶颈在于第二种转移，考虑优化。
因为$S\cap T=\phi$，因此$T\subset \overline S$，那么我们可以直接枚举$\overline S$的子集，设这个集合为$X$，那么可以用下面的伪代码段实现（这里的$X,T$均用二进制来状态压缩）：
$T\ \gets\ X$
while $T\ \ne\ \phi$
// do something here
$T\ \gets\ (T-1)\wedge X$
end while
那么利用等比数列求和公式，可以证明这样优化之后算法的总复杂度是$\Theta (3^n\cdot n)$，空间复杂度仍然是$\Theta (2^n\cdot n)$，期望得分：$83$或$90$分（取决于常数因子），结合Algorithm 1可以得到$88$或$95$分。
Algorithm 5
诶？我怎么写了Algorithm 4然后加了点(wáng)优(yì)化(sōng)就$100$了？是不是数据造水了？
别急，我们来理性分析一波：显然只有$1\in S$的状态才是有效的，所以我们在进行转移之前直接跳过无用状态就可以使状态数变成至多$2^{n-1}\cdot n$，那么这样之后总的复杂度也就是$O(3^{n-1}\cdot n)$。
所以理论上加入跳过无用状态这么一个一行代码的优化就可以获得$100$分辣！是不是很简单？
小D与圣诞树(tree)
因为对于$100\%$的数据，$n,m$同阶。所以题解中的复杂度均用$n$代替$m$。
定义题解中用到的一些符号如下：
- $f_u$表示点对$(1,u)$的美观度。
- $p_{u,v}$表示距离$v$最近的$u$的邻居，特别地，$p_{u,u}=u$。
Algorithm 1
暴力按照题意模拟。
时间复杂度：$\Theta (n^2)$，空间复杂度：$\Theta (n)$，期望得分：$15$分。
Algorithm 2
对于$t=1$的子任务，因为没有修改，那么因为每个点的初始装饰品均不相同，所以点对$(u,v)$的美观度就是两点路径上经过的点数。那么对于点对的询问，直接求出$LCA$然后算距离即可。对于子树的询问，可以预处理每一个子树中最深的点的深度。
时间复杂度：$\Theta (n\log_2n)$或$\Theta (n)$，空间复杂度：$\Theta (n\log_2n)$或$\Theta (n)$，期望得分：$10$分，结合Algorithm 1可以得到$25$分。
Algorithm 3
对于$t=2$的子任务，因为是一条链，由定义可以知道显然越深的点的$f$越大。所以对于子树询问，肯定是选择最深的点，因此只要维护现在有多少种不同的颜色即可。
对于点对询问，我们可以注意到最终的颜色一定分成一段一段的，同一种颜色不会被断开。那么我们设询问的$(u,v)$中，深度较深的为$v$，则答案就是$f_v-f_u+1$，这可以用线段树维护$f$来实现。
时间复杂度：$\Theta (n\log_2n)$，空间复杂度：$\Theta (n)$，期望得分：$15$分，结合Algorithm 1 & 2可以得到$40$分。
问题转化
有了链的问题的铺垫，我们可以发现在树上每种颜色也是一条竖着的路径（即上面的点的深度是单调的，不会拐弯）。
因此我们设$LCA(u,v)=x$，则$x$的颜色不会和$p_{x,u},p_{x,v}$均相等。那么我们讨论一下有没有和其中某一个相等，就可以得到点对$(u,v)$的美观度公式为：$f_u+f_v-2\cdot f_x+1$。
Algorithm 4
对于$t=3,4,5$的子任务，因为数据随机，所以树的期望深度是$\log_2n$级别的。那么我们可以使用线段树维护$f$，每次修改时暴力的走$u$到$1$的路径，算出每一个子树的$f$的变化，用线段树区间修改。
询问点对时求出$LCA$，然后利用上面的式子求。子树的询问可以维护线段树区间最大值来实现。
时间复杂度：$\Theta (n\log_2^2n)$，空间复杂度：$\Theta (n\log_2n)$，期望得分：$28$分（如果其中某种询问的处理方法没有想到也可以获得$10$分），结合Algorithm 1 & 2 & 3可以得到$68$分。
Algorithm 5
联想到$ZJOI\ 2018\ 历史$，可以发现这两个题目的修改方式很类似。
注意到我们如果把同色点（颜色均指装饰品的种类）之间的边看成实边，异色点之间的边看成虚边，那么其实一次对$u$的修改就是$LCT$中$access(u)$的操作。
于是我们可以直接用一棵$LCT$，在$access$中连接、断开边会导致各自的子树$\pm 1$，那么直接用线段树区间加维护$f$即可。询问的处理方法同Algorithm 4。
时间复杂度：$\Theta (n\log_2^2n)$，空间复杂度：$\Theta (n\log_2n)$，期望得分：$95$或$100$分（取决于算法实现时的常数）。
