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

$ curl repovive.com/contests/1/problems/d

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

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

$ curl repovive.com/contests/1/problems/d

Repovive

DFS Order Counting - Repovive Goodbye 2025 Round | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

1D. DFS Order Counting

2000 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Hint 1

Consider a graph that is already nice, and run a DFS that discovers vertices in the order $1,2,\dots,n$ (with some suitable adjacency-list order).

Look at the DFS tree and focus on vertex $1$ . Suppose its children in the DFS tree are $v_1, v_2, \dots, v_t$ in the order they are first visited.

A crucial property is that each child subtree forms a contiguous interval in the DFS order: the vertices in the subtree of $v_j$ are exactly $[L_j, R_j]$ for some $L_j \le R_j$ , and these intervals partition $[2,n]$ .

Two key facts follow:

(No edges between different child intervals)
If $u \in [L_i, R_i]$ and $v \in [L_j, R_j]$ with $i \ne j$ , then there is no edge $(u,v)$ in a nice graph.
Reason: while DFS is exploring one child interval, all vertices of other intervals are still unvisited, so any such edge would let DFS jump to another interval and break the discovery order.
(The parent connects to the start of each interval)
For every child interval $[L_j, R_j]$ , vertex $1$ must be connected to its first vertex $L_j$ by a DFS-tree edge, i.e. $(1, L_j)$ must exist (and be kept).
Otherwise DFS could not enter that interval starting at $L_j$ .

Consider a graph that is already nice, and run a DFS that discovers vertices in the order $1,2,\dots,n$ (with some suitable adjacency-list order).

Look at the DFS tree and focus on vertex $1$ . Suppose its children in the DFS tree are $v_1, v_2, \dots, v_t$ in the order they are first visited.

Two key facts follow:

(No edges between different child intervals)
If $u \in [L_i, R_i]$ and $v \in [L_j, R_j]$ with $i \ne j$ , then there is no edge $(u,v)$ in a nice graph.
Reason: while DFS is exploring one child interval, all vertices of other intervals are still unvisited, so any such edge would let DFS jump to another interval and break the discovery order.
(The parent connects to the start of each interval)
For every child interval $[L_j, R_j]$ , vertex $1$ must be connected to its first vertex $L_j$ by a DFS-tree edge, i.e. $(1, L_j)$ must exist (and be kept).
Otherwise DFS could not enter that interval starting at $L_j$ .