AT_xmascon24_e Embed the Tree

给定一棵有 $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$ 的个数。

输入以如下形式从标准输入读入。 > $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 代价的最小值为 $24$，能达到该代价的 $p$ 有 $2$ 个，分别为 $(4, 1, 3, 2, 5)$ 和 $(4, 1, 3, 5, 2)$。 例如当 $p = (4, 1, 3, 2, 5)$ 时，代价为 $C(4, 1) + C(4, 3) + C(1, 2) + C(1, 5) = 5 + 5 + 7 + 7 = 24$。 ### 数据范围 - $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$）。 由 ChatGPT 5 翻译