Shrink the Tree

AtCoder

IDwtf22_day1_c

Time5000ms

Memory256MB

Difficulty—

You are given a tree $T$ with $N$ vertices numbered $1$ to $N$. The $i$\-th edge connects vertices $A_i$ and $B_i$. You can perform the following operation any number of times, possibly zero. * Choose two leaves $u$ and $v$ of $T$ such that the distance between them is odd. Then, remove $u$ and $v$ from $T$ (along with the incident edges). Here, a vertex is said to be a leaf when its degree is exactly one at the time of the operation. The distance between two vertices is the number of edges in the path connecting those vertices. Find the number, modulo $998244353$, of sets that can be the vertex set of $T$ after your operations. ## Constraints * $2 \leq N \leq 150$ * $1 \leq A_i,B_i \leq N$ * The input graph is a tree. * All input values are integers. ## Input The input is given from Standard Input in the following format: $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_{N-1}$ $B_{N-1}$ [samples]

Samples

Input #1

Output #1

3

Performing zero operations yields the vertex set ${1,2,3,4}$.
Erasing the leaves $1$ and $4$ from $T$ yields the vertex set ${2,3}$.
From this state, erasing the leaves $2$ and $3$ yields the vertex set ${}$.

Input #2

Output #2

Input #3

Output #3

Input #4

Output #4

API Response (JSON)

{
  "problem": {
    "name": "Shrink the Tree",
    "description": {
      "content": "You are given a tree $T$ with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects vertices $A_i$ and $B_i$. You can perform the following operation any number of times, possibly zero. *   Cho",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "wtf22_day1_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a tree $T$ with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge connects vertices $A_i$ and $B_i$.\nYou can perform the following operation any number of times, possibly zero.\n\n*   Cho...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments