这道题可以离线回答，很大概率是什么树上差分之类的东西。但是树上差分无法维护区间信息，然后想到用权值线段树来维护。如果暴力开\(1e5\)个线段树来维护会 GG，但是我们可以动态开点，然后每个点对应的线段树大小差不多为\(O(\log n)\)级别的，这样空间就可以接受的了。
既然有了很好用的动态开点线段树，我们就可以用树上差分那一套路，在端点和\(LCA\)处打标记，然后考虑从下往上合并答案。合并可以用线段树合并，复杂度为重合部分，差不多就是\(O(\log n)\)。然后就没了，很傻逼的一道题。
这道题原题解作者的思路非常的清晰。我来阐述一下。
首先思考答案的意义，一定是总的权值和减去：
我们可以用上面这三个元素组一个网络流，计算最小割使答案最大。
考虑将源点连入雌性，雄性连入雄性，流上限就是变性花费：如果将这种边割掉，那么就是不需要进行变性。考虑朋友的边，如果倾向于变雌性，源点连入，向所有的对应编号连边；如果雄性，连入汇点，所有对应编号的向该朋友连边。
这道题所有购买方案的取值上界为\(a_i \times k\)，差不多就是\(1e5\)级别。考虑超级大暴力，设置状态\(f[i][j][w]\)为选了\(i\)个次、最后一次是第\(j\)种硬币且当前总价为\(w\)是否可行。这个转移算上取值上限就差不多是\(O(n^4)\)的，只能过掉一部分分数。
考虑进行状态转化。我们先让所有商品的价格减去价格最小值，然后剩下购买的方案就变成了形如\(k*minVal + sum\)的形式，然后我们设置状态\(f[i][j]\)最后一次选第\(i\)种商品，且选到\(j\)的最少选择次数，统计次数小于\(k\)的状态就可以了。
真你妈毒瘤。
原式子是长这个样子的：
\[ f(n) = \sum_{i = 0}^n \sum_{j = 0}^i \begin{Bmatrix} i \\ j \end{Bmatrix} 2^j (j!) \]
我们发现，直接算一个连通块非常的困难。这个时候可以尝试容斥。我们发现至少一个的特别好算：划分至少\(i\)个连通块的答案记为\(g(i)\)。\(g(i)\)比较好算，可以考虑 DFS 枚举出每一个点所在的连通块根，然后把连通情况放入线性基中，如果线性基插入失败，那么说明当前的情况不能被表示出，且该状态符合划分，那么计入小答案\(tot\)，最后对答案的贡献就是：\(2^{tot}\)。
现在考虑如何用\(g(i)\)算恰好\(i\)个连通块的答案\(f(i)\)。考虑搞下容斥系数，使得\(f(i)\)只被计算一次：
\[ \sum_{i = 1}^n \begin{Bmatrix} n \\ i \end{Bmatrix} coefficient(i) = [n = 1] \]
打表出来就是：
\[ coefficient(i) = (-1)^{i – 1} (i – 1)! \]
考虑超级暴力，设计状态\(dp[k][i][j]\)为走了\(k\)步处于\((i, j)\)的答案：
\[ dp[k][i][j] = mp[i][j] + \max \begin{cases} dp[k – 1][i – 1][j] \\ dp[k – 1][i + 1][j] \\ dp[k – 1][i][j + 1] \\ dp[k – 1][i][j – 1] \end{cases} \]