Gym-103438C Werewolves
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 循环中执行