分数: 700 点
问题陈述
你得到一棵树 T 与 N 顶点编号 1 通过 N,以及 N \times N 矩阵 A = (A_{i,j})。的 团队的 i第边缘 T 连接顶点 U_i 和 V_i。每个条目的 A is 0 or 1.
定义 整数序列的 分数 整数序列的 x=(x_1,x_2,\dots,x_N) 如下:
- 对于顶点对 (i,j)(1 \le i,j \le N),让简单路径进入 T 来自 i to j be v_1=i,v_2,\dots,v_n=j (这条路径是唯一的,因为 T 是一棵树)。这对 (i,j) 被称为 回文对 if x_{v_k} = x_{v_{n+1-k}} 对于每个 k(1 \le k \le n).
- 如果存在一对 (i,j) 这样 A_{i,j} = 1 和 (i,j) 不是回文对,则分数为 x is 10^{100}.
- 否则,得分为 x 是对数 (i,j) 这样 1 \le i,j \le N 和 (i,j) 是回文对。
找到所有整数序列的最小分数 x.
约束
- 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}
输入
输入由标准输入按以下格式给出:
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
4 1 2 1 3 1 4 1000 0101 0010 0101
示例输出 1
6
例如,当 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.
另一方面,当 x = (1,2,3,4),我们有 A_{2,4} = 1 同时 (2,4) 不是回文对,所以分数是 10^{100}.
示例输入 2
7 7 2 4 1 6 5 1 6 3 4 2 3 1001000 0100000 0010000 1001001 0000100 0000010 0001001
示例输出 2
13
示例输入 3
10 7 5 10 3 7 6 6 10 8 3 9 3 5 4 1 5 2 10 1000000000 0100010000 0010010100 0001000000 0000100100 0110010000 0000001001 0010100110 0000000110 0000001001
示例输出 3
66