problem link: https://open.kattis.com/problems/animal
I solved this problem a few hours ago by following the “editorial” and using recursive parser, sorting and binary search Here is the link which contains a solution to the problem: https://www.comp.nus.edu.sg/~acmicpc/rcdreport-preliminarycontest.pdf (go to the “Animal Classification problem part”).
I don’t understand a particular analysis in the solution. In the link, the editorialist explains that two subtrees from two different trees share exactly the same set of leaves if their set of leaves have the same sum, minimum, maximum and number of leaves (size). Of course, this is limited to the context of the problem which describes the both trees to have leaf labels 1 to N with no repeating labels.
I made a counterexample as it didn’t seem too hard to make.
8 (((1,8),(6,4)),((2,3),(7,5))) (((1,8),(7,3)),((2,4),(6,5)))
The subtrees ((1,8),(6,4)) and ((1,8),(7,3)) have the same sum (i.e. 19), minimum (i.e. 1), maximum (i.e. 8), and number of leaves (i.e. 4). But they clearly do not have the same set of leaves.
Can anyone explain this?