Surrounded Nodes

AtCoder

IDabc149_f

Time2000ms

Memory256MB

Difficulty—

Given is a tree $T$ with $N$ vertices. The $i$\-th edge connects Vertex $A_i$ and $B_i$ ($1 \leq A_i,B_i \leq N$). Now, each vertex is painted black with probability $1/2$ and white with probability $1/2$, which is chosen independently from other vertices. Then, let $S$ be the smallest subtree (connected subgraph) of $T$ containing all the vertices painted black. (If no vertex is painted black, $S$ is the empty graph.) Let the _holeyness_ of $S$ be the number of white vertices contained in $S$. Find the expected holeyness of $S$. Since the answer is a rational number, we ask you to print it $\bmod 10^9+7$, as described in Notes. ## 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$ $:$ $A_{N-1}$ $B_{N-1}$ [samples] ## Notes When you print a rational number, first write it as a fraction $\frac{y}{x}$, where $x, y$ are integers, and $x$ is not divisible by $10^9 + 7$ (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer $z$ between $0$ and $10^9 + 6$, inclusive, that satisfies $xz \equiv y \pmod{10^9 + 7}$.

Samples

Input #1

3
1 2
2 3

Output #1

125000001

If the vertices $1, 2, 3$ are painted black, white, black, respectively, the holeyness of $S$ is $1$.
Otherwise, the holeyness is $0$, so the expected holeyness is $1/8$.
Since $8 \times 125000001 \equiv 1 \pmod{10^9+7}$, we should print $125000001$.

Input #2

Output #2

375000003

The expected holeyness is $3/8$.
Since $8 \times 375000003 \equiv 3 \pmod{10^9+7}$, we should print $375000003$.

Input #3

Output #3

250000002

The expected holeyness is $1/4$.

Input #4

Output #4

570312505

API Response (JSON)

{
  "problem": {
    "name": "Surrounded Nodes",
    "description": {
      "content": "Given is a tree $T$ with $N$ vertices. The $i$\\-th edge connects Vertex $A_i$ and $B_i$ ($1 \\leq A_i,B_i \\leq N$). Now, each vertex is painted black with probability $1/2$ and white with probability $",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc149_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Given is a tree $T$ with $N$ vertices. The $i$\\-th edge connects Vertex $A_i$ and $B_i$ ($1 \\leq A_i,B_i \\leq N$).\nNow, each vertex is painted black with probability $1/2$ and white with probability $...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments