CF1527D MEX Tree

You are given a tree with $ n $ nodes, numerated from $ 0 $ to $ n-1 $ . For each $ k $ between $ 0 $ and $ n $ , inclusive, you have to count the number of unordered pairs $ (u,v) $ , $ u \neq v $ , such that the MEX of all the node labels in the shortest path from $ u $ to $ v $ (including end points) is $ k $ . The MEX of a sequence of integers is the smallest non-negative integer that does not belong to the sequence.

N/A

N/A

1. In example case $ 1 $ ,  - For $ k = 0 $ , there is $ 1 $ path that is from $ 2 $ to $ 3 $ as $ MEX([2, 3]) = 0 $ . - For $ k = 1 $ , there are $ 2 $ paths that is from $ 0 $ to $ 2 $ as $ MEX([0, 2]) = 1 $ and $ 0 $ to $ 3 $ as $ MEX([0, 2, 3]) = 1 $ . - For $ k = 2 $ , there is $ 1 $ path that is from $ 0 $ to $ 1 $ as $ MEX([0, 1]) = 2 $ . - For $ k = 3 $ , there is $ 1 $ path that is from $ 1 $ to $ 2 $ as $ MEX([1, 0, 2]) = 3 $ - For $ k = 4 $ , there is $ 1 $ path that is from $ 1 $ to $ 3 $ as $ MEX([1, 0, 2, 3]) = 4 $ . 2. In example case $ 2 $ ,  - For $ k = 0 $ , there are no such paths. - For $ k = 1 $ , there are no such paths. - For $ k = 2 $ , there is $ 1 $ path that is from $ 0 $ to $ 1 $ as $ MEX([0, 1]) = 2 $ .