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
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 161 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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
Name |
---|
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