#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/6/problems/f

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/6/problems/f

Repovive

DFS Good Pairs - Repovive Premier Round 3 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

6F. DFS Good Pairs

3000 ptstype :zen to enter zen mode

by Amirali Asgari

Time: 2sMemory: 256 MB

Page 1

Consider a fixed vertex $i$ .

In a DFS preorder, the ancestors of $i$ must appear before $i$ . Besides them, the only other vertices that may appear before $i$ are complete subtrees branching out from the path from the root to $i$ .

More precisely, let the path from the root to $i$ be

$1 = p_0, p_1, \ldots, p_d = i$ .

For every vertex $p_r$ on this path, except $i$ itself, we may choose some children of $p_r$ that are not on the path to $i$ . If such a child is chosen, its whole subtree appears before $i$ .

Therefore, before reaching $i$ , we see:

all $d$ ancestors of $i$ ,
plus some complete side subtrees.

So if vertex $i$ is the $i$ -th vertex in the DFS order, the total number of vertices taken from side subtrees must be

$k_i = i - 1 - depth_i$ .

If $k_i < 0$ , vertex $i$ can never be placed in position $i$ .