Tree and Constraints

AtCoder

IDabc152_f

Time4000ms

Memory256MB

Difficulty—

We have a tree with $N$ vertices numbered $1$ to $N$. The $i$\-th edge in this tree connects Vertex $a_i$ and Vertex $b_i$. Consider painting each of these edges white or black. There are $2^{N-1}$ such ways to paint the edges. Among them, how many satisfy all of the following $M$ restrictions? * The $i$\-th $(1 \leq i \leq M)$ restriction is represented by two integers $u_i$ and $v_i$, which mean that the path connecting Vertex $u_i$ and Vertex $v_i$ must contain at least one edge painted black. ## Constraints * $2 \leq N \leq 50$ * $1 \leq a_i,b_i \leq N$ * The graph given in input is a tree. * $1 \leq M \leq \min(20,\frac{N(N-1)}{2})$ * $1 \leq u_i < v_i \leq N$ * If $i \not= j$, either $u_i \not=u_j$ or $v_i\not=v_j$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $b_1$ $:$ $a_{N-1}$ $b_{N-1}$ $M$ $u_1$ $v_1$ $:$ $u_M$ $v_M$ [samples]

Samples

Input #1

Output #1

3

The tree in this input is shown below:  
  
![image](https://img.atcoder.jp/ghi/5b0208ab1e3bb39a5d4fb7bafbfc448e.png)  
  
All of the $M$ restrictions will be satisfied if Edge $1$ and $2$ are respectively painted (white, black), (black, white), or (black, black), so the answer is $3$.

Input #2

Output #2

1

The tree in this input is shown below:  
  
![image](https://img.atcoder.jp/ghi/d08b3f53dfa4857fe9ffe13fa5d7ae69.png)  
  
All of the $M$ restrictions will be satisfied only if Edge $1$ is painted black, so the answer is $1$.

Input #3

Output #3

9

The tree in this input is shown below:  
  
![image](https://img.atcoder.jp/ghi/386502bb3c85e0bb5aee64e4e7c087a1.png)

Input #4

Output #4

62

The tree in this input is shown below:  
  
![image](https://img.atcoder.jp/ghi/955fa8fd8af658abb24ff2f68b9997be.png)

API Response (JSON)

{
  "problem": {
    "name": "Tree and Constraints",
    "description": {
      "content": "We have a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge in this tree connects Vertex $a_i$ and Vertex $b_i$.   Consider painting each of these edges white or black. There are $2^{N-1}$ ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc152_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge in this tree connects Vertex $a_i$ and Vertex $b_i$.  \nConsider painting each of these edges white or black. There are $2^{N-1}$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments