D - Many Palindromes on Tree

コンテスト時間: 2025-05-25 21:00:00+0900 ~ 2025-05-25 23:00:00+0900 (120分) AtCoderホームへ戻る

D - Many Palindromes on Tree 解説

実行時間制限: 5 sec / メモリ制限: 1024 MiB

配点 : 700 点

問題文

頂点に 1 から N の番号がついた N 頂点の木 T と N \times N 行列 A = (A_{i,j}) が与えられます。T の i 本目の辺は頂点 U_i と頂点 V_i を結ぶ辺です。また、A の成分は 0 または 1 です。

整数列 x=(x_1,x_2,\dots,x_N) のスコアを以下のように定義します。

頂点の組 (i,j)(1 \le i,j \le N) に対して、T における i から j への単純パスが通る頂点を v_1=i,v_2,\dots,v_n=j とする(T は木なので、単純パスが一意に定まる)。(i,j) が回文ペアであるとは、任意の k(1 \le k \le n) について、x_{v_k} = x_{v_{n+1-k}} が成り立つことと定義する。
A_{i,j} = 1 かつ (i,j) が回文ペアでないような (i,j) が存在するとき、x のスコアは 10^{100} とする。
そのような (i,j) が存在しないとき、x のスコアは 1 \le i,j \le N かつ (i,j) が回文ペアであるような (i,j) の個数とする。

全ての整数列 x に対する、スコアの最小値を求めてください。

制約

1 \le N \le 3000
1 \le U_i,V_i \le N
T は木である。
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 1
A_{i,j} = A_{j,i}

入力

入力は以下の形式で標準入力から与えられる。

N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

出力

全ての整数列 x に対する、スコアの最小値を出力せよ。

入力例 1

出力例 1

例えば x = (1,2,4,2) のとき、A_{i,j} = 1 かつ (i,j) が回文ペアでないような (i,j) は存在しません。また、(i,j) が回文ペアであるようなものは (1,1),(2,2),(3,3),(4,4),(2,4),(4,2) の 6 個なので、スコアは 6 です。

他にも x = (1,2,3,4) のとき、(i,j) = (2,4) について A_{2,4} = 1 ですが、(2,4) が回文ペアでないためスコアは 10^{100} です。

入力例 2

出力例 2

入力例 3

出力例 3

Score : 700 points

Problem Statement

You are given a tree T with N vertices numbered 1 through N, and an N \times N matrix A = (A_{i,j}). The i-th edge of T connects vertices U_i and V_i. Each entry of A is 0 or 1.

Define the score of an integer sequence x=(x_1,x_2,\dots,x_N) as follows:

For a vertex pair (i,j)(1 \le i,j \le N), let the simple path in T from i to j be v_1=i,v_2,\dots,v_n=j (this path is unique since T is a tree). The pair (i,j) is called a palindromic pair if x_{v_k} = x_{v_{n+1-k}} for every k(1 \le k \le n).
If there exists a pair (i,j) such that A_{i,j} = 1 and (i,j) is not a palindromic pair, then the score of x is 10^{100}.
Otherwise, the score of x is the number of pairs (i,j) such that 1 \le i,j \le N and (i,j) is a palindromic pair.

Find the minimum score over all integer sequences x.

Constraints

1 \le N \le 3000
1 \le U_i,V_i \le N
T is a tree.
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 1
A_{i,j} = A_{j,i}

Input

The input is given from Standard Input in the following format:

N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Output the minimum score over all integer sequences x.

Sample Input 1

Sample Output 1

For example, when x = (1,2,4,2), there is no pair (i,j) such that A_{i,j}=1 and (i,j) is not a palindromic pair. The palindromic pairs are (1,1),(2,2),(3,3),(4,4),(2,4),(4,2), so the score is 6.

On the other hand, when x = (1,2,3,4), we have A_{2,4} = 1 while (2,4) is not a palindromic pair, so the score is 10^{100}.

Sample Input 2

Sample Output 2

Sample Input 3

問題文

制約

入力

出力