EXPTREE codechef problem not able to understand the proof , please help !!

Revision en1, by shahianshu, 2018-10-22 19:19:51

Hello,

EXPTREE Problem link

i was reading the editorial for Exptree i was not able to understand the proof mentioned by @gil_vegliach in the commments, as he mentioned that for any two vertices v1 and v2 in [1..n] in tree T1 , T2 resp., if we remove (parent[v1],v1) and (parent[v2],v2) will lead to same tree only if T1 = T2 initially but i came up with a counter example of 7 nodes

(T1)                                           (T2)
               0                  and                           0
             /   \                                            /   \
           0      0                                          0     0
         /         \                                                \
   ( 0 )            0                                                 0
                  /   \                                             /  \
                 0     0                                            0    0
                                                                          \
                                                                          ( 0 )

v1 is the vertex marked with () in T1 and v2 is the vertex marked with () in T2 , now if i remove the edge between v1 and it's parent , and remove the edge between v2 and it's parent then i get the same tree but T1 != T2. Now i am not able to understand wheather the proof is wrong or i have understood it incorrectly

Tags #codechef, exptree, proof, #editorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English shahianshu 2018-10-22 19:19:51 1710 Initial revision (published)