Problem:
 Score : 600 points    Problem Statement 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.      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} .      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}       Output Print the expected holeyness of S , \bmod 10^9+7 .        Sample Input 1 3
1 2
2 3      Sample 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 .       Sample Input 2 4
1 2
2 3
3 4      Sample Output 2 375000003  The expected holeyness is 3/8 .  Since 8 \times 375000003 \equiv 3 \pmod{10^9+7} , we should print 375000003 .       Sample Input 3 4
1 2
1 3
1 4      Sample Output 3 250000002  The expected holeyness is 1/4 .       Sample Input 4 7
4 7
3 1
2 6
5 2
7 1
2 7      Sample Output 4 570312505

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

    pow2 = [0] * (N + 1)
    pow2[0] = 1
    for i in range(N):
        pow2[i + 1] = pow2[i] * 2 % MOD

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - 1 - (pow2[N - nodes[v]] - 1)) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - (pow2[nodes[nv]] - 1)) % MOD

    denom = pow2[N]
    ans = (numer * pow(denom, MOD - 2, MOD)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def solve():
    N = int(input())
    AB = [tuple(map(int,input().split())) for i in range(N-1)]
    MOD = 10**9+7
    es = [[] for _ in range(N)]
    for a,b in AB:
        a,b = a-1,b-1
        es[a].append(b)
        es[b].append(a)

    cs = [1] * N
    def dfs(v,p=-1):
        ret = 1
        for to in es[v]:
            if to==p: continue
            ret += dfs(to,v)
        cs[v] = ret
        return ret
    dfs(0)

    pow2 = [1]
    for i in range(N):
        pow2.append((pow2[-1]*2) % MOD)

    ans = 0
    for i in range(N):
        if len(es[i]) == 1: continue
        ans += pow2[N-1] - 1
        c = 0
        for to in es[i]:
            if cs[to] > cs[i]: continue
            c += cs[to]
            ans -= pow2[cs[to]] - 1
        ans -= pow2[N-c-1] - 1

    ans *= pow(pow2[N], MOD-2, MOD)
    print(ans%MOD)
solve()

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] == 0:
			visit[i] = 1
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist.append(W[i])

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque(); self.Q.append(s)
		self.dist = [INF] * N; self.dist[s] = 0
		self.prev = [None] * N; self.prev[s] = -1
		self.order = []
		while self.Q:
			v = self.Q.popleft()
			self.order.append(v)
			for i in self.g[v]:
				if self.dist[i] == INF:
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.append(i)



def main():
	
	N = int(input())
	G = Graph()
	Nedge = [0] * N
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
		Nedge[a] += 1; Nedge[b] += 1

	W = [1] * N
	
	
	
	

	BF = BFS(G, 0, N)

	for i in range(N - 1, 0, -1):
		v = BF.order[i]
		W[BF.prev[v]] += W[v]

	Wlist = []
	for i in range(N):
		for j in G.graph[i]:
			if j != BF.prev[i]:
				Wlist.append(W[j])
	for i in range(N):
		Wlist.append(N - W[i])

	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= pow(2, i, con) - 1
		ans_up %= con

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

if __name__ == '__main__':
	main()

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
stack = []
root = -1
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == -1:
    root = i
deg[root] += 1
dp = [[] for i in range(n+1)]
num = [0]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    num[x] = sum(dp[x])+1
  else:
    num[x] = 1
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(num[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
for i in range(1,n+1):
  if num[i] != n:
    dp[i].append(n-num[i])
ans = 0
mod = 10**9+7
def inv(x):
  return pow(x,mod-2,mod)
inv2 = inv(2)
inv2n = inv(pow(2,n,mod))
for i in range(1,n+1):
  if len(dp[i]) > 1:
    ans += 1
    ans -= inv2
    ans += inv2n*(len(dp[i])-1)
    for val in dp[i]:
      ans -= pow(2,val,mod)*inv2n
      ans %= mod
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


n = ni()
G = [list() for _ in range(n)]
for _ in range(n-1):
  a, b = nm()
  a -= 1; b -= 1
  G[a].append(b)
  G[b].append(a)
  
  
mod = 10**9 + 7
dub = [1]*(n+1)
for i in range(n):
  dub[i+1] = dub[i] * 2
  if dub[i+1] > mod:
    dub[i+1] -= mod
    
size = [1]*n
def dfs_depandsize(tree,v,p):
    for x in tree[v]:
        if x == p:
            continue
        size[v] += dfs_depandsize(tree,x,v)
    return size[v]
dfs_depandsize(G, 0, -1)
ans = 0
for v in range(n):
  c = 0
  res = 1
  for x in G[v]:
    if size[x] < size[v]:
      c += size[x]
      res += dub[size[x]] - 1
  res += dub[n-1-c] - 1
  res %= mod
  ans = (ans + dub[n-1] - res) % mod
print(ans * pow(dub[n], mod-2, mod) % mod)

Solution (Python):
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


n = ni()
G = [list() for _ in range(n)]
for _ in range(n-1):
  a, b = nm()
  a -= 1; b -= 1
  G[a].append(b)
  G[b].append(a)
  
  
mod = 10**9 + 7
dub = [1]*(n+1)
for i in range(n):
  dub[i+1] = dub[i] * 2
  if dub[i+1] > mod:
    dub[i+1] -= mod
    
size = [-1]*n
q = [0]
while q:
  v = q[-1]
  if size[v] < 0:
    for x in G[v]:
      if size[x] < 0:
        q.append(x)
    size[v] = 0
  else:
    size[v] = 1
    for x in G[v]:
      size[v] += size[x]
    q.pop()

ans = 0
for v in range(n):
  c = 0
  res = 1
  for x in G[v]:
    if size[x] < size[v]:
      c += size[x]
      res += dub[size[x]] - 1
  res += dub[n-1-c] - 1
  res %= mod
  ans = (ans + dub[n-1] - res) % mod
print(ans * pow(dub[n], mod-2, mod) % mod)

Solution (Python):


import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  

def calc_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def solve(N: int, A: "List[int]", B: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(N - 1):
        conns[A[i] - 1].append(B[i] - 1)
        conns[B[i] - 1].append(A[i] - 1)

    pows = []
    for i in range(N + 1):
        pows.append(pow(2, i, MOD))

    num = [0]
    visited = [False] * N
    def dfs(idx):
        visited[idx] = True
        children = 0
        subs = []
        for c in conns[idx]:
            if visited[c]:
                continue
            sub = dfs(c)
            children += sub
            subs.append(sub)
        subs.append(N - children - 1)
        
        tmp = pows[N - 1]
        tmp -= 1 
        for sub in subs:
            
            tmp -= pows[sub] - 1
        num[0] += tmp
        return children + 1
    dfs(0)

    
    deno = pows[N]
    num = num[0]
    ret = calc_fraction_mod(num, deno)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    A = [int()] * (N - 1)  
    B = [int()] * (N - 1)  
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


MOD = 1000000007
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            nums[v] += nums[nv] + 1
            tmp += pow2[nums[nv] + 1] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N = int(stdin.buffer.readline())
m = map(int, stdin.buffer.read().split())
AB = zip(m, m)
G = [[] for _ in range(N)]
for a, b in AB:
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            nums[v] += nums[nv] + 1
            tmp += pow2[nums[nv] + 1] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            nums[v] += nums[nv] + 1
            tmp += pow2[nums[nv] + 1] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Solution (Python):
from sys import stdin, setrecursionlimit
from collections import deque

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            c = nums[nv] + 1
            nums[v] += c
            tmp += pow2[c] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)


memo = [[] for _ in range(N + 1)]


def dfs(s, p=-1):
    sub_tree = []
    res = 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        sub_tree.append(size)
        res += size
    if N != res:
        sub_tree.append(N - res)
    memo[s].extend(sub_tree)
    return res


dfs(1)
pow2 = [1] * (N + 1)
for i in range(1, N + 1):
    pow2[i] = pow2[i - 1] * 2 % mod

cnt = 0
for lis in memo[1:]:
    if len(lis) == 1:
        continue
    
    tmp = pow2[N - 1] - 1  
    for x in lis:
        black = pow2[x] - 1
        tmp = (tmp - black + mod) % mod
    cnt = (cnt + tmp) % mod

div = pow2[N]
ans = cnt * pow(div, mod - 2, mod) % mod
print(ans)

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)


ans = 0
pow2 = [1] * (N + 1)
for i in range(1, N + 1):
    pow2[i] = pow2[i - 1] * 2 % mod


def dfs(s, p=-1):
    global ans
    res = 1
    tmp = pow2[N-1] - 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        res += size
        tmp = (tmp - pow2[size] + 1 + mod) % mod
    if N != res:
        tmp = (tmp - pow2[N-res] + 1 + mod) % mod
    ans = (ans + tmp) % mod
    return res


dfs(1)
div = pow2[N]
print(ans*pow(div, mod-2, mod) % mod)

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        g[i] = [j for j in g[i] if di <= d[j]]

    d = [j for i, j in sorted([(j, i) for i, j in enumerate(d)])]
    dp = [(0, 0, 1) for _ in [0]*n]

    for i in d[::-1]:
        if g:
            n = sum([dp[j][2] for j in g[i]])+1
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                xj, yj, nj = dp[j]
                p1, p2 = pow2[n-nj], pow2[nj]
                x += xj*p1+yj*(p1-1)-p2+1
                y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline


sys.setrecursionlimit(10**9)
from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))




def main():
	mod=10**9+7
	n=II()
	G=[[] for _ in range(n+1)]
	p=[0]*(n+1)
	v=[0]*(n+1)


	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)

	inv2=[1]*(n+1)
	t=pow(pow(2,n,mod),mod-2,mod)
	for i in range(n,-1,-1):
		inv2[i]=t
		t*=2
		t%=mod
	

	def dfs(a):
		cnt=1
		for i in G[a]:
			if p[a]==i:
				continue
			else:
				p[i]=a
				cnt+=dfs(i)
		v[a]=cnt
		return cnt
	dfs(1)
	

	def f(a):
		return (1-inv2[a])*(1-inv2[n-a])%mod

	ans=1-inv2[n]-n*inv2[1]
	for i in range(1,n+1):
		ans+=f(v[i])%mod
	print(ans%mod)



if __name__ == "__main__":
	main()

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()

Solution (Python):
n=int(input())
mod=10**9+7
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)

inv2=[1]*(n+1)
t=pow(pow(2,n,mod),mod-2,mod)
for i in range(n,-1,-1):
    inv2[i]=t
    t*=2
    t%=mod
    
import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
ans=[0]
def f(a):
    return inv2[n-a]*(1-inv2[a])%mod
def dfs(s,d):
    dep[s]=d
    tmp=inv2[1]-inv2[n]
    y=0
    for i in edge[s]:
        if dep[i]==-1:
            x=dfs(i,d+1)
            tmp-=f(x)
            y+=x
    if y==0:
        return 1
    tmp-=f(n-y-1)
    ans[0]+=tmp
    ans[0]%=mod
    return y+1
dfs(1,0)
print(ans[0])

Solution (Python):

from collections import deque
n=int(input())
e = [[] for _ in range(n)]

for i in range(n-1):
    ai,bi=map(int,input().split( ))
    ai-=1;bi-=1
    e[ai].append(bi)
    e[bi].append(ai)

deg = [len(e[i]) for i in range(n)]
dep0 = [-1]*n
dep0[0]=0

Q=deque();Q.append(0)

while Q:
    v=Q.popleft()
    for u in e[v]:
        if dep0[u]<0:
            dep0[u]=dep0[v]+1
            Q.append(u)
size = [1]*n
for i in range(n):
    flag=True
    for j in e[i]:
        if dep0[i]<dep0[j]:
            flag=False
            break
    if flag:
        Q.append(i)
while Q:
    v=Q.popleft()
    for u in e[v]:
        if dep0[u]<dep0[v]:
            size[u]+=size[v]
            deg[u]-=1
            if deg[u]==1 and u:
                Q.append(u)
ans=0
mod=10**9+7
x=pow(2,mod-2,mod)

pw_rev=[1]*(n+1)
for i in range(1,n+1):
    
    pw_rev[i] = pw_rev[i-1] * x % mod
for u in range(n):
    for v in e[u]:
        if dep0[u]<dep0[v]:
            ans += (1 - pw_rev[size[v]]) * (1 - pw_rev[n-size[v]])
    ans%=mod

print((ans-n*x+1-pw_rev[n]) % mod)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1;
        E[u].append(v)
        E[v].append(u)

    size = [1] * n
    stack = [(0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            size[p] += size[~v]

    def rerooting(v, p):
        if p == -1:
            return
        size[p] -= size[v]
        size[v] += size[p]

    res = [None] * n
    stack = [(0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            if res[v] is None:
                cnt = pow(2, n - 1, MOD)
                cnt -= 1
                for nv in E[v]:
                    cnt -= pow(2, size[nv], MOD) - 1
                res[v] = cnt % MOD
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    print(sum(res) * pow(2, n * (MOD - 2) % (MOD - 1), MOD) % MOD)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

pow2 = [0 for _ in range(n+1)]
pow2[0] = 1
for i in range(n):
    pow2[i+1] = pow2[i]*2 % mod

for _ in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)


def func(x):
    return pow2[x]-1


class Tree:
    def __init__(self, crdinal, adjgrph, root, fnction=lambda x: 0):
        self.crdinal = crdinal
        self.adjgrph = adjgrph
        self.root = root
        self.fnction = fnction
        self.parent = [-1]*self.crdinal
        self.depth = [-1]*self.crdinal
        self.subsize = [1]*self.crdinal
        self.result = [0]*self.crdinal

        s = [root]
        while s:
            v = s.pop()
            if self.depth[v] == -1:
                if v == root:
                    self.depth[v] = 0
                else:
                    self.depth[v] = self.depth[self.parent[v]] + 1
                    s.append(v)
                for w in self.adjgrph[v]:
                    if self.depth[w] == -1:
                        self.parent[w] = v
                        s.append(w)
            else:
                self.subsize[self.parent[v]] += self.subsize[v]
                self.result[self.parent[v]] += self.fnction(self.subsize[v])

    def parent(self) -> list:
        return self.parent

    def depth(self) -> list:
        return self.depth

    def size(self) -> list:
        return self.subsize

    def result(self) -> list:
        return self.result


tr = Tree(n, g, 0, func)
sizesub = tr.subsize
black = tr.result


cnt = 0

for i in range(n):
    tmp = pow2[n-1] - pow2[n-sizesub[i]] - black[i]
    tmp %= mod
    cnt += tmp
    cnt %= mod


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    
    return (mod+x % mod) % mod


print(inv(pow2[n], mod)*cnt % mod)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

pow2 = [0 for _ in range(n+1)]
pow2[0] = 1
for i in range(n):
    pow2[i+1] = pow2[i]*2 % mod

for _ in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

par = [-1]*n
depth = [-1]*n
sizesub = [1 for _ in range(n)]
black = [0 for _ in range(n)]

root = 0
stack = [root]

while stack:
    v = stack.pop()
    if depth[v] == -1:
        if v == root:
            depth[v] = 0
        else:
            depth[v] = depth[par[v]] + 1
            stack.append(v)
        for w in g[v]:
            if depth[w] == -1:
                par[w] = v
                stack.append(w)
    else:
        sizesub[par[v]] += sizesub[v]
        black[par[v]] += pow2[sizesub[v]] - 1


cnt = 0

for i in range(n):
    tmp = pow2[n-1] - pow2[n-sizesub[i]] - black[i]
    tmp %= mod
    cnt += tmp
    cnt %= mod


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    
    return (mod+x % mod) % mod


print(inv(pow2[n], mod)*cnt % mod)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

par = [-1]*n
depth = [-1]*n
sizesub = [1 for _ in range(n)]
black = [0 for _ in range(n)]

root = 0
stack = [root]

while stack:
    v = stack.pop()
    if depth[v] == -1:
        if v == root:
            depth[v] = 0
        else:
            depth[v] = depth[par[v]] + 1
            stack.append(v)
        for w in g[v]:
            if depth[w] == -1:
                par[w] = v
                stack.append(w)
    else:
        sizesub[par[v]] += sizesub[v]
        black[par[v]] += pow(2, sizesub[v], mod) - 1


cnt = 0

for i in range(n):
    tmp = pow(2, n-1, mod) - pow(2, n-sizesub[i], mod) - black[i]
    tmp %= mod
    cnt += tmp
    cnt %= mod


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    
    return (mod+x % mod) % mod


print(inv(pow(2, n, mod), mod)*cnt % mod)

Solution (Python):
import sys
readline = sys.stdin.readline

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx - self.N0
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx - self.N0

def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            ast(vf)
    return par, order

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


N = int(readline())
MOD = 10**9+7
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)


pow2 = [1]*(N+3)
for i in range(1, len(pow2)):
    pow2[i] = (2*pow2[i-1])%MOD
P, L = parorder(Edge, 0)

dp1 = [0]*N
dp2 = [0]*N
size = [1]*N
for l in L[:0:-1]:
    p = P[l]
    size[p] += size[l]

for l in L[:0:-1]:
    p = P[l]
    dp1[l] = (dp1[l] + pow2[size[l]-1] - 1)%MOD
    dp2[l] = (dp2[l] + pow2[size[l]-1] - 1)%MOD
    k = pow2[size[p]-1-size[l]]
    dp1[p] = (dp1[p] - (pow2[size[l]]-1) + (2*k-1)*dp2[l] + dp1[l])%MOD
    dp2[p] = (dp2[p] + 2*dp2[l]*k)%MOD

dp1[0] = (dp1[0] + pow2[size[0]-1] - 1)%MOD
print(dp1[0]*pow(pow(2, N, MOD), MOD-2, MOD)%MOD)