codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2218F.md (2752B)


      1 Source: https://codeforces.com/problemset/problem/2218/F
      2 
      3 F. The 67th Tree Problem
      4 
      5 time limit per test
      6 
      7 4 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Now that PMOI season is over (Cloud emerged victorious), Macaque can continue on his journey towards enlightenment. The problems he is to solve are getting harder, the burden of the past lives is getting heavier, and you are losing your free will at such a rate that you struggle to remember the last time you did anything out of your own volition without being coerced by Macaque. The only upside for you is that Macaque is giving you a free tour of his current habitat up in the trees once you solve the following problem for him.
     22 
     23 You are given two integers $x$ and $y$.
     24 
     25 Your task is to construct a tree with $x + y$ nodes, rooted at node $1$, such that:
     26 
     27 * Exactly $x$ nodes in the tree have even subtree$^{\text{∗}}$ size.
     28 * Exactly $y$ nodes in the tree have odd subtree size.
     29 
     30 If multiple valid trees exist, you may output any of them. If there is no such tree, output NO.
     31 
     32 $^{\text{∗}}$The subtree of a vertex $u$ is the set of all vertices that pass through $u$ on a simple path to the root (including $u$ itself).
     33 
     34 Input
     35 
     36 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     37 
     38 Each subsequent line contains two integers $x$ and $y$ ($0 \leq x, y \leq 2 \cdot 10^5$, $1 \leq x + y \leq 2 \cdot 10^5$).
     39 
     40 It is guaranteed that the sum of $x+y$ over all test cases does not exceed $2\cdot 10^5$.
     41 
     42 Output
     43 
     44 For each query, output "YES" or "NO", depending on whether or not a construction exists. You can output "YES" and "NO" in any case (for example, "yES", "yes", and "Yes" will be recognized as a positive response).
     45 
     46 If you output "YES", output $x+y-1$ lines, each containing two space-separated integers $u$ and $v$, denoting that there is an edge between nodes $u$ and $v$.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 7
     54 
     55 1 1
     56 
     57 2 1
     58 
     59 0 3
     60 
     61 3 4
     62 
     63 0 2
     64 
     65 1 0
     66 
     67 4 7
     68 ```
     69 
     70 Output
     71 
     72 ```
     73 YES
     74 1 2
     75 NO
     76 YES
     77 1 2
     78 1 3
     79 YES
     80 1 2
     81 2 3
     82 3 4
     83 4 5
     84 5 6
     85 6 7
     86 NO
     87 NO
     88 YES
     89 1 2
     90 2 3
     91 3 4
     92 4 5
     93 4 11
     94 2 6
     95 6 7
     96 7 8
     97 2 9
     98 9 10
     99 ```
    100 
    101 Note
    102 
    103 In the first test, the output tree is valid because node $1$ has subtree size $2$, which is even, and node $2$ has subtree size $1$, which is odd.
    104 
    105 In the second test, it can be shown that no valid tree exists.
    106 
    107 In the fourth test, the nodes with even subtree size are $[2, 4, 6]$, and the nodes with odd subtree size are $[1, 3, 5, 7]$.
    108 
    109 The output of the final test is shown in the diagram below, where the blue nodes have even subtree size and the red nodes have odd subtree size.
    110 
    111  ![](https://espresso.codeforces.com/e76628e482920b31c69a3d4905a0ca4da059dc86.png)