AT_arc198_d.[ARC198D] Many Palindromes on Tree

给定一棵具有 $ N $ 个顶点的树 $ T $，顶点编号为 $ 1 $ 至 $ N $，以及一个 $ 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 $ 是树，所以简单路径唯一）。如果对于所有 $ k $（$ 1 \le k \le n $），都有 $ x_{v_k} = x_{v_{n+1-k}} $，则称 $ (i,j) $ 为回文对。
• 如果存在 $ (i,j) $ 满足 $ A_{i,j} = 1 $ 且 $ (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 $ 的分数的最小值。

约束条件

• $ 1 \le N \le 3000 $
• $ 1 \le U_i, V_i \le N $
• $ T $ 是一棵树。
• $ A_{i,j} \in {0,1} $
• $ A_{i,i} = 1 $
• $ A_{i,j} = A_{j,i} $

样例解释 #1

例如，当 $ x = (1,2,4,2) $ 时，不存在 $ (i,j) $ 满足 $ A_{i,j} = 1 $ 且 $ (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} $。

翻译由 DeepSeek V3 完成