← 返回题目列表

AtCoder · arc198_d

D. 树上有许多回文

中文机器翻译题面 查看原题

分数: 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