组合好题，注意到 \(n\) 个点的边数为 \(n - 1\)，总度数为 \(2n - 2\)，因此序列 \(a\) 的权值不为 \(0\) 时当且仅当 \(\sum a = 2n - 2\) 且 \(a_i \gt 0\)。
接下来是一个简单的贪心，如果对于给定的序列需要构造出一个直径最大的树，我们钦定树上有 \(k\) 个叶子节点，在 \(a\) 中体现为 \(a_i = 1\)，此时只需要将剩下的 \(n - k\) 个节点全部串起来，再在两端放上两个叶子节点，构造出了一棵直径长度为 \(n - k + 2 - 1 = n - k + 1\) 的树，其余的叶子节点挂在 \(n - k\) 个节点上使其满足度数要求。
现在问题转化为，对于每个可能的叶子节点数 \(k \in [2, n - 1]\)，计算有多少个序列 \(a\) 满足恰好有 \(k\) 项 \(a_i = 1\)，然后将数量乘上对应的直径 \(d\)，最后统计总和就是答案。关键在于如何计算”恰好有 \(k\) 项为 \(1\) 的 \(a\) 的数量“。推导如下：
- 选 \(k\) 个叶子：\(\binom{n}{k}\)
- 分配剩余的度数：树的总度数和是 \(2n - 2\)，其中 \(k\) 个叶子节点已经占用了 \(k \times 1 = k\) 的度数，剩下的 \((2n - 2) - k\) 的度数还必须满足分配给剩下的 \(n - k\) 个非叶子节点，同时非叶子节点要求度数 \(\geq 2\)
- 将剩下的 \(2n - 2 - k\) 的度数视为相同的小球，分发给定的 \(n - k\) 个节点视为不同的盒子，每个盒子至少要放 \(2\) 个球，考虑插板法来解决这个问题：
- 由于每个盒子至少要有 \(2\) 个小球，我们先给 \(n - k\) 个盒子都分配 \(2\) 的度数，这样就提前分配出了 \(2 \times (n - k)\) 的度数
- 剩余度数为 \((2n - 2 - k) - 2 \times (n - k) = 2n - 2 - k - 2n + 2k = k - 2\)，问题再次转化为将 \(k - 2\) 个小球任意分配给 \(n - k\) 个不同的盒子，盒子可以为空
- 这就是标准的插板法：将 \(m\) 个小球放入 \(p\) 个不同的盒子，允许盒子为空的方案数是 \(\binom{m + p - 1}{p - 1}\)，代入公式 \(m = k - 2, p = n - k\)
- 因此分配方案数为 \(\binom{(k - 2) + (n - k) - 1}{(n - k) - 1} = \binom{n - 3}{n - k - 1}\)，根据组合数的性质 \(\binom{a}{b} = \binom{a}{a - b}\) 化简得到 \(\binom{n - 3}{k - 2}\)
综上所述得到了最终的求答案的式子：
这样子就做到了 \(O(n)\) 求和，我们还需要一点黑科技来将其变为 \(O(1)\) 的。
第一个是吸收恒等式（Absorption Identity），形式如：
其中 \(n \geq k \geq 1\)。恒等式的作用是”吸收“系数 \(k\) 从而改变组合数参数，同样有提取出来的恒等式：
证明直接展开组合数就可以了，当然通过组合意义证明更直观而且深刻，但是注意到”吸收恒等式“这个名称可能只流传在 OI 圈中，这个等式作为组合数的一个基础扩展并没有一个定称。
另一个是 范徳蒙德卷积：重点在于转化出两个组合数的下脚标之和为定值 \(k\)。
化简求和式：
拆开计算两者：
运用范徳蒙德卷积处理第一项：
运用吸收恒等式和卷积处理第二项：
终于降为了 \(O(1)\)，预处理一下组合数就做完了。