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 翻译