← 返回题目列表

AtCoder · xmascon24_e

E. 嵌入树

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

配点 : 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