相关链接
题目传送门:https://www.hackerrank.com/challenges/unique-colors
题目大意:http://paste.ubuntu.com/23686184/
官方题解:https://www.hackerrank.com/challenges/unique-colors/editorial
解题报告
Ⅰ.点分治的做法 \(O(n\log (n))\)
先考虑一种较为简单的情况:只有一种颜色
询问有多少对节点间至少存在一个点被染色直接考虑点分治的做法的话
设当前的分治点为1
定义\({T_i}\)为点i的子树中到1号点的路径上有点被染色的点的数量
定义\({S_i}\)为点i的子树中点的个数
考虑此时对 点3 的贡献:
- 点3 到 点1 的简单路径上没有染色点
那么贡献为\({T_1} – {T_3}\)- 点3 到点1 的简单路径上有染色点
那么贡献为\({S_1} – {S_2}\)这样的话,只有一种颜色的情况就解决了
现在考虑有多种颜色:不难发现对于一个固定点i,颜色只需要分两类:
1. 到分支点的路径上出现过该颜色
2. 到分治点的路径上没有出现过该颜色这样的话,我们发现只需要一次DFS就可以解决这个问题
于是就可以使用点分治解决这个问题啦!
Ⅱ. DFS序的做法 \(O(n)\)
先来考虑一个简单一点的版本:假如这货是在序列上
考虑每一种颜色单独处理的话,就是将序列分成几块,每一块的贡献不同
现在重新考虑树上的版本,其实也是把整个树分成好几块
酱紫的话,我们唯一需要解决的就是如何给树上一个连通块统一加上一个数
我们发现我们可以先搞出一个最小的包含“需要更改的连通块”的子树
然后去掉一些子树来删掉多余的部分
子树操作的话,在DFS序上是连续的,于是打差分就好
因为题目的特殊性,不难发现需要删掉的子树总共只会有\(O(n)\)个
于是此题就 \(O(n)\) 辣!