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

$ curl repovive.com/contests/3/problems/e

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

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

$ curl repovive.com/contests/3/problems/e

Repovive

Different Distances - Repovive Premier Round 2 | Repovive | Repovive

Back

Code

Upload

Submissions

Problem

3E. Different Distances

2500 ptstype :zen to enter zen mode

Time: 2sMemory: 256 MB

Page 1

A useful parity fact is the following. If $dist(u,v)$ is odd, then for every vertex $x$ we always have $dist(u,x)\ne dist(v,x)$ , because $dist(u,x)$ and $dist(v,x)$ have opposite parity. So pairs at odd distance never cause trouble.

The only problematic pairs are those with even distance. For such a pair $(u,v)$ , let $m$ be the unique midpoint of the path from $u$ to $v$ . Then $dist(u,x)=dist(v,x)$ holds exactly for those $x$ whose path to $u$ and $v$ meets at $m$ , i.e. for vertices that lie outside the two components of $T\setminus\{m\}$ that contain $u$ and $v$ . Therefore, the pair $(u,v)$ is not distinguished by $S$ iff $S$ avoids both of these two components.