https://www.hackerrank.com/challenges/unique-colors does anyone know how to solve this problem??? I dont understand the problem setter's solution. thanks a lot
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
https://www.hackerrank.com/challenges/unique-colors does anyone know how to solve this problem??? I dont understand the problem setter's solution. thanks a lot
Название |
---|
First, sorry for my bad English. We use Centroid-decomposition. We store an array res[] — the result for each node With a tree with root R. we add for each node in the tree the amount of color and path that pass the root R.
for each node u in the tree, let x be the color of this node, if the path from it to root doesn't have x, so that for other node v, that LCA(u , v) = R we can increase res[u] an amount = chil[v]. chil[x] is number of nodes in the subtree x. so that we store f[u]: f[u] = chil[u] if the color in u is unique in the path from u to root, else f[u] = 0;
we store a number "total": that number of colors that a node can add for itself. total = sum of all f[u] (u != R). we store sum[x] : sum of all f[u] which color[u] = x; we use dfs, when you reach a node u, if f[u] > 0 , we must decrease total an amount (sum[color[u]] — number of color[u] in the subtree neareast root which contains u); and then we add to res[u] : res[u] += total, and res[u] += number of different colors in the path from u to root * (chil[R] — chil[x]) — x is the node neareast root which its subtree contain u. when we finish dfs at u, if (f[u] > 0) we must increase total an amount like we decreased. finish solve with root R, continue for other root by using centroid-decomposition.
Here is my code https://ideone.com/d7VGFi
thanks