Gym-103438C Werewolves

题面

有 \(n (1 \le n \le 3000)\) 个节点的树，每个节点的颜色为 \(c_i\)。

请计算这个树存在多少不同的连通子图，满足这个连通子图中，存在某种颜色，其出现次数 严格大于 连通子图中节点数量的一半。

简化题意

first

• 对于任意一个联通子图，如果该联通子图对答案有贡献，则一定只有一种颜色，在其中出现次数严格大于连通子图中节点数量的一半。
• 所以可以枚举颜色，讲树分为黑白两种颜色。

second

• 对于任意一个联通子图
• 假设是颜色 \(C\) 的节点在其中出现次数严格大于连通子图中节点数量的一半。
• 设 \(x\) 为颜色 \(C\) 的节点数量，\(sum\) 为联通子图的节点数量。
• 该联通子图对答案有贡献，当且仅当（这里的除法都是向下取整）：
  • \(x > sum \div 2\)
  • \(x \times 2 > sum\)
  • \(x \times 2 - sum > 0\)
• 设 \(y = x \times 2 - sum\)。
• 依据最后推导出的公式，发现颜色 \(C\) 的节点对 \(y\) 的贡献是 \(1\)，其余节点对 \(y\) 的贡献是 \(-1\)。

实现 \(O(n^3)\)

• 化简了题意，接下来就是实现了。
• 这显然是树上背包，需要注意的是：
  • 注意 \(y\)，在背包的途中可能会为负数，所以树上背包不可以在其中实现自我滚动，需要手动进行滚动。
  • 在手动滚动的时候，记住树上背包是将一棵树不断转化为二叉树进行合并，所以在更新辅助数组的是在枚举儿子的 for 循环中执行