AT_arc198_d [ARC198D] Many Palindromes on Tree

[problemUrl]: https://atcoder.jp/contests/arc198/tasks/arc198_d 给定一棵具有 $ 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 完成