AT_arc198_d [ARC198D] Many Palindromes on Tree

You are given a tree $ T $ with $ N $ vertices numbered $ 1 $ through $ N $ , and an $ N \times N $ matrix $ A = (A_{i,j}) $ . The $ i $ -th edge of $ T $ connects vertices $ U_i $ and $ V_i $ . Each entry of $ A $ is $ 0 $ or $ 1 $ . Define the **score** of an integer sequence $ x=(x_1,x_2,\dots,x_N) $ as follows: - For a vertex pair $ (i,j)(1 \le i,j \le N) $ , let the simple path in $ T $ from $ i $ to $ j $ be $ v_1=i,v_2,\dots,v_n=j $ (this path is unique since $ T $ is a tree). The pair $ (i,j) $ is called a **palindromic pair** if $ x_{v_k} = x_{v_{n+1-k}} $ for every $ k(1 \le k \le n) $ . - If there exists a pair $ (i,j) $ such that $ A_{i,j} = 1 $ and $ (i,j) $ is not a palindromic pair, then the score of $ x $ is $ 10^{100} $ . - Otherwise, the score of $ x $ is the number of pairs $ (i,j) $ such that $ 1 \le i,j \le N $ and $ (i,j) $ is a palindromic pair. Find the minimum score over all integer sequences $ x $ .

The input is given from Standard Input in the following format: > $ N $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_{N-1} $ $ V_{N-1} $ $ A_{1,1}A_{1,2}\dots A_{1,N} $ $ A_{2,1}A_{2,2}\dots A_{2,N} $ $ \vdots $ $ A_{N,1}A_{N,2}\dots A_{N,N} $

Output the minimum score over all integer sequences $ x $ .

### Sample Explanation 1 For example, when $ x = (1,2,4,2) $ , there is no pair $ (i,j) $ such that $ A_{i,j}=1 $ and $ (i,j) $ is not a palindromic pair. The palindromic pairs are $ (1,1),(2,2),(3,3),(4,4),(2,4),(4,2) $ , so the score is $ 6 $ . On the other hand, when $ x = (1,2,3,4) $ , we have $ A_{2,4} = 1 $ while $ (2,4) $ is not a palindromic pair, so the score is $ 10^{100} $ . ### Constraints - $ 1 \le N \le 3000 $ - $ 1 \le U_i,V_i \le N $ - $ T $ is a tree. - $ A_{i,j} \in \lbrace 0,1 \rbrace $ - $ A_{i,i} = 1 $ - $ A_{i,j} = A_{j,i} $