【HackerRank】Unique Colors

相关链接

题目传送门: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 的贡献:

  1. 点3点1 的简单路径上没有染色点
    那么贡献为\({T_1} – {T_3}\)
  2. 点3点1 的简单路径上有染色点
    那么贡献为\({S_1} – {S_2}\)

这样的话,只有一种颜色的情况就解决了
现在考虑有多种颜色:

不难发现对于一个固定点i,颜色只需要分两类:
1. 到分支点的路径上出现过该颜色
2. 到分治点的路径上没有出现过该颜色

这样的话,我们发现只需要一次DFS就可以解决这个问题
于是就可以使用点分治解决这个问题啦!

Ⅱ. DFS序的做法 \(O(n)\)

先来考虑一个简单一点的版本:假如这货是在序列上
考虑每一种颜色单独处理的话,就是将序列分成几块,每一块的贡献不同
现在重新考虑树上的版本,其实也是把整个树分成好几块
酱紫的话,我们唯一需要解决的就是如何给树上一个连通块统一加上一个数

我们发现我们可以先搞出一个最小的包含“需要更改的连通块”的子树
然后去掉一些子树来删掉多余的部分
子树操作的话,在DFS序上是连续的,于是打差分就好
因为题目的特殊性,不难发现需要删掉的子树总共只会有\(O(n)\)个
于是此题就 \(O(n)\) 辣!

Code

好像两种写法都不是特别好写的样子
于是就不写代码辣!

发表评论

电子邮件地址不会被公开。 必填项已用*标注