E - Embed the Tree Editorial /

Time Limit: 4 sec / Memory Limit: 2048 MB

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