Beauty of Pairs

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME75/hindi/BOFP.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME75/bengali/BOFP.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME75/mandarin/BOFP.pdf), [Russian](http://www.codechef.com/download/translated/LTIME75/russian/BOFP.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME75/vietnamese/BOFP.pdf) as well. You are given a tree with $N$ vertices numbered 1 through $N$ as a sequence of $N1$ edges — pairs $(a_1, b_1), (a_2, b_2), \ldots, (a_{N1}, b_{N1})$. Let's define the *value* of a sequence $A$ with length $N1$ as $$F(A)=\sum_{i=1}^{N1} A_i \cdot W_i \,,$$ where $W_1, W_2, \ldots, W_{N1}$ are given weights. You may change the order of the pairs and the order of elements within any pairs. Formally, consider a *reordering* $(P, R)$ — any permutation $P = (P_1, P_2, \ldots, P_{N1})$ of the integers $1$ through $N1$ and any subset $R$ of these integers (possibly containing all of them). Let's define two sequences $C = (c_{P_1}, c_{P_2}, \ldots, c_{P_{N1}})$ and $D = (d_{P_1}, d_{P_2}, \ldots, d_{P_{N1}})$, where for each valid $i$, $c_i = a_i$ and $d_i = b_i$ if $i \not\in R$, or $c_i = b_i$ and $d_i = a_i$ if $i \in R$. If $D$ is **strictly** increasing, the reordering is *valid* and its value is $F(C)$. Find the maximum value of a valid reordering, i.e. the maximum $F(C)$, and the number of valid reorderings that have this maximum value. ### 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$.  The second line contains $N1$ spaceseparated integers $W_1, W_2, \ldots, W_{N1}$.  $N1$ lines follow. For each $i$ ($1 \le i \le N1$), the $i$th of these lines contains two spaceseparated integers $a_i$ and $b_i$. ### Output For each test case, print a single line containing two spaceseparated integers — the maximum value of a reordering and the number of reorderings with the maximum value. ### Constraints  $1 \le T \le 100$  $2 \le N \le 2 \cdot 10^5$  $W_i \le 10^4$ for each valid $i$  $1 \le a_i, b_i \le N$ for each valid $i$  pairs $(a_i, b_i)$ are edges of a tree  the sum of $N$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (50 points):**  $N \le 1,000$  the sum of $N$ over all test cases does not exceed $5,000$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 1 4 1 1 0 1 2 1 3 3 4 ``` ### Example Output ``` 4 2 ``` ### Explanation **Example case 1:** There are two valid orderings with value $4$:  $P = (2, 1, 3)$, $R = \{2, 3\}$; $C = (3, 1, 4)$ and $D = (1, 2, 3)$, so $F(C) = 3 \cdot 1 + 1 \cdot 1 + 4 \cdot 0 = 4$  $P = (2, 1, 3)$, $R = \{2\}$; $C = (3, 1, 3)$ and $D = (1, 2, 4)$, so $F(C) = 3 \cdot 1 + 1 \cdot 1 + 3 \cdot 0 = 4$Author:  farhod_farmon 
Editorial  https://discuss.codechef.com/problems/BOFP 
Tags  farhod_farmon, ltime75, mediumhard, observations, segmenttree, taran_1407 
Date Added:  20062019 
Time Limit:  2 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, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions