Paint Tree

AtCoder

IDarc108_f

Time2000ms

Memory256MB

Difficulty—

Given is a tree with $N$ vertices numbered $1$ to $N$, and $N-1$ edges numbered $1$ to $N-1$. Edge $i$ connects Vertex $a_i$ and $b_i$ bidirectionally and has a length of $1$. Snuke will paint each vertex white or black. The _niceness_ of a way of painting the graph is $\max(X, Y)$, where $X$ is the maximum among the distances between white vertices, and $Y$ is the maximum among the distances between black vertices. Here, if there is no vertex of one color, we consider the maximum among the distances between vertices of that color to be $0$. There are $2^N$ ways of painting the graph. Compute the sum of the nicenesses of all those ways, modulo $(10^{9}+7)$. ## Constraints * $2 \leq N \leq 2 \times 10^{5}$ * $1 \leq a_i, b_i \leq N$ * The given graph is a tree. ## Input Input is given from Standard Input in the following format: $N$ $a_1$ $b_1$ $\vdots$ $a_{N-1}$ $b_{N-1}$ [samples]

Samples

Input #1

2
1 2

Output #1

2

*   If we paint Vertex $1$ and $2$ the same color, the niceness will be $1$; if we paint them different colors, the niceness will be $0$.
*   The sum of those nicenesses is $2$.

Input #2

Output #2

Input #3

Output #3

298219707

*   Be sure to compute the sum modulo $(10^{9}+7)$.

API Response (JSON)

{
  "problem": {
    "name": "Paint Tree",
    "description": {
      "content": "Given is a tree with $N$ vertices numbered $1$ to $N$, and $N-1$ edges numbered $1$ to $N-1$. Edge $i$ connects Vertex $a_i$ and $b_i$ bidirectionally and has a length of $1$. Snuke will paint each ve",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc108_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given is a tree with $N$ vertices numbered $1$ to $N$, and $N-1$ edges numbered $1$ to $N-1$. Edge $i$ connects Vertex $a_i$ and $b_i$ bidirectionally and has a length of $1$.\nSnuke will paint each ve...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments