Sort the Leaves

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
You are given a binary tree with $N$ vertices numbered $1$ through $N$. The root of the tree is vertex $1$. There are two types of vertices:  nonleaf: has exactly two sons — a left son and a right son  leaf: doesn't have sons, but it has an integer *value* Let's denote the number of leaves by $L$. It is guaranteed that the values of all leaves are pairwise distinct numbers between $1$ and $L$ inclusive. To each leaf, we can assign a string in the following way:  consider the simple path $1=v_1, v_2, \dots, v_l$ from the root to leaf $v_l$  the string $S_{v_l}$ assigned to leaf $v_l$ has length $l1$; for each valid $i$, $S_i$ is 'L' if $v_{i+1}$ is the left son of $v_i$ or 'R' if it's the right son of $v_i$ It's clear that these strings are all pairwise distinct. Let's call the tree *leafsorted* if the following property holds for every pair of different leaves $a, b$: $S_a$ is lexicographically smaller than $S_b$ if and only if the value of $a$ is smaller than the value of $b$. You are allowed to perform the following operation an arbitrary number of times (including zero): choose a nonleaf vertex and swap the edges to its left and right son. That is, the original left son of this vertex becomes the right son and the original right son becomes the left son (along with their whole subtrees). Find the minimum number of operations needed to make the tree leafsorted, or determine that it's impossible. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains two spaceseparated integers $l$ and $r$. If $l = 1$, vertex $i$ is a leaf with value $r$. Otherwise, $l$ and $r$ respectively denote the left and right son of vertex $i$. ### Output For each test case, print a single line containing one integer — the minimum required number of operations or $1$ if it's impossible to make the tree leafsorted. ### Constraints  $1 \le T \le 1,000$  $2 \le N \le 10^5$  $1 \le r \le L$ for each leaf ($l = 1$)  $1 \le l, r \le N$ for each nonleaf  the values of all leaves are pairwise distinct  the graph described on the input is a binary tree rooted at vertex $1$  the sum of $N$ for all test cases does not exceed $2 \cdot 10^5$ ### Subtasks **Subtask #1 (30 points):**  $1 \le T \le 100$  $2 \le N \le 30$ **Subtask #2 (20 points):**  $1 \le T \le 100$  $2 \le N \le 1,000$  the sum of $N$ for all test cases does not exceed $2,000$ **Subtask #3 (50 points):** original constraints ### Example Input ``` 2 5 3 5 1 2 2 4 1 3 1 1 7 2 3 4 5 6 7 1 1 1 4 1 3 1 2 ``` ### Example Output ``` 1 1 ``` ### Explanation **Example case 1:** The leaves of this tree are vertices $2, 4, 5$, the strings assigned to them are "LL", "LR", "R" and their values are $2, 3, 1$. The strings are in increasing order and the corresponding values are not, so the tree isn't leafsorted. However, if we swap the left and right son of the root (vertex $1$), the strings assigned to the vertices become "RL, "RR", "L", so the tree becomes leafsorted.Author:  isaf27 
Editorial  https://discuss.codechef.com/problems/TREESORT 
Tags  bottomup, dfs, easymedium, greedy, isaf27, isaf27, likecs, ltime61 
Date Added:  23062018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 