配点 : 100 点
小心地将树嵌入加权完整图中,注意将计算量乘以常数。
問題文
N 给出一棵顶点树。在顶部 它的编号为 1, 2, \ldots, N 。i 番目 (1 \le i \le N - 1) 边是顶点 连接 A_i 和顶点 这意味着 B_i 。
另外,N \times N 非负整数 给出 C(x,y) (1 \le x, y \le N).这是 C(x,y) = C(y,x) 很满意。
(1, 2, \ldots, N) 的排列 在 p = (p(1), p(2), \ldots, p(N)) , 定义p 的成本 定义为在 \displaystyle\sum_{i=1}^{N-1} C(p(A_i), p(B_i)) 。成本的最小可能值和最小化成本的排列 查找 p 的编号。 问题句子中的树由
制約
- 1 \le N \le 18.
- 1 \le A_i < B_i \le N (1 \le i \le N - 1).
- A_i, B_i 确定。
- 0 \le C(x,y) \le 10^7 (1 \le x, y \le N).
- C(x,x) = 0 (1 \le x \le N).
- C(x,y) = C(y,x) (1 \le x, y \le N).
入力
输入将以以下格式从标准输入给出。
N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}
C(1,1) C(1,2) \cdots C(1,N)
C(2,1) C(2,2) \cdots C(2,N)
\vdots
C(N,1) C(N,2) \cdots C(N,N)
出力
成本的最小可能值和最小化成本的排列 输出以空格分隔的 p 的数量。
入力例 1
5 1 2 1 3 2 4 2 5 0 7 9 5 7 7 0 9 9 6 9 9 0 5 9 5 9 5 0 9 7 6 9 9 0
出力例 1
24 2
最低成本是 24 并实现它 p 是 (4, 1, 3, 2, 5) 和 (4, 1, 3, 5, 2) 的 2 。 当
例如 p = (4, 1, 3, 2, 5) 时,成本为 C(4, 1) + C(4, 3) + C(1, 2) + C(1, 5) = 5 + 5 + 7 + 7 = 24 变为。
入力例 2
7 1 2 2 3 1 4 4 5 1 6 6 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10000000 0 0 0 0 0 0 10000000 0 0 0 0 10000000 10000000 0
出力例 2
0 2448