这个题好神仙哦（
设 f(n) 表示点权乘积为 n 的所有方案的权值（答案）之和。
不难看出这个函数是个积性函数，因为权值互质意味着两棵树的所有点都两两互质，那么 gcd 什么的就直接乘起来就可以。
既然要求是正奇数，那么只需要强制令偶数处的 f 值为 0 即可。
则注意到 f(p)=[p>2]np，其中 p 为质数。
考虑 Min_25 筛，则需要求出 f(pk) 的值。
注意到若乘积为 pk 的形式，那么每个点的权值显然也是 pk 的形式。
又注意到由于不需要考虑 2，所以 k≤⌊log31010⌋=20。
于是可以全部 logp，设 cntx,y 表示给这棵树上赋点权使得点权之和为 x，所有路径上的点权 min 之和为 y 的方案数。
首先考虑一下当 x 确定时 y 的上界。
设 gu,i=[au≥i]，则 n∑u=1x∑i=1gu,i=n∑u=1au=x。
令 Path 为所有路径的集合，则有 y=∑S∈Pathminu∈Sau=∑S∈Pathx∑i=1∏u∈Sgu,i=x∑i=1∑S∈Path∏u∈Sgu,i
注意到对 0/1 进行乘法相当于取 min，所以可以通过只乘路径的起点和终点来进行放缩。
即 y≤k∑i=1n−1∑u=1n∑v=u+1gu,igv,i=12k∑i=1(n∑u=1gu,i)(1+n∑u=1gu,i)≤12(k∑i=1n∑u=1gu,i)(1+k∑i=1n∑u=1gu,i)≤x(x+1)2
（DH 大佬的证法看得不是很懂，感觉自己只能从他的思路证出 y≤x(n+1)2）
于是考虑一个非常暴力的 DP，设 fu,i,v,S 表示 u 的子树内权值和为 i，所有路径上点权 min 之和为 v，所有点到 u 的路径上的 min 值的可重集为 S。
转移考虑枚举 au，对 i 维做树形背包，另外枚举当前的 v,S 和儿子的 v,S 并合并状态。
这个东西显然是不能过的，复杂度我也算不出来（
注意到显然有很多无用状态，首先考虑有多少种 S。
首先发现 S 中的 0 是无用的，可以忽略。
由于 S 的元素和显然不超过 i，所以 S 最多有 i∑j=1partition(i) 种，其中 partition(n) 表示 n 的划分数。
当 i=20 时这个值为 2714，可以接受。
然后考虑将 v,S 视作一个二元组，在数据随机的情况下，且确定了 u,i 的情况下，大概有 17000 种不同的这样的二元组，依然可以接受。
最后一个问题在于如何离散化状态，以及加速状态合并。
关于离散化状态，首先先通过状态压缩 S 将 S 离散化。
（状压可重集的方式是同一种元素用若干个连续的 1 表示这个元素的个数，不同种类元素用 0 隔开）
然后直接开一个数组来存储 (v,S) 的对应关系。
加速状态合并的话，考虑合并 (v0,S0),(v1,S1)。
得 (v0+v1+∑x∈S0∑y∈S1min{x,y},S0∪{min{y,w}∣y∈S1})
这些东西都预处理一下就可以了。
细节超多（
请配合 O2 使用（
代码：
1 |
|