Sticky Notes

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/DEC19/hindi/STICNOT.pdf), [Bengali](http://www.codechef.com/download/translated/DEC19/bengali/STICNOT.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/DEC19/mandarin/STICNOT.pdf), [Russian](http://www.codechef.com/download/translated/DEC19/russian/STICNOT.pdf), and [Vietnamese](http://www.codechef.com/download/translated/DEC19/vietnamese/STICNOT.pdf) as well. You are given a tree with $N$ vertices (numbered $1$ through $N$). Its edges are numbered $1$ through $N1$. For each valid $i$, there is an integer $a_i$ written on the $i$th vertex. Also, for each valid $i$, there is an integer $b_i$ written on the $i$th edge. You want the following condition to be satisfied: for each vertex $v$ and each edge $e$ adjacent to $v$, $a_v \ge b_e$. In order to achieve that, you may perform an arbitrary number of steps (including zero). In one step, you may perform one the following operations: 1. Select two different vertices $u$ and $v$. Swap $a_u$ and $a_v$. 2. Select two different edges $e$ and $f$. Swap $b_e$ and $b_f$. 3. Select a vertex $v$ and an integer $x$. Change $a_v$ to $x$ and pay one coin. Calculate the minimum number of coins you need in order to satisfy the required condition. ### 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$.  $N1$ lines follow. For each $i$ ($1 \le i \le N1$), the $i$th of these lines contains three spaceseparated integers $u_i$, $v_i$ and $b_i$ denoting that the $i$th edge connects vertices $u_i$ and $v_i$ and the initial value written on it is $b_i$.  The last line contains $N$ spaceseparated integers $a_1, a_2, \ldots, a_N$. ### Output For each test case, print a single line containing one integer ― the minimum necessary number of coins. ### Constraints  $1 \le T \le 10$  $2 \le N \le 100,000$  $1 \le u_i, v_i \le N$ for each valid $i$  $1 \le b_i \le 10^9$ for each valid $i$  $1 \le a_i \le 10^9$ for each valid $i$  the graph on the input is a tree ### Subtasks **Subtask #1 (10 points):** $N \le 7$ **Subtask #2 (10 points):** $N \le 10$ **Subtask #3 (30 points):** $N \le 200$ **Subtask #4 (50 points):** original constraints ### Example Input ``` 1 3 1 2 4 2 3 7 1 5 10 ``` ### Example Output ``` 1 ``` ### Explanation **Example case 1:** There is no way to satisfy the required condition without paying any coins. When we have one coin, we can perform the following operations:  Swap the integers written on vertices $1$ and $2$.  Pay one coin and change the integer written on vertex $2$ to $7$.Author:  saboon 
Editorial  https://discuss.codechef.com/problems/STICNOT 
Tags  binarysearch, dec19, greedy, medium, melfice, saboon, tree 
Date Added:  21102019 
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, SQL, 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