Game of Theory

All submissions for this problem are available.
Tyrion is learning game theory to impress the queen.Lord Varys wanted to test the learning of Tyrion so he presented him with a problem on minmax. Help Tyrion in solving the problem. Given a tree with $N$ nodes rooted at node $1$. Each node ($U$) of the tree is associated with a pair of values $(A_U, B_U)$. You need to find the value of result ($R$). $ \\ R \qquad = \qquad \displaystyle\sum\limits_{U=1}^{N}\displaystyle\sum\limits_{V=1}^{N} F(U, V) \\ $ $ F(U,V) = \left\{\begin{matrix} MIN( MAX(A_U, A_V), MAX(B_U, B_V) ) & if\, V\, lies\, in\, subtree\, of\, U \\ 0 & otherwise \end{matrix}\right. $ ###Input:  First line will contain one integer $N$ denoting number of nodes in the tree.  Second line will contain $N$ space separated integers $A_1, A_2, A_3 ...... A_N$.  Third line will contain $N$ space separated integers $B_1, B_2, B_3 ...... B_N$.  Each of the next $N  1$ lines will contain 2 space separated integers $U$ and $V$ denoting that there is an edge between node $U$ and $V$. ###Output: Output in a single line value of result $R$. ###Constraints  $1 \leq N \leq 10^5$  $1 \leq A[i], B[i] \leq 10^9$  $1 \leq U, V \leq N$  $U \ne V$ ###Sample Input: ``` 5 1 4 5 2 3 5 2 4 1 3 1 2 1 3 2 4 2 5 ``` ###Sample Output: ``` 30 ``` ###EXPLANATION: $F(1, 1) = MIN(MAX(A_1, A_1), MAX(B_1, B_1)) = 1$ $F(1, 2) = MIN(MAX(A_1, A_2), MAX(B_1, B_2)) = 4$ $F(1, 3) = MIN(MAX(A_1, A_3), MAX(B_1, B_3)) = 5$ $F(1, 4) = MIN(MAX(A_1, A_4), MAX(B_1, B_4)) = 2$ $F(1, 5) = MIN(MAX(A_1, A_5), MAX(B_1, B_5)) = 3$ $F(2, 2) = MIN(MAX(A_2, A_2), MAX(B_2, B_2)) = 2$ $F(2, 4) = MIN(MAX(A_2, A_4), MAX(B_2, B_4)) = 2$ $F(2, 5) = MIN(MAX(A_2, A_5), MAX(B_2, B_5)) = 3$ $F(3, 3) = MIN(MAX(A_3, A_3), MAX(B_3, B_3)) = 4$ $F(4, 4) = MIN(MAX(A_4, A_4), MAX(B_4, B_4)) = 1$ $F(5, 5) = MIN(MAX(A_5, A_5), MAX(B_5, B_5)) = 3$ Rest of $F(U, V)$ which are not listed above have value $0$. $R$ = 1 + 4 + 5 + 2 + 3 + 2 + 2 + 3 + 4 + 1 + 3 = 30 Hence the result is 30.Author:  aashu_k 
Tags  aashu_k 
Date Added:  31032019 
Time Limit:  3.5 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
HELP
If you are still having problems, see a sample solution here. 