最不想写的一集。
A. 树与路径（path）
题目简介
给定一棵有 个结点的树，定义 表示用恰好 条不交的路径实现整棵树的边覆盖的方案数。这里的不交指的是边不重合，一个结点能够被覆盖多次。
对 求出 ，对 取模。
数据范围：
考虑一个朴素的 ，设 表示 子树内的所有边，包括 被 条路径覆盖的方案数。
我们首先不考虑存在跨过 的路径，即不存在路径 。那么这个转移为：
这是一个树上背包的转移形式，可以做到 合并。
然后考虑跨过 的路径，设度数为 ，那么对于所有与 相连的边，其必须两两配对，如果是奇数则还会剩下一条延伸到祖先。
基于上面的转移，我们会合并两条路径（交在了 上），设我们合并了 条路径，那么转移：
其中 为所有 的奇数的乘积，这个计算方式与去年初赛某一道有歧义的题的计算方式相同。
所以总时间复杂度 。
考虑到去年我们在 上同样做过一道 的类树上背包的树型 。我们采用同样的优化方式。
一个树上背包的经典 ，发现这个转移就像是多项式合并一样，所以用分治 优化，可以做到 。
B. 树据结构（tree）
题目简介
给定一棵有 个结点的模板树，以及一棵初始与模板树相同的大树。树边有权值，接下来维护 次操作：
- 将模板树中路径 中的边边权加 ；
- 将模板树复制一份连接在大树编号为 的结点下，连接边权为 ；
- 求大树路径 的边权和；
- 求大树以 为根的子树内的边权和。
部分数据强制在线。
数据范围：
这题完整代码 ，说点对考场有用的。
离线的话，我们完全可以直接把大树给建出来。但我们不可能在一棵有 个结点的树上跑树剖，这显然不现实。
所以我们考虑以每一棵模板树作为大树的结点，形成一棵「树套树」。
我们每挂一个结点，对于其祖先结点在查询子树时就会增加 的模板树边权和。所以这一部分我们可以通过 序维护 前缀和来解决。而在查询路径的时候，我们可以预处理出倍增距离数组然后跳到 求和。
然后你发现用 的时候是不需要离线的，直接做即可，否则可能还会计算到询问之后添加的子树上去。
的时候无视操作 ，就是一个动态加点的查询路径和子树和问题。
加点操作可以用 维护，查询路径是 的基本操作，但是不容易维护子树和。因为 认父不认子。
考虑统计一个结点 所有虚儿子的结点信息（虚儿子指的是 ），记录 表示虚儿子贡献， 表示子树贡献。
所以我们把 的贡献纳入 就可以统计出所有子结点的贡献，在虚实边交换的时候需要修改 的权值。
需要注意的是 的子树信息仅能维护具有差分性质的（如最值就不行），否则需要用 套平衡树才能实现。
把大树中每一个模板树打包成一个结点，其中连边的权值修改为 连接的点到其根的长度和，那么现在的问题就和 一样考虑，用 维护即可。
但模板树可能会被修改，所以对于模板树我们用树剖维护主席树来获得其修改权值，需要支持的操作是区间加和区间查询历史版本和，所以这个主席树是区间修改的，需要标记永久化。
看上去就十分阴间，不想写。
我们同样大树上的每一棵模板树抽象成一个结点，然后对每一个结点维护一棵平衡树（题解使用的是 ），维护所有挂在这个结点上的所有其它模板树的边权和。
所以这个时候查询子树和就相当于是查询 的区间和了。
然后考虑如果大树静态，我们可以对其进行树剖，对每一条重链深度后缀打上标记，表示真实的子树权值，然后对于轻儿子暴力下方标记，这个过程不会超过 。
所以整体而言就是一个区间修改区间查询的 。
树链剖分静态转动态的方法就是变成 维护，但 有虚实链反转的操作，这个时候需要维护标记，每加入一个新的结点就 access，然后对交换了的链维护标记，维护次数也不会超过 ，还可以同时下放标记。
然后你发现正解就是把维护路径和维护子树的两种方法揉在一起。
但两种方法无论哪一种拎出来都是毒瘤级别的存在，更别说 和 写出来 左右了。
C. 树上的数（number）
题目简介
存在一个有 个结点的树，你需要对其结点赋值，记赋值序列为 ，其中， 必须为正奇数，且满足 。
我们定义一个点对 的权值为 到 路径中所有经过点的点权的 ，然后我们定义一个赋值序列的权值为所有无序点对的权值和。
求出所有合法赋值序列的权值和。对 取模。
数据范围：
时空限制：
首先设定状态 表示考虑 的子树中已经分配了 的权值，当前子树内路径点权 的和为 ，当前所有子树内点到 的点权 组成的可重集为 的方案数。
首先可以无视 中的 ,对于一个点 ， 到 路径上的点权 。
因此 中元素和小于等于 ，因此不同的 最多有 个。在 时有 个， 时有 个， 时有 个。
考虑将 和 压成一个状态，发现在随机下这个状态不会太多， 大概在 以下（不会证不随机时的极限），在 时更小，可以计算一个 值，开 std::map 统计。
转移时，枚举 位置的权值 ，然后依次枚举每个子树内的权值和和状态，暴力合并状态。
这样在随机下效率很好，可以通过部分分。
考虑如何加速状态合并和如何去掉 std::map，我们用一个数 来表示 ， 的计算方式如下:
如果 中有一个 ， 值等于 删去这个 后的值乘 加 ，否则， 值等于 中所有元素减 后的集合的值乘 。
可以发现这样一个 对应的 唯一，且这样的 不会大于 ，其中 表示 的元素和。
对于两个 ，可以较快的合并，因为 不大，所以可以用数组实现 和 的对应。
然后考虑状态第一维不超过 ，第二维不超过 ，因此可以用另外一个数组实现对应，这样就去掉了 std::map，加上上面的优化即可通过此题。