AT_arc198_d [ARC198D] Many Palindromes on Tree

頂点に $ 1 $ から $ N $ の番号がついた $ N $ 頂点の木 $ T $ と $ N \times N $ 行列 $ A = (A_{i,j}) $ が与えられます。 $ T $ の $ i $ 本目の辺は頂点 $ U_i $ と頂点 $ V_i $ を結ぶ辺です。また、 $ A $ の成分は $ 0 $ または $ 1 $ です。 整数列 $ x=(x_1,x_2,\dots,x_N) $ の**スコア**を以下のように定義します。 - 頂点の組 $ (i,j)(1 \le i,j \le N) $ に対して、 $ T $ における $ i $ から $ j $ への単純パスが通る頂点を $ v_1=i,v_2,\dots,v_n=j $ とする( $ T $ は木なので、単純パスが一意に定まる)。 $ (i,j) $ が**回文ペア**であるとは、任意の $ k(1 \le k \le n) $ について、 $ x_{v_k} = x_{v_{n+1-k}} $ が成り立つことと定義する。 - $ A_{i,j} = 1 $ かつ $ (i,j) $ が回文ペアでないような $ (i,j) $ が存在するとき、 $ x $ のスコアは $ 10^{100} $ とする。 - そのような $ (i,j) $ が存在しないとき、 $ x $ のスコアは $ 1 \le i,j \le N $ かつ $ (i,j) $ が回文ペアであるような $ (i,j) $ の個数とする。 全ての整数列 $ x $ に対する、スコアの最小値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ 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} $

全ての整数列 $ x $ に対する、スコアの最小値を出力せよ。

### Sample Explanation 1 例えば $ x = (1,2,4,2) $ のとき、 $ A_{i,j} = 1 $ かつ $ (i,j) $ が回文ペアでないような $ (i,j) $ は存在しません。また、 $ (i,j) $ が回文ペアであるようなものは $ (1,1),(2,2),(3,3),(4,4),(2,4),(4,2) $ の $ 6 $ 個なので、スコアは $ 6 $ です。 他にも $ x = (1,2,3,4) $ のとき、 $ (i,j) = (2,4) $ について $ A_{2,4} = 1 $ ですが、 $ (2,4) $ が回文ペアでないためスコアは $ 10^{100} $ です。 ### Constraints - $ 1 \le N \le 3000 $ - $ 1 \le U_i,V_i \le N $ - $ T $ は木である。 - $ A_{i,j} \in \lbrace 0,1 \rbrace $ - $ A_{i,i} = 1 $ - $ A_{i,j} = A_{j,i} $