CF1009F Dominant Indices

You are given a rooted undirected tree consisting of $ n $ vertices. Vertex $ 1 $ is the root. Let's denote a depth array of vertex $ x $ as an infinite sequence $ [d_{x, 0}, d_{x, 1}, d_{x, 2}, \dots] $ , where $ d_{x, i} $ is the number of vertices $ y $ such that both conditions hold: - $ x $ is an ancestor of $ y $ ; - the simple path from $ x $ to $ y $ traverses exactly $ i $ edges. The dominant index of a depth array of vertex $ x $ (or, shortly, the dominant index of vertex $ x $ ) is an index $ j $ such that: - for every $ k < j $ , $ d_{x, k} < d_{x, j} $ ; - for every $ k > j $ , $ d_{x, k} \le d_{x, j} $ . For every vertex in the tree calculate its dominant index.

N/A

N/A