BZOJ3162:独钓寒江雪 – 题解

主要思路

刚看这题我人都是懵的…仔细看了看能大概想到，定一个根然后做 DP 得到方案，然后对于相同形态的子树进行方案分配即可。（但是不会写）

具体而言，转换成有根树的方法就是用重心来做根（如果有两个重心的话，就加一个虚根），并且每次 DFS 完之后用 Hash 值排序，然后进行分组转移。

转移的时候，可以给每一种情况进行标号，然后用前缀的组合意义来做转移即可。具体：\( dp[i] = \sum_{uniqueType \in subtree} {dp[uniqueType] + |subtree| – 1 \choose |subtree|} \)。

如果加了虚点，那就判一下就好了。

考虑三种最短路的形式：\(A \times dist, \lfloor \frac{dist}{2} \rfloor B + (dist \bmod 2) A, kB \)。前两种直接 BFS 一遍即可，第三种对路径有特殊要求：不能存在边集外一条边可以使得与路径的某两条边形成三元环。

说到三元环，我们就可以仿照那个根号的方法，先做标记，然后再枚举中间边。然而，这里我们没法拆成单向边，所以直接根号的做法是假的。

继续思考一个三元环 \((u, v, w)\)，发现如果我们找到了一个这样的三元环，至少我们可以直接删掉 \((v, w)\)，因为这个边不会再发挥作用了（因为我们在 BFS 的时候肯定提供最优解）。

规律题。只要能发现合法序列的极差不超过 \(1\) 这个性质就可以算了。直接：

\[ ans = 2 – n + \sum_{i = 1}^{n – 1} 2^{\gcd(i, n)} \]

然后这个显然可以用某些 Polya 题的方式用数论函数进行优化，就没了。

总有一种之前纪中 A 组做过的感觉，没想到真的做过，只是那个时候并不知道这个东西叫做 DP 套 DP。

这个题还蛮神仙的，我很喜欢。

如果是做暴力的话，那么这个思路是很有限的。我们考虑换一种思路。既然最后的答案是要求 \(\Theta(k^2)\) 级别对的最短路，我们尝试把这个规模进行缩小，然后只求小规模的全局解（并不是求出所有最短路），然后多次求解之后可以得到全规模的全局解。