- Prepare
- Data Structures
- Advanced
- Coloring Tree
- Discussions

# Coloring Tree

# Coloring Tree

+ 1 comment I see two ambiguties in this problem formulation, please correct me if I am wrong.

- It is, to me and also to @Shubham_2012 not clearly defined how to interpret which node is the i:th. is it the i:th node that we encountered during parsing or is it the one with the i:th value, starting from whatever the root node's offset is?
Edges are bi-directional as per the problem formulation ("In each of the next N-1 lines, there are two space separated integers(a b) representing an edge from node a to Node b

**and vice-versa**.", emphasis added). This means that there is no discernable difference between parent and child nodes. To see why this matters, say that I pick a node at random and call it the root of my subtree. Since all edges connected to it are bi-directional, even what we in some configuration could have regarded as the node's parent is also a child node. This means that, in essence, every subtree is the entire tree, only with a different root node. And so, the answer for how many colors there are should always be the same. Obviously, this cannot be correct, can it?P.S. Why does the commenting system here on hackerrank say that markdown is supported when it only works in the preview window?

+ 1 comment How to decide which is the ith node so that a color could be assigned to it? Will it be decided on the basis of its number, i.e. 1 is the 1st node, 2 is the 2nd node, and so on or on the basis of level order traversal of the tree?

+ 1 comment Can you please clarify how the subtree rooted with 1 and 2 results in 11 and 5 respectively? while the tree has only 9 and 4 nodes only.

Blog link in similar discussion is broken.

Best,

+ 0 comments If A and B are two sets with the size of A bigger than B then it is faster to do

A |= B B = A del A

than

B |= A del A

Knowing that it is possible to solve this problem the natural way (without segment tree). At least in python.

+ 1 comment Assuming that the edges are undirected, Sample test case's output should be 3 and 3. Because if you consider the tree rooted at 2, it will have 3 children; 1, 3, 4.

I think I am missing something here. Can you someone please explain how the answer is 2 and not 3 for the second query?

Thanks

Salil

Sort 24 Discussions, By:

Please Login in order to post a comment