RBTREES - Editorial

stunn_areeb09 · August 25, 2020, 5:18pm

Did anybody did it with dp with states like dp[depth][0/1] with the answer being min(dp[1][0], dp[1][1]);

gpoxy · August 25, 2020, 7:20pm

Got the setter’s solution but the 2nd line of dfs in editorialist’s solution is going above my head… please can someone explain…

shashi_23 · August 26, 2020, 3:59pm

how this thing is giving us the distance that we require.Anybody please, i m not able to digest it…

prmondal · August 29, 2020, 4:13pm

@psychik Can you explain?

psychik · August 29, 2020, 4:18pm

“(parity[node] == prty)” is a boolean statement whose value will be either 0 or 1. You can also use if-else statement.

prmondal · August 29, 2020, 6:39pm

I guess we are asking here for explanation why these two lines added? Can you explain the logic?

hmmidkwhat · August 30, 2020, 5:28pm

@psychik Please explain what parity is first before you start using said parity

psychik · August 30, 2020, 5:40pm

Actually I mentioned it in the first line of Explanation that it is just used to refer the nodes of two disjoint set of bipartite graph parity0 and parity1. Nothing specific and If its confusing then consider that I root the tree at node 1 and referring to the node with even depth(or distance from node 1) with parity0 and to the node with odd depth with parity1

hmmidkwhat · August 30, 2020, 5:43pm

I got it while looking at the parity assignment function. Thanks anyway

darklord_chef · August 31, 2020, 6:43am

the second Type2 should be Type1

popeye12 · September 4, 2020, 9:27am

could you please explain again? why are we doing for i=0 && i=1 dfs.
since ,it’s already mentioned that 0 is red and 1=blue.

anon41069019 · September 29, 2020, 12:00am

we are given a tree, what i did is i ran dfs taking node 1 as root. and then checked whether the current node is ok or not, (it is ok it its parity is different that its parent), i calculated all invalid nodes with wrong parities, and now i have two types of nodes with wrong parity,

node with parity 1, but they must be 0
node with parity 0, but they must be 1

so i took two values for each node (is it a wrong node of type 1, is it a wrong node of type 2).
no matter at which position my tree is rooted the shortest path between a type1 and type2 node will go from their LCAs (right?), so i can just push all the wrong node up the tree in one operation and my answer should be number of time i swapped a wrong node with its parent.

so basically i am keeping two values for each node, and then i am starting to traverse node from the bottom of the tree, and pushing my nodes up the tree. and i will stop pushing certain node when ever it meet with the node of other type.

but this approach gives WA. i am unable to reason why?
https://www.codechef.com/viewsolution/38311762