i was reading the tutorial for problem E from this round↵
https://codeforces.com/blog/entry/125943↵
↵
and it says that "And as it is known, the number of edges in the compressed tree is O(k)"↵
↵
i couldnt find anything about it on the internet does anyone have a proof on why we have O(k) edges in a compressed tree ?↵
↵
↵
↵
edit : i realized how stupid i was asking this question since we can have atmost 2k — 1 vertices in a compressed tree (where k is the number of important vertices in the main tree) there can be at most 2k — 2 edges since a tree will always have n — 1 edges↵
https://codeforces.com/blog/entry/125943↵
↵
and it says that "And as it is known, the number of edges in the compressed tree is O(k)"↵
↵
i couldnt find anything about it on the internet does anyone have a proof on why we have O(k) edges in a compressed tree ?↵
↵
↵
↵
edit : i realized how stupid i was asking this question since we can have atmost 2k — 1 vertices in a compressed tree (where k is the number of important vertices in the main tree) there can be at most 2k — 2 edges since a tree will always have n — 1 edges↵
