Many Palindromes on Tree

AtCoder

IDarc198_d

Time5000ms

Memory256MB

Difficulty—

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}$ [samples]

Samples

Input #1

Output #1

6

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}$.

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Many Palindromes on Tree",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc198_d"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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 ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments