task1 n=1

输出 $1$ 到 $n$ 中所有奇数的和即可

task2 m<=100

暴搜

task3 m<=10^6,n<=10

设 $f(i)$ 表示权值乘积为 $i$ 的树的权值和

容易看出 $f(i)$ 为积性函数

因此只需要求出所有 $f(p^k)$ 的值

考虑这样一个问题:对树上每个点分配一个非负整数权值 $a_i$ ，使得 $\sum a_i=k$

求对于每个 $v$ ,树上所有路径上的权值 $min$ 的和为 $v$ 的方案数

容易发现只要求出这个问题，就可以求出 $f(p^k)$

首先考虑 $v$ 的上界

设 $g_{u,i}=[a_u>=i]$ ,则 $\sum_u \sum_{i=1}^k g_{u,i} =k$

有 $v=\sum_{S\ is \ a \ path \ in \ T} min_{u\in S}a_u$

$v=\sum_{S\ is \ a \ path \ in \ T} \sum_{i=1}^k \prod_{u\in S}g_{u,i}$

$v=\sum_{i=1}^k \sum_{S\ is \ a \ path \ in \ T} \prod_{u\in S}g_{u,i}$

容易证明，对于 $n$ 个点的森林，不同路径数不超过 $n*(n-1)/2$

因此 $v\leq \sum_{i=1}^k (\sum_ug_{u,i})*(\sum_ug_{u,i}-1)/2$

因为 $\sum_{i=1}^k\sum_u g_{u,i} =k$ ，可以得到 $v\leq k*(k-1)/2$

对于这一个task， $k\leq 12$ ,可以暴搜所有 $a_i$ ，然后线性筛 $f$ 即可

task4 m<=10^10,n<=10

对于 $n\leq10,k\leq20$ 的部分，暴搜可以较快的得到答案

注意到 $f(p)=[p>2]p$ ，$f(p^k)$ 已经求出，因此可以 min_25 筛解决问题

task5 m<=10^6,n<=50

考虑一个 $dp$ : $dp_{i,j,v,S}$ 表示 $i$ 的子树内，已经分配了 $j$ 的权值， $i$ 子树内的路径点权 $min$ 和为 $v$，当前 $i$ 子树内的每一个点到 $i$ 路径上的点权 $min$ 组成的可重集为 $S$ ，当前的方案数

首先可以无视 $S$ 中的 $0$ ,对于一个点 $u$ ,$u$ 到 $i$ 路径上的点权 $min\leq a_u$

因此 $S$ 中元素和小于等于 $j$ ,因此不同的 $S$ 最多有 $\sum_{i=0}^k partition(k)$ 个

在 $k\leq 12$ 时有 $272$ 个， $k\leq 18$ 时有 $1597$ 个， $k\leq 20$ 时有 $2714$ 个

考虑将 $v$ 和 $S$ 压成一个状态，发现在随机下这个状态不会太多， $k=20$ 大概在 $17000$ 以下(我不会证不随机时的极限)，在 $k\leq 12$ 时更小，可以计算一个 $hash$ 值，开map统计

$dp$ 转移时，枚举 $i$ 位置的权值 $a_i$ ,然后依次枚举每个子树内的权值和和状态，暴力合并状态

这样在随机下效率很好，可以通过

task6 m<=10^9,n<=50

task7 m<=10^9,n<=100

task8 m<=10^10,n<=50

上述算法不同常数的实现

task9 m<=10^9,n<=50

仍然是上一个算法，考虑如何加速状态合并和如何去掉map

以下是一种方式:

我们用一个数 $v$ 来表示 $S$ ，$v$ 的计算方式如下:

如果 $S$ 中有一个 $1$ ,$v$ 值等于 $S$ 删去这个 $1$ 后的值乘 $2$ 加 $1$

否则, $v$ 值等于 $S$ 中所有元素减 $1$ 后的集合的值乘 $2$

可以发现这样一个 $v$ 对应的 $S$ 唯一，且这样的 $v$ 不会大于 $2^{S元素和}$

对于两个 $v$ ，可以较快的合并，具体参考std

因为 $v$ 不大，所以可以用数组实现 $v$ 和 $1 - 2714$ 的对应

然后考虑状态第一维不超过 $190$ ,第二维不超过 $2714$ ，因此可以用另外一个数组实现对应，这样就去掉了map

加上上面的优化即可通过此题