There are n cities and n - 1 roads in the Seven Kingdoms, each road connects two cities and we can reach any city from any other by the roads.

Theon and Yara Greyjoy are on a horse in the first city, they are starting traveling through the roads. But the weather is foggy, so they can’t see where the horse brings them. When the horse reaches a city (including the first one), it goes to one of the cities connected to the current city. But it is a strange horse, it only goes to cities in which they weren't before. In each such city, the horse goes with equal probabilities and it stops when there are no such cities. 

Let the length of each road be 1. The journey starts in the city 1. What is the expected length (expected value of length) of their journey? You can read about expected (average) value by the link https://en.wikipedia.org/wiki/Expected_value.


-----Input-----

The first line contains a single integer n (1 ≤ n ≤ 100000) — number of cities.

Then n - 1 lines follow. The i-th line of these lines contains two integers u_{i} and v_{i} (1 ≤ u_{i}, v_{i} ≤ n, u_{i} ≠ v_{i}) — the cities connected by the i-th road.

It is guaranteed that one can reach any city from any other by the roads.


-----Output-----

Print a number — the expected length of their journey. The journey starts in the city 1.

Your answer will be considered correct if its absolute or relative error does not exceed 10^{ - 6}.

Namely: let's assume that your answer is a, and the answer of the jury is b. The checker program will consider your answer correct, if $\frac{|a - b|}{\operatorname{max}(1, b)} \leq 10^{-6}$.


-----Examples-----
Input
4
1 2
1 3
2 4

Output
1.500000000000000

Input
5
1 2
1 3
3 4
2 5

Output
2.000000000000000



-----Note-----

In the first sample, their journey may end in cities 3 or 4 with equal probability. The distance to city 3 is 1 and to city 4 is 2, so the expected length is 1.5.

In the second sample, their journey may end in city 4 or 5. The distance to the both cities is 2, so the expected length is 2.

Difficulty: MEDIUM
Tags: Graph algorithms

Graph traversal

Probability

Tree algorithms

Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
def dfs(start):
	visited = [0, True] + [False] * (n - 1)
	stack = [(x, 1, 1 / len(tree[start])) for x in tree[start]]
	while stack:
		(v, l, p) = stack.pop()
		if leafs[v]:
			L.append(l * p)
		if not visited[v]:
			visited[v] = True
			for u in tree[v]:
				if not visited[u]:
					stack.append((u, l + 1, p / (len(tree[v]) - 1)))
n = int(input())
tree = {x: [] for x in range(1, n + 1)}
L = []
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	tree[u].append(v)
	tree[v].append(u)
leafs = [False, True] + [len(tree[x]) == 1 for x in range(2, n + 1)]
dfs(1)
print(sum(L))


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
int1 = lambda x: int(x) - 1
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
G = defaultdict(list)

def addEdge(u, v):
	G[u].append(v)
	G[v].append(u)

def bfs(N):
	q = deque()
	vis = [False] * (N + 1)
	q.append((1, 1))
	vis[1] = True
	count = 0
	path = -1
	v = 0
	while q:
		path += 1
		for i in range(len(q)):
			(p, r) = q.popleft()
			z = G.get(p, [])
			if len(z) == 1 and p != 1:
				v += path / r
			vis[p] = True
			for j in z:
				if not vis[j]:
					if p == 1:
						q.append((j, len(z) * r))
					else:
						q.append((j, (len(z) - 1) * r))
	return v
N = int(input())
for i in range(N - 1):
	(u, v) = aj()
	addEdge(u, v)
if N == 1:
	print(0)
	exit(0)
ans = bfs(N)
print(ans)


n = int(input())
t = {x: [] for x in range(1, n + 1)}
v = set()
s = 0
q = [(1, 1, 0)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	t[a].append(b)
	t[b].append(a)
while q:
	(u, p, depth) = q.pop()
	v.add(u)
	branch = 0
	for i in t[u]:
		if i not in v:
			branch += 1
	leaf = not branch
	if leaf:
		s += p * depth
	else:
		for i in t[u]:
			if i not in v:
				q.append((i, p / branch, depth + 1))
print(s)


from sys import stdin, stdout

def main():
	n = int(stdin.readline().strip())
	g = [[] for i in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = [int(_) for _ in stdin.readline().strip().split()]
		g[u].append(v)
		g[v].append(u)
	visited = [False for i in range(n + 1)]
	paths = []
	stack = [(1, 0, 1)]
	while len(stack):
		(u, plen, prb) = stack.pop()
		visited[u] = True
		nBranch = 0
		for v in g[u]:
			if not visited[v]:
				nBranch += 1
		if nBranch > 0:
			probability = prb * (1 / nBranch)
			for v in g[u]:
				if not visited[v]:
					stack.append((v, plen + 1, probability))
		if nBranch == 0:
			paths.append(plen * prb)
	ans = sum(paths)
	stdout.write(str(ans) + '\n')

def __starting_point():
	main()
__starting_point()


from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math

def get_int():
	return int(stdin.readline().strip())

def get_tuple():
	return map(int, stdin.readline().split())

def get_list():
	return list(map(int, stdin.readline().split()))

def main():
	n = get_int()
	graph = defaultdict(list)
	for _ in range(n - 1):
		(u, v) = get_tuple()
		graph[u].append(v)
		graph[v].append(u)
	queue = deque()
	(queue.append((1, 1, 0)), 0)
	vis = [0] * (n + 1)
	res = 0
	while queue:
		(v, cnt, h) = queue.pop()
		vis[v] = 1
		c = 0
		for i in graph[v]:
			if not vis[i]:
				c += 1
		if c == 0:
			res += cnt * h
		else:
			for i in graph[v]:
				if not vis[i]:
					queue.append((i, cnt / c, h + 1))
	print(res)
TestCases = False
if TestCases:
	for i in range(get_int()):
		main()
else:
	main()


n = int(input())
g = {i: [] for i in range(n)}
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	g[u].append(v)
	g[v].append(u)
v = set()
q = [(0, 1, 0)]
res = 0
while q:
	(s, p, l) = q.pop()
	v.add(s)
	dep = 0
	for to in g[s]:
		if to not in v:
			dep += 1
	if dep == 0:
		res += p * l
	else:
		for to in g[s]:
			if to not in v:
				q.append((to, p / dep, l + 1))
print(res)


def sol():
	n = int(input())
	if n == 1:
		print(0)
		return 0
	cities = []
	for i in range(n):
		cities.append([])
	was = [False] * n
	for i in range(n - 1):
		(a, b) = list(map(int, input().split()))
		cities[a - 1].append(b - 1)
		cities[b - 1].append(a - 1)
	q = [[0, 1]]
	preQ = []
	s = -1
	out = []

	def dfs(ind, howDeep):
		was[ind] = True
		c = cities[ind]
		fl = False
		prob = howDeep / max(1, len(c) - 1)
		if ind == 0:
			prob = howDeep / len(c)
		for i in range(len(c)):
			if not was[c[i]]:
				preQ.append([c[i], prob])
				fl = True
		if not fl:
			out.append(s * howDeep)
	while len(q):
		s += 1
		for i in range(len(q)):
			dfs(q[i][0], q[i][1])
		q = []
		for i in range(len(preQ)):
			q.append(preQ[i])
		preQ = []
	print(sum(out))
sol()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
n = int(input())
g = [[] for i in range(100000)]
ans = 0.0
q = []
for i in range(n - 1):
	(u, v) = map(int, input().split())
	g[u - 1].append(v - 1)
	g[v - 1].append(u - 1)
q.append((0, 1, 0))
v = [0] * n
while q:
	(node, prob, h) = q.pop()
	v[node] = 1
	adj = 0
	for i in g[node]:
		if v[i] == 0:
			adj += 1
	if adj == 0:
		ans += prob * h
	else:
		for i in g[node]:
			if v[i] == 0:
				q.append((i, prob / adj, h + 1))
				v[i] = 1
print('{0:.20f}'.format(ans))


from sys import stdin, stdout
input = stdin.buffer.readline
import collections
n = int(input())
tree = collections.defaultdict(list)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	tree[u].append(v)
	tree[v].append(u)
queue = collections.deque()
queue.append([0, -1, 1])
res = d = 0
while queue:
	q = len(queue)
	for _ in range(q):
		(u, p, t) = queue.popleft()
		isleaf = True
		for v in tree[u]:
			if v != p:
				isleaf = False
				queue.append([v, u, t / (len(tree[u]) - (1 if u != 0 else 0))])
		if isleaf:
			res += d * t
	d += 1
print(res)


def __starting_point():
	n = int(input())
	edges = [[] for i in range(n + 1)]
	edges[0] = None
	for i in range(n - 1):
		(n1, n2) = list(map(int, input().split()))
		edges[n1].append(n2)
		edges[n2].append(n1)
	stack = [(1, 0, 1.0)]
	sev = 0
	visited = [False for i in range(n + 1)]
	while len(stack) > 0:
		(node, height, prob) = stack.pop()
		visited[node] = True
		children = len(edges[node]) - 1
		if node == 1:
			children += 1
		for child in edges[node]:
			if visited[child]:
				continue
			stack.append((child, height + 1, prob / children))
		if children == 0:
			sev += height * prob
	print(sev)
__starting_point()


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions, statistics
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal
from sys import stdout
from heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest
INF = 99999999999999999999999999999999

def main():
	mod = 1000000007
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	tc = 1
	for _ in range(tc):
		n = ri()
		visited = [False] * (n + 1)
		graph = [[] for i in range(n + 1)]
		q = deque([])
		for i in range(n - 1):
			(a, b) = ria()
			graph[a].append(b)
			graph[b].append(a)
		dist = [0] * (n + 1)
		visited[1] = True
		q.append(1)
		leafsdis = []
		prob = [0] * (n + 1)
		prob[1] = 1
		while q:
			parent = q[0]
			q.popleft()
			if parent != 1:
				if len(graph[parent]) == 1:
					leafsdis.append(dist[parent] * prob[parent])
			for i in graph[parent]:
				if not visited[i]:
					if parent == 1:
						prob[i] = prob[parent] / len(graph[parent])
					else:
						prob[i] = prob[parent] / (len(graph[parent]) - 1)
					visited[i] = True
					q.append(i)
					dist[i] = dist[parent] + 1
		print(sum(leafsdis))
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


from collections import defaultdict
n = int(input())
d = {}
d = defaultdict(lambda : [], d)
for _ in range(n - 1):
	(u, v) = map(int, input().split(' '))
	d[u].append(v)
	d[v].append(u)
arr = [[1, 1, 0]]
vis = [0] * (n + 1)
vis[1] = 1
s = 0
while len(arr) != 0:
	x = arr.pop(0)
	cnt = 0
	flag = 0
	for i in d[x[0]]:
		if vis[i] == 0:
			flag = 1
			cnt += 1
	if flag == 0:
		s += x[1] * x[2]
	else:
		for i in d[x[0]]:
			if vis[i] == 0:
				arr.append([i, x[1] / cnt, x[2] + 1])
				vis[i] = 1
print(s)


from functools import reduce
n = int(input())
paths = []
for _ in range(n):
	paths.append([])
for _ in range(n - 1):
	(i, j) = [int(k) - 1 for k in input().split()]
	paths[i].append(j)
	paths[j].append(i)
stack = [(0, 0, 1)]
visited = set()
answer = 0
while stack:
	(vertex, deep, branching) = stack.pop()
	visited.add(vertex)
	unvisited_count = reduce(lambda acc, el: acc if el in visited else acc + 1, paths[vertex], 0)
	if unvisited_count == 0:
		answer += deep / branching
		continue
	for other_vertex in paths[vertex]:
		if other_vertex not in visited:
			stack.append((other_vertex, deep + 1, branching * unvisited_count))
print(answer)


n = int(input())
d = {}
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	if u in d:
		d[u].add(v)
	else:
		d[u] = {v}
	if v in d:
		d[v].add(u)
	else:
		d[v] = {u}
stack = [1]
pr = {1: 1}
l = {1: 0}
ans = 0
poped = set()
if n != 1:
	while stack:
		p = stack.pop()
		poped.add(p)
		c = 0
		for x in d[p]:
			if x not in poped:
				c += 1
		if c != 0:
			for x in d[p]:
				if x not in poped:
					pr[x] = pr[p] / c
					l[x] = l[p] + 1
					stack.append(x)
		else:
			ans += pr[p] * l[p]
print(ans)


from sys import stdin
from decimal import Decimal as D
input = stdin.readline
n = int(input())
adj = [[] for i in range(n + 1)]
tree = [[] for i in range(n + 1)]
visit = [-1] * (n + 1)
length = [-1] * (n + 1)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	adj[a].append(b)
	adj[b].append(a)
bfsord = []
from collections import deque
Q = deque()
Q.append(1)
visit[1] = 0
while len(Q):
	p = Q.popleft()
	bfsord.append(p)
	for q in adj[p]:
		if visit[q] != -1:
			continue
		visit[q] = visit[p] + 1
		Q.append(q)
		tree[p].append(q)
for p in reversed(bfsord):
	if not tree[p]:
		length[p] = D(0)
	else:
		length[p] = D(1) + sum((length[q] for q in tree[p])) / len(tree[p])
print(length[1])


from collections import deque
import sys
from decimal import Decimal
readline = sys.stdin.readline
n = int(input())
edges = [[] * n for _ in [None] * n]
for _ in [None] * (n - 1):
	(a, b) = map(int, readline().split())
	edges[a - 1].append(b - 1)
	edges[b - 1].append(a - 1)
visited = [False] * n
visited[0] = True
cnt = 0
total = 0
dq = deque()
(append, pop) = (dq.append, dq.popleft)
append((0, 0, Decimal(1)))
while dq:
	(pos, l, multiple) = pop()
	flag = True
	to = [x for x in edges[pos] if visited[x] == False]
	if to:
		x = len(to)
		multiple /= Decimal(x)
		for v in to:
			visited[v] = True
			append((v, l + 1, multiple))
	else:
		total += Decimal(l) * multiple
print(total)


n = int(input())
tree = {x: [] for x in range(1, n + 1)}
for _ in range(n - 1):
	(k, l) = list(map(int, input().split()))
	tree[k].append(l)
	tree[l].append(k)
visited = set()
s = 0
a = [(1, 1, 0)]
while a:
	(v, p, l) = a.pop()
	visited.add(v)
	k = 0
	for vv in tree[v]:
		if vv not in visited:
			k += 1
	if k <= 0:
		s += p * l
	else:
		for vv in tree[v]:
			if vv not in visited:
				a.append((vv, p * 1.0 / k, l + 1))
print(s)


import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest

def STR():
	return list(input())

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

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

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def sortListWithIndex(listOfTuples, idx):
	return sorted(listOfTuples, key=lambda x: x[idx])

def sortDictWithVal(passedDic):
	temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]
	toret = {}
	for tup in temp:
		toret[tup[0]] = tup[1]
	return toret

def sortDictWithKey(passedDic):
	return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
n = INT()
graph = defaultdict(list)
for _ in range(n - 1):
	(t1, t2) = MAP()
	graph[t1].append(t2)
	graph[t2].append(t1)
visited = [False] * (n + 1)
q = deque([(1, 0, 1)])
leafLengths = []
total = 0
while q:
	popped = q.popleft()
	node = popped[0]
	dis = popped[1]
	probab = popped[2]
	flag = 1
	visited[node] = True
	numChild = len(graph[node])
	if node != 1:
		numChild -= 1
	for child in graph[node]:
		if visited[child] == False:
			q.append((child, dis + 1, probab / numChild))
			flag = 0
	if flag == 1:
		leafLengths.append((dis, probab))
		total += 1
ans = 0
for el in leafLengths:
	ans += el[0] * el[1]
print(ans)


from sys import maxsize, stdout, stdin, stderr
mod = int(1000000000.0 + 7)

def I():
	return int(stdin.readline())

def lint():
	return [int(x) for x in stdin.readline().split()]

def S():
	return input().strip()

def grid(r, c):
	return [lint() for i in range(r)]
from collections import defaultdict, Counter
import math
import heapq
from heapq import heappop, heappush
import bisect
from itertools import groupby

def gcd(a, b):
	while b:
		a %= b
		tmp = a
		a = b
		b = tmp
	return a

def lcm(a, b):
	return a / gcd(a, b) * b

def check_prime(n):
	for i in range(2, int(n ** (1 / 2)) + 1):
		if not n % i:
			return False
	return True

def Bs(a, x):
	i = 0
	j = 0
	left = 0
	right = len(a)
	flag = False
	while left < right:
		mi = (left + right) // 2
		if a[mi] <= x:
			left = mi + 1
			i += 1
		else:
			right = mi
			j += 1
	if left > 0 and a[left - 1] == x:
		return (i - 1, j)
	else:
		return (-1, -1)

def nCr(n, r):
	return fact(n) / (fact(r) * fact(n - r))

def fact(n):
	res = 1
	for i in range(2, n + 1):
		res = res * i
	return res

def primefactors(n):
	num = 0
	while n % 2 == 0:
		num += 1
		n = n / 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			num += 1
			n = n // i
	if n > 2:
		num += 1
	return num

def ask(a):
	print('? {}'.format(a), flush=True)
	n = lint()
	return n
d = defaultdict(lambda : [])

def dfs(i, p):
	(a, tmp) = (0, 0)
	for j in d[i]:
		if j != p:
			a += 1
			tmp += dfs(j, i)
	if a == 0:
		return 0
	return tmp / a + 1
n = I()
for i in range(n - 1):
	(a, b) = lint()
	d[a].append(b)
	d[b].append(a)
(v, q, ans) = ([0] * (n + 1), [(1, 1, 1)], 0)
while q:
	(p, cnt, h) = q.pop()
	(v[p], c) = (1, 0)
	for i in d[p]:
		if not v[i]:
			c += 1
	if c == 0:
		ans += cnt * h
	else:
		for i in d[p]:
			if not v[i]:
				q.append((i, cnt / c, h + 1))
				v[i] = 1
print(ans - 1)


from sys import stdin, stdout, setrecursionlimit
setrecursionlimit(10 ** 6)
import threading
threading.stack_size(2 ** 26)

class SOLVE:

	def dfs(self, child, parent, node):
		total = 0
		for v in node[child]:
			if v != parent:
				total += self.dfs(v, child, node) + 1
		return total / (len(node[child]) - (1 if parent else 0)) if total else 0

	def solve(self):
		R = stdin.readline
		W = stdout.write
		n = int(R())
		node = [[] for i in range(n + 1)]
		for _ in range(n - 1):
			(u, v) = [int(x) for x in R().split()]
			node[u].append(v)
			node[v].append(u)
		print(self.dfs(1, 0, node))
		return 0

def main():
	s = SOLVE()
	s.solve()
threading.Thread(target=main).start()


n = int(input())
lines = [[] for i in range(n + 1)]
for i in range(n - 1):
	(x, y) = map(int, input().split())
	lines[x].append(y)
	lines[y].append(x)
q = [(1, 0, 1)]
head = 0
f = [True] * (n + 1)
f[1] = False
ans = 0
while head < len(q):
	leaf = True
	num = len(lines[q[head][0]]) - (1 if q[head][0] != 1 else 0)
	for i in lines[q[head][0]]:
		if f[i]:
			q.append((i, q[head][1] + 1, q[head][2] / num))
			f[i] = False
			leaf = False
	if leaf:
		ans += q[head][1] * q[head][2]
	head += 1
print(ans)


import collections

def bfs1(graph):
	visited = len(graph) * [False]
	visited[0] = True
	q = collections.deque([(0, 0, 1.0)])
	ans = 0.0
	while len(q) > 0:
		(vertex, depth, prob) = q.popleft()
		if len(graph[vertex]) == 1 and visited[graph[vertex][0]]:
			ans += prob * depth
		else:
			num_child = 0
			for child in graph[vertex]:
				if not visited[child]:
					num_child += 1
			for child in graph[vertex]:
				if not visited[child]:
					visited[child] = True
					q.append((child, depth + 1, prob * (1.0 / num_child)))
	return ans
n = int(input())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
	(one, two) = map(int, input().split())
	one -= 1
	two -= 1
	graph[one].append(two)
	graph[two].append(one)
if n == 1:
	print(0)
else:
	leaf1 = bfs1(graph)
	print(leaf1)


from queue import *
n = int(input())
g = [[] for x in range(n)]
for i in range(n - 1):
	(a, b) = map(int, input().split())
	a -= 1
	b -= 1
	g[a].append(b)
	g[b].append(a)
used = [0] * n
anw = 0

def solve(v, d, r):
	nonlocal anw
	q = Queue()
	q.put((v, d, r))
	while not q.empty():
		(v, d, r) = q.get(v)
		used[v] = True
		for u in g[v]:
			if not used[u]:
				q.put((u, d + 1, r * (len(g[v]) - (v != 0))))
		if v != 0 and len(g[v]) == 1:
			anw += d / r
solve(0, 0, 1)
print(anw)


from sys import stdin

def main():
	n = int(input())
	(g, r) = ([[] for _ in range(n + 1)], 0.0)
	for s in stdin.read().splitlines():
		(u, v) = map(int, s.split())
		g[u].append(v)
		g[v].append(u)
	stack = [(1, 1, -1)]
	while stack:
		(u, denom, depth) = stack.pop()
		depth += 1
		vv = g[u]
		if vv:
			denom *= len(vv)
			for v in vv:
				g[v].remove(u)
				stack.append((v, denom, depth))
		else:
			r += depth / denom
	print(r)
main()


n = int(input())
e = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	e[u].append(v)
	e[v].append(u)
used = [False for i in range(n + 1)]
sol = 0
q = [(1, 0, 1)]
used[1] = True
while len(q):
	(u, d, p) = q.pop()
	if len(e[u]) == 1:
		sol += d * p
	for v in e[u]:
		if not used[v]:
			np = p / (len(e[u]) - (u != 1))
			q.append((v, d + 1, np))
			used[v] = True
print(sol)


import sys
readline = sys.stdin.readline

def i1():
	return int(readline())

def nl():
	return [int(s) for s in readline().split()]

def nn(n):
	return [int(readline()) for i in range(n)]

def nnp(n, x):
	return [int(readline()) + x for i in range(n)]

def nmp(n, x):
	return (int(readline()) + x for i in range(n))

def nlp(x):
	return [int(s) + x for s in readline().split()]

def nll(n):
	return [[int(s) for s in readline().split()] for i in range(n)]

def mll(n):
	return ([int(s) for s in readline().split()] for i in range(n))

def s1():
	return readline().rstrip()

def sl():
	return [s for s in readline().split()]

def sn(n):
	return [readline().rstrip() for i in range(n)]

def sm(n):
	return (readline().rstrip() for i in range(n))

def redir(s):
	global readline
	import os
	fn = sys.argv[0] + f'/../in-{s}.txt'
	readline = open(fn).readline if os.path.exists(fn) else readline
import os
if 'DEPTH' in os.environ:

	def printd(*a, **aa):
		print(*a, **aa)
else:

	def printd(*a, **aa):
		pass
redir('c')
n = i1()
nodes = [[] for i in range(n + 1)]
depth = [0] * (n + 1)
notseen = [0] * (n + 1)
fa = [0] * (n + 1)
for i in range(1, n):
	(u, v) = nl()
	nodes[u].append(v)
	nodes[v].append(u)
stk = [1]
notseen[1] = 1
depth[1] = 0
_ = 0
pathlens = []
while stk:
	r = stk[-1]
	ch = nodes[r]
	_ += 1
	if notseen[r] < 2:
		d = 1 + depth[r]
		for c in ch:
			if notseen[c] == 0:
				notseen[c] += 1
				fa[c] = r
				depth[c] = d
				stk.append(c)
		notseen[r] += 1
	else:
		r = stk.pop()
		ch = nodes[r]
		if len(ch) == 1 and r != 1:
			pathlens.append(depth[r])
		else:
			total = sum((depth[i] for i in ch if i != fa[r]))
			deg = len(ch) - (r != 1)
			depth[r] = total / deg if deg else total
print(depth[1])


import sys
readline = sys.stdin.readline

def i1():
	return int(readline())

def nl():
	return [int(s) for s in readline().split()]

def nn(n):
	return [int(readline()) for i in range(n)]

def nnp(n, x):
	return [int(readline()) + x for i in range(n)]

def nmp(n, x):
	return (int(readline()) + x for i in range(n))

def nlp(x):
	return [int(s) + x for s in readline().split()]

def nll(n):
	return [[int(s) for s in readline().split()] for i in range(n)]

def mll(n):
	return ([int(s) for s in readline().split()] for i in range(n))

def s1():
	return readline().rstrip()

def sl():
	return [s for s in readline().split()]

def sn(n):
	return [readline().rstrip() for i in range(n)]

def sm(n):
	return (readline().rstrip() for i in range(n))

def redir(s):
	global readline
	import os
	fn = sys.argv[0] + f'/../in-{s}.txt'
	readline = open(fn).readline if os.path.exists(fn) else readline
import os
if 'DEPTH' in os.environ:

	def printd(*a, **aa):
		print(*a, **aa)
else:

	def printd(*a, **aa):
		pass
redir('c')
n = i1()
nodes = [[] for i in range(n + 1)]
depth = [0] * (n + 1)
notseen = [True] * (n + 1)
fa = [0] * (n + 1)
for i in range(1, n):
	(u, v) = nl()
	nodes[u].append(v)
	nodes[v].append(u)
leaf = [len(nodes[i]) == 1 for i in range(n + 1)]
leaf[1] = len(nodes[1]) < 1
stk = [(1, 0, 1)]
ans = 0
while stk:
	(r, depth, weight) = stk.pop()
	if leaf[r]:
		ans += weight * depth
		continue
	ch = nodes[r]
	weight /= len(ch) - (r != 1)
	for c in ch:
		if notseen[c]:
			notseen[c] = False
			stk.append((c, depth + 1, weight))
print(ans)


import sys
import threading
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)

def recur(pos):
	global visited
	global edges
	global leaf
	visited[pos] = True
	count = 0
	size = float(len(edges[pos][1])) if pos == 1 else float(len(edges[pos][1]) - 1)
	for node in edges[pos][1]:
		if not visited[node]:
			edges[node][2] *= size * edges[pos][2]
			edges[node][0] = edges[pos][0] + 1.0
			recur(node)
			count += 1
	if count == 0:
		leaf.append(pos)

def main():
	global visited
	global edges
	global leaf
	n = int(input())
	visited = [False] * (n + 1)
	edges = [[0.0, [], 1.0] for i in range(n + 1)]
	leaf = []
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		edges[a][1].append(b)
		edges[b][1].append(a)
	visited[0] = True
	recur(1)
	s = sum([edges[idx][0] / edges[idx][2] for idx in leaf])
	print(s)
t = threading.Thread(target=main)
t.start()
t.join()


import sys
import threading
threading.stack_size(2 ** 26)
sys.setrecursionlimit(10 ** 6)

def main():
	n = int(input())
	adj = [[] for i in range(n)]
	vis = [False] * n

	def expected(u):
		vis[u] = True
		res = 0
		count = 0
		for v in adj[u]:
			if not vis[v]:
				count += 1
				res += 1 + expected(v)
		if count > 0:
			res /= count
		return res
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		adj[u - 1].append(v - 1)
		adj[v - 1].append(u - 1)
	print(expected(0))
threading.Thread(target=main).start()


import sys, math
input = sys.stdin.readline

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input().strip()

def listStr():
	return list(input().strip())
import collections as col
import math
from types import GeneratorType

def solve():

	def bootstrap(f, stack=[]):

		def wrappedfunc(*args, **kwargs):
			if stack:
				return f(*args, **kwargs)
			else:
				to = f(*args, **kwargs)
				while True:
					if type(to) is GeneratorType:
						stack.append(to)
						to = next(to)
					else:
						stack.pop()
						if not stack:
							break
						to = stack[-1].send(to)
				return to
		return wrappedfunc

	@bootstrap
	def tour(graph, node, visited_dict):
		if node not in visited_dict:
			visited_dict[node] = node
		n_count = 0
		for neighbour in graph[node]:
			if neighbour not in visited_dict:
				n_count += 1
		if n_count == 0:
			yield 0.0
		ans = 0.0
		for neighbour in graph[node]:
			if neighbour not in visited_dict:
				x = (yield tour(graph, neighbour, visited_dict))
				ans += (1.0 + x) / n_count
		yield ans
	N = getInt()
	graph = col.defaultdict(set)
	for n in range(N - 1):
		(U, V) = getInts()
		graph[U].add(V)
		graph[V].add(U)
	visited_dict = {}
	if N < 2:
		return N - 1
	expected_val = tour(graph, 1, visited_dict)
	return expected_val
print(solve())


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	d = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		d[a].append(b)
		d[b].append(a)
	d[1].append(1)
	vis = [0] * (n + 1)
	stack = [(1, 1, 0)]
	ans = 0
	while stack:
		zz = stack.pop()
		if vis[zz[0]]:
			continue
		vis[zz[0]] = 1
		pp = len(d[zz[0]])
		if pp == 1:
			ans += zz[1] * zz[2]
		else:
			for item in d[zz[0]]:
				if vis[item] == 0:
					stack.append((item, zz[1] / (pp - 1), zz[2] + 1))
	print('{:.7f}'.format(ans))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import defaultdict
I = lambda : int(input())
IL = lambda : list(map(int, input().split()))
n = I()
N = defaultdict(set)
for i in range(n - 1):
	(a, b) = IL()
	N[a].add(b)
	N[b].add(a)
ans = 0
S = [(1, 0, 1.0)]
depth = 0
while S:
	S2 = []
	for (v, h, p) in S:
		nv = N[v] - {h}
		if not nv:
			ans += p * depth
			continue
		for v2 in nv:
			S2.append((v2, v, p / len(nv)))
	depth += 1
	S = S2
print(ans)


from os import path
import sys, time, collections as c, math as m, pprint as p
(maxx, localsys, mod) = (float('inf'), 0, int(1000000000.0 + 7))
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
input = sys.stdin.readline
n = int(input())
g = c.defaultdict(list)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
(v, q, ans) = ([0] * (n + 1), [(1, 1, 1)], 0)
while q:
	(p, cnt, h) = q.pop()
	(v[p], c) = (1, 0)
	for i in g[p]:
		if not v[i]:
			c += 1
	if c == 0:
		ans += cnt * h
	else:
		for i in g[p]:
			if not v[i]:
				q.append((i, cnt / c, h + 1))
				v[i] = 1
print('%.14f' % (ans - 1))


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from threading import stack_size, Thread
sys.setrecursionlimit(10 ** 6)
stack_size(2 ** 25)
visited = {}
dic = {}
subsize = {}

def dfs(node):
	visited[node] = 1
	curr_size = 0
	count = 0
	for i in dic[node]:
		if visited[i] == 0:
			count += 1
			curr_size += dfs(i)
	subsize[node] = curr_size / max(1, count)
	return curr_size / max(1, count) + 1

def main():
	for _ in range(1):
		global dic, visited, subsize
		n = int(input())
		if n == 1:
			print(0)
		else:
			for i in range(n - 1):
				(u, v) = map(int, input().split())
				if u in dic:
					dic[u].append(v)
				else:
					dic[u] = [v]
				if v in dic:
					dic[v].append(u)
				else:
					dic[v] = [u]
			for i in range(1, n + 1):
				visited[i] = 0
				subsize[i] = 0
			dfs(1)
			print(subsize[1])
Thread(target=main).start()


import queue
n = int(input().strip())
graph = [[] for _ in range(n)]
probabilities = [1.0] * n
dist = [0] * n
visited = [False] * n
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a - 1].append(b - 1)
	graph[b - 1].append(a - 1)
q = queue.Queue()
q.put(0)
sum_ = 0
while not q.empty():
	top = q.get()
	count = 0
	visited[top] = True
	if len(graph[top]) == 1 and top != 0:
		sum_ += dist[top] * probabilities[top]
	for i in graph[top]:
		if not visited[i]:
			count += 1
	for i in graph[top]:
		if not visited[i]:
			dist[i] = dist[top] + 1
			probabilities[i] = probabilities[top] / count
			q.put(i)
print('{0:.15f}'.format(sum_))


import sys
input = sys.stdin.readline

def bfs(d):
	visited = set()
	visited.add(1)
	queue = [1]
	level = {}
	prob = {1: 1}
	level[1] = 0
	p = []
	while len(queue) != 0:
		r = queue.pop(0)
		o = d[r]
		f = 0
		s = 0
		w = []
		for i in o:
			if i not in visited:
				f = 1
				s = s + 1
				w.append(i)
		for i in w:
			level[i] = level[r] + 1
			prob[i] = prob[r] * (1 / s)
			queue.append(i)
			visited.add(i)
		if f == 0:
			p.append(level[r] * prob[r])
	g = sum(p)
	return g
n = int(input())
if n != 1:
	d = {}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		if a in d:
			x = d[a]
			x.append(b)
			d[a] = x
		else:
			d[a] = [b]
		if b in d:
			x = d[b]
			x.append(a)
			d[b] = x
		else:
			d[b] = [a]
	ans = bfs(d)
	q = str(ans)
	sys.stdout.write(q)
else:
	print(0)


import sys

def explore(src, prob, length, adj_mat, gains, visited):
	nexts = set(adj_mat[src]) - visited
	if nexts:
		go_prob = 1 / len(nexts)
		length += 1
		for dst in nexts:
			visited.add(dst)
			explore(dst, prob * go_prob, length, adj_mat, gains, visited)
	else:
		gains[src] += prob * length

def main():
	n = int(sys.stdin.readline())
	adj_mat = [[] for __ in range(n)]
	node_exp = [0 for __ in range(n)]
	for __ in range(n - 1):
		(u, v) = list(map(int, sys.stdin.readline().split()))
		adj_mat[u - 1].append(v - 1)
		adj_mat[v - 1].append(u - 1)
	stk = [0]
	visited = set([0])
	prob = [1] * n
	length = [0] * n
	while stk:
		nxt = stk.pop()
		nexts = set(adj_mat[nxt]) - visited
		if nexts:
			go_prob = 1 / len(nexts)
			for dst in nexts:
				visited.add(dst)
				stk.append(dst)
				prob[dst] *= prob[nxt] * go_prob
				length[dst] = length[nxt] + 1
		else:
			node_exp[nxt] += prob[nxt] * length[nxt]
	print('{:.13f}'.format(sum(node_exp)))
main()


n = int(input())
t = {x: [] for x in range(1, n + 1)}
for _ in range(n - 1):
	(k, l) = map(int, input().split())
	t[k].append(l)
	t[l].append(k)
(v, s, a) = (set(), 0, [(1, 1, 0)])
while a:
	(vs, p, l) = a.pop()
	v.add(vs)
	k = 0
	for vi in t[vs]:
		if vi not in v:
			k += 1
	if k <= 0:
		s += p * l
	else:
		for vi in t[vs]:
			if vi not in v:
				a.append((vi, p * 1 / k, l + 1))
print(s)


from collections import defaultdict
from typing import Dict, List, Set, Tuple

def parse_input() -> Tuple[int, List[List[int]]]:
	n = int(input())
	arr = [[int(x) for x in input().split()] for _ in range(n - 1)]
	return (n, arr)

def create_graph(arr: List[List[int]]) -> Dict[int, List[int]]:
	g: Dict[int, List[int]] = defaultdict(list)
	for (u, v) in arr:
		g[u].append(v)
		g[v].append(u)
	return g

def solve(n: int, arr: List[List[int]]) -> float:
	g = create_graph(arr)
	expected_value = 0.0
	queue: List[Tuple[int, int, int]] = [(1, 0, 1)]
	visited: Set[int] = set()
	while queue:
		curr = queue.pop()
		visited.add(curr[0])
		children = len([node for node in g[curr[0]] if node not in visited])
		if children == 0:
			expected_value += curr[1] * (1 / curr[2])
		else:
			for node in g[curr[0]]:
				if node not in visited:
					queue.append((node, curr[1] + 1, children * curr[2]))
	return expected_value
(n, arr) = parse_input()
print(solve(n, arr))


from collections import deque, Counter

def mean_of_ways(graph, n):
	leafs = []
	distances = [None] * n
	probabilities = [0] * n
	probabilities[0] = 1
	distances[0] = 0
	used = [False] * n
	used[0] = True
	active_vertices = deque([0])
	while active_vertices:
		where = active_vertices.popleft()
		is_leaf = True
		leafs_count = [not used[v] for v in graph[where]].count(True)
		if leafs_count > 1:
			probabilities[where] /= leafs_count
		for to in graph[where]:
			if not used[to]:
				active_vertices.append(to)
				distances[to] = distances[where] + 1
				probabilities[to] = probabilities[where]
				used[to] = True
				is_leaf = False
		if is_leaf:
			leafs.append(where)
	Mx = 0
	for i in leafs:
		Mx += probabilities[i] * distances[i]
	return Mx

def main():
	n = int(input())
	graph = [list() for i in range(n)]
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		u -= 1
		v -= 1
		graph[u].append(v)
		graph[v].append(u)
	print(mean_of_ways(graph, n))
main()


import sys
n = int(input())
if n == 1:
	print(0)
	exit()
d = {}
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	if a not in d:
		d[a] = set()
	d[a].add(b)
	if b not in d:
		d[b] = set()
	d[b].add(a)
x = [None] * (n + 1)
for node in d:
	if len(d[node]) == 1 and node != 1:
		x[node] = 0
done = False
visited = [None] * (n + 1)
unvisited = set([1])
traverseOrder = [1]
while unvisited:
	node = unvisited.pop()
	visited[node] = True
	for neighbour in d[node]:
		if visited[neighbour] == None:
			unvisited.add(neighbour)
			traverseOrder += [neighbour]
			visited[neighbour] = True
for node in traverseOrder[::-1]:
	if len(d[node]) == 1 and node != 1:
		x[node] = 0
	else:
		cost = 0
		count = 0
		for child in d[node]:
			if x[child] != None:
				cost += x[child]
				count += 1.0
		x[node] = 1 + cost / count
print(x[1])


class Node:

	def __init__(self, index):
		self.neighbours = []
		self.index = index
		self.prob = 1.0
		self.vis = False
		self.length = 0

	def addNode(self, city):
		self.neighbours.append(city)
		if self.index == 1:
			self.prob = 1.0 / len(self.neighbours)
		else:
			l = len(self.neighbours)
			self.prob = 1.0 if l < 2 else 1.0 / (l - 1)
n = int(input())
if n == 1:
	print(0)
	exit()
cities = {}
for i in range(n - 1):
	(a, b) = map(lambda k: int(k), input().split())
	if a not in cities:
		cities[a] = Node(a)
	cities[a].addNode(b)
	if b not in cities:
		cities[b] = Node(b)
	cities[b].addNode(a)
if len(cities) == 2:
	print(1)
	exit()

def inorder(city):
	s = []
	s.append(city)
	while s:
		city = s.pop()
		city.vis = True
		if city.neighbours:
			if city.index == 1 or len(city.neighbours) > 1:
				for c in city.neighbours:
					if not cities[c].vis:
						cities[c].length = city.length + 1
						cities[c].prob *= city.prob
						s.append(cities[c])
			else:
				yield (city.index, city.prob, city.length)
test = sum([city[1] * city[2] for city in inorder(cities[1])])
print(test)


from collections import defaultdict

def solve():
	n = int(input())
	route = defaultdict(list)
	for i in range(n - 1):
		(x, y) = list(map(int, input().split(' ')))
		route[x].append(y)
		route[y].append(x)
	visited = set()
	queue = [(1, 0, 1)]
	total = 0
	while len(queue) > 0:
		(node, distance, probability) = queue.pop(0)
		visited.add(node)
		branches = route[node]
		unique = 0
		for i in branches:
			if i not in visited:
				unique += 1
		for i in branches:
			if i not in visited:
				queue.append((i, distance + 1, probability / unique))
		if unique == 0:
			total += probability * distance
	print(total)
solve()


from sys import stdin, stdout, setrecursionlimit
import threading
g = None
visited = None
paths = None

def dfs(u, plen, prb):
	nonlocal visited, paths
	visited[u] = True
	nBranch = 0
	for v in g[u]:
		if not visited[v]:
			nBranch += 1
	if nBranch > 0:
		probability = prb * (1 / nBranch)
		for v in g[u]:
			if not visited[v]:
				dfs(v, plen + 1, probability)
	if nBranch == 0:
		paths.append(plen * prb)

def main():
	nonlocal g, visited, paths
	n = int(stdin.readline().strip())
	g = [[] for i in range(n + 1)]
	for _ in range(n - 1):
		(u, v) = [int(_) for _ in stdin.readline().strip().split()]
		g[u].append(v)
		g[v].append(u)
	visited = [False for i in range(n + 1)]
	paths = []
	dfs(1, 0, 1)
	ans = sum(paths)
	stdout.write(str(ans) + '\n')

def __starting_point():
	setrecursionlimit(10 ** 6)
	threading.stack_size(134217728)
	thread = threading.Thread(target=main)
	thread.start()
__starting_point()


from sys import stdin
inp = stdin.readline
(n, ans) = (int(inp()), 0)
g = {v: [] for v in range(1, n + 1)}
visited = [0] * (n + 1)
q = [(1, 1, 0)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
while q:
	(v, cnt, h) = q.pop()
	visited[v] = 1
	adj = 0
	for i in g[v]:
		if not visited[i]:
			adj += 1
	if adj == 0:
		ans += cnt * h
	else:
		for i in g[v]:
			if not visited[i]:
				q.append((i, cnt / adj, h + 1))
print(ans)


n = int(input())
if n == 1:
	print(0)
	exit()
graph = [None] * n
for i in range(n - 1):
	(u, v) = map(int, input().split())
	u -= 1
	v -= 1
	if graph[u] == None:
		graph[u] = [v]
	else:
		graph[u].append(v)
	if graph[v] == None:
		graph[v] = [u]
	else:
		graph[v].append(u)
is_checked = [False] * n
lens = [None] * n
lens[0] = 0
divs = [None] * n
divs[0] = 1
stack = [0]
ans = 0
while stack:
	top = stack.pop()
	is_checked[top] = True
	vals = graph[top]
	for i in range(len(vals)):
		cur = vals[i]
		if not is_checked[cur]:
			lens[cur] = lens[top] + 1
			divs[cur] = divs[top] * (len(vals) - (1 if top != 0 else 0))
			if len(graph[cur]) == 1:
				ans += lens[cur] / divs[cur]
				is_checked[cur] = None
				lens[cur] = None
				divs[cur] = None
				continue
			stack.append(cur)
print('{:.8f}'.format(ans))


def solve(graph, root, numNodes):
	graph[0] = {root}
	graph[root].add(0)
	solution = [0 for node in range(numNodes + 1)]
	for (child, parent) in dfs(graph, 0, 0, numNodes):
		solution[child] /= len(graph[child]) - 1 or 1
		solution[parent] += 1 + solution[child]
	return solution[root]

def dfs(graph, root, rootParent, numNodes):
	visited = [False for _ in range(numNodes + 1)]
	queue = [(root, rootParent)]
	while queue:
		(node, parent) = queue[-1]
		visited[node] = True
		numUnvisitedNeighbors = 0
		for neighbor in graph[node]:
			if not visited[neighbor]:
				queue.append((neighbor, node))
				numUnvisitedNeighbors += 1
		if numUnvisitedNeighbors == 0:
			yield queue.pop()

def inputTree(numNodes):
	tree = {1: set()}
	for _ in range(numNodes - 1):
		(u, v) = map(int, input().split())
		tree.setdefault(u, set()).add(v)
		tree.setdefault(v, set()).add(u)
	return tree
numNodes = int(input())
print(solve(inputTree(numNodes), 1, numNodes))


import sys

def main():
	n = int(input())
	if n == 1:
		print(0)
		return
	x = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b) = map(int, sys.stdin.readline().split())
		x[a - 1].append(b - 1)
		x[b - 1].append(a - 1)
	isl = [False] * n
	for i in range(1, n):
		if len(x[i]) == 1:
			isl[i] = True
	u = [False] * n
	u[0] = True
	q = [(0, 0, 1 / len(x[0]))]
	a = 0
	while len(q) != 0:
		(c, s, t) = q.pop()
		for i in x[c]:
			if not u[i]:
				if isl[i]:
					a += (s + 1) * t
				else:
					q.append((i, s + 1, t / (len(x[i]) - 1)))
				u[i] = True
	print(a)
main()


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
n = int(input())
adj = [[] for i in range(n + 1)]
for i in range(n - 1):
	(s, e) = map(int, input().split())
	adj[s].append(e)
	adj[e].append(s)
po = [0] * (n + 1)
po[0] = 1

@bootstrap
def dfs(node, old, kkk, dist):
	global res
	po[node] = po[old] / kkk
	if len(adj[node]) == 1 and adj[node][0] == old:
		res += dist * po[node]
	else:
		tt = len(adj[node]) - (1 if old != 0 else 0)
		for i in adj[node]:
			if i != old:
				yield dfs(i, node, tt, dist + 1)
	yield
res = 0
dfs(1, 0, 1, 0)
print(res)


n = int(input())
a = [[] for i in range(n + 1)]
for i in range(n - 1):
	(c, d) = map(int, input().split())
	a[c].append(d)
	a[d].append(c)
vis = [True] * (n + 1)
vis[1] = False
r = [0] * (n + 1)
r[1] = 1
q = [[1, 1]]
while len(q) != 0:
	x = q.pop()
	for i in a[x[0]]:
		if vis[i]:
			if x[0] == 1:
				r[i] = r[x[0]] / len(a[x[0]])
			else:
				r[i] = r[x[0]] / (len(a[x[0]]) - 1)
			vis[i] = False
			q.append([i, r[i]])
an = 0
for i in range(2, n + 1):
	an += r[i]
print(an)


from queue import Queue
from collections import defaultdict
ans = 0

def dfs(i, p, graph, prob, d):
	global ans
	l = len(graph[i])
	if l == 1 and p != -1:
		ans += prob * d
		return
	if p == -1:
		newProb = prob / l
	else:
		newProb = prob / (l - 1)
	for j in graph[i]:
		if j != p:
			dfs(j, i, graph, newProb, d + 1)
n = int(input())
graph = defaultdict(list)
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
ans = 0
q = Queue()
q.put([1, -1, 1, 0])
while not q.empty() and n != 1:
	t = q.get()
	(i, p, prob, d) = (t[0], t[1], t[2], t[3])
	l = len(graph[i])
	if l == 1 and p != -1:
		ans += prob * d
		continue
	if p == -1:
		newProb = prob / l
	else:
		newProb = prob / (l - 1)
	for j in graph[i]:
		if j != p:
			q.put([j, i, newProb, d + 1])
print(ans)


n = int(input())
res = 0
stack = [(1.0, 0, -1, 0)]
edges = [[] for x in range(n)]
for i in range(n - 1):
	(i, j) = map(int, input().split())
	edges[i - 1].append(j - 1)
	edges[j - 1].append(i - 1)
while len(stack) > 0:
	(prob, depth, prev, curr) = stack.pop()
	if len(edges[curr]) == 1 and curr > 0:
		res += prob * depth
	count = len(edges[curr]) - 1
	if curr == 0:
		count += 1
	for neigh in edges[curr]:
		if neigh == prev:
			continue
		stack.append((prob / count, depth + 1, curr, neigh))
print(res)


from collections import defaultdict, deque

def averagePath(root, hm):
	if not root:
		return 0
	queue = deque([(root, None, 1)])
	total = 0
	while queue:
		for _ in range(len(queue)):
			node = queue.popleft()
			used_paths = 1 if node[1] else 0
			if not len(hm[node[0]]) - used_paths:
				continue
			new_prob = node[2] / (len(hm[node[0]]) - used_paths)
			for item in hm[node[0]]:
				if item == node[1]:
					continue
				queue.append((item, node[0], new_prob))
				total += new_prob
	return total
cities = defaultdict(list)
n = int(input())
for _ in range(n - 1):
	line = list(map(int, input().split()))
	cities[line[0]].append(line[1])
	cities[line[1]].append(line[0])
ans = averagePath(1, cities)
print(ans)


import os
import sys
from io import BytesIO, IOBase
from collections import deque

def main():
	n = int(input())
	tree = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = map(int, input().split())
		tree[x].append(y)
		tree[y].append(x)
	leaf = []
	for i in range(1, n + 1):
		if len(tree[i]) == 1 and i != 1:
			leaf.append(i)
	h = [0] * (n + 1)
	pro = [0] * (n + 1)
	v = [0] * (n + 1)
	pro[0] = 1
	q = deque()
	q.append((0, 1))
	while q:
		(p, c) = q.popleft()
		h[c] = h[p] + 1
		pro[c] = pro[p] / max(len(tree[p]) - (p != 1), 1)
		v[c] = 1
		for i in tree[c]:
			if not v[i]:
				q.append((c, i))
	ans = 0
	for i in leaf:
		ans += (h[i] - 1) * pro[i]
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


from collections import defaultdict
tree = defaultdict(list)
n = int(input())
for i in range(n - 1):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	tree[x].append(y)
	tree[y].append(x)
ans = 0
vis = [0] * n
q = [(0, 1, 0)]
seen = {}
while q:
	child = 0
	(cur, ev, l) = q.pop()
	vis[cur] = 1
	for nv in tree[cur]:
		if vis[nv] != 1:
			child += 1
	if child:
		for nv in tree[cur]:
			if vis[nv] != 1:
				q.append((nv, ev / child, l + 1))
	else:
		ans += ev * l
print('{0:.10f}'.format(ans))


import sys
input = sys.stdin.buffer.readline
from collections import deque

def prog():
	n = int(input())
	adj_list = [[[], 0] for i in range(n + 1)]
	for _ in range(n - 1):
		(a, b) = map(int, input().split())
		adj_list[a][0].append(b)
		adj_list[b][0].append(a)
	adj_list[1][0].append(1)
	s = deque([1])
	probability = [1 for i in range(n + 1)]
	visited = set()
	expected_length = 0
	while s:
		curr = s[-1]
		had_neighbor = False
		visited.add(curr)
		neighbors = adj_list[curr]
		for i in range(neighbors[1], len(neighbors[0])):
			neighbor = neighbors[0][i]
			if neighbor not in visited:
				had_neighbor = True
				s.append(neighbor)
				probability[neighbor] = probability[curr] / (len(neighbors[0]) - 1)
				neighbors[1] = i + 1
				break
		if not had_neighbor:
			s.pop()
			if len(adj_list[curr][0]) == 1:
				expected_length += probability[curr] * len(s)
	print(expected_length)
prog()


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil
mod = 10 ** 9 + 7
for _ in range(1):
	n = int(input())
	memo = {}
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		if u not in memo:
			memo[u] = [[v, 0]]
		else:
			memo[u].append([v, 0])
		if v not in memo:
			memo[v] = [[u, 0]]
		else:
			memo[v].append([u, 0])
	p = [0 for i in range(n + 1)]
	p[1] = 1
	visited = set()
	stack = [1]
	visited.add(1)
	while stack:
		current_node = stack[-1]
		stack.pop()
		curr_p = p[current_node]
		if current_node in memo:
			count = 0
			for nodes in memo[current_node]:
				node = nodes[0]
				if node not in visited:
					count += 1
					nodes[1] = 1
					stack.append(node)
					visited.add(node)
			for nodes in memo[current_node]:
				if nodes[1]:
					p[nodes[0]] += curr_p / count
	print(sum(p) - 1)


from sys import stdin
input = stdin.readline
n = int(input())
edges = list((list(map(int, input().split())) for _ in range(n - 1)))
adj = {i: [] for i in range(1, n + 1)}
for (u, v) in edges:
	adj[u].append(v)
	adj[v].append(u)
(q, res) = ([(1, 1, 0)], 0)
vis = [0] * (n + 1)
while q:
	(v, cnt, h) = q.pop()
	vis[v] = 1
	c = 0
	for i in adj[v]:
		if not vis[i]:
			c += 1
	if c == 0:
		res += cnt * h
	else:
		for i in adj[v]:
			if not vis[i]:
				q.append((i, cnt / c, h + 1))
print(res)


import math
import os
import sys
from sys import *
from decimal import *
from io import BytesIO, IOBase
from itertools import accumulate, combinations, permutations, combinations_with_replacement, product
from collections import *
import random
M = 10 ** 9 + 7
import heapq
from bisect import *
from functools import lru_cache
from queue import PriorityQueue
if sys.version_info[0] < 3:
	from __builtin__ import xrange as range
	from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def inpu():
	return int(inp())

def luckynumber(x, n, a):
	if x > 0:
		a.append(x)
	if x > 10 ** 9:
		return a
	elif x < 1000000000000.0:
		luckynumber(x * 10 + 4, n, a)
		luckynumber(x * 10 + 7, n, a)

def lcm(a, b):
	return a * b // math.gcd(a, b)

def query1(l, r):
	if l >= r:
		return -1
	print('?', l + 1, r + 1)
	sys.stdout.flush()
	return int(input()) - 1

def answer(p):
	print('!', p + 1)
	sys.stdout.flush()
	exit()

def rse(arr, n):
	stack = []
	ans = []
	for i in range(n - 1, -1, -1):
		if len(stack) == 0:
			ans.append(n)
		else:
			while len(stack) != 0:
				if stack[-1][0] >= arr[i]:
					stack.pop()
				else:
					break
			if len(stack) == 0:
				ans.append(n)
			else:
				ans.append(stack[-1][1])
		stack.append([arr[i], i])
	ans.reverse()
	return ans

def lse(arr, n):
	stack = []
	ans = []
	for i in range(n):
		if len(stack) == 0:
			ans.append(-1)
		else:
			while len(stack) != 0:
				if stack[-1][0] >= arr[i]:
					stack.pop()
				else:
					break
			if len(stack) == 0:
				ans.append(-1)
			else:
				ans.append(stack[-1][1])
		stack.append([arr[i], i])
	return ans

def mah(arr):
	max1 = 0
	p = rse(arr, len(arr))
	q = lse(arr, len(arr))
	for i in range(len(arr)):
		a = (p[i] - q[i] - 1) * arr[i]
		max1 = max(a, max1)
	return max1

def maxSumIS(arr, n):
	msis = arr.copy()
	for i in range(1, n):
		for j in range(i):
			if arr[i] > arr[j] and msis[i] < msis[j] + arr[i]:
				msis[i] = msis[j] + arr[i]
	c = max(msis)
	p = 5
	return c

def binarysearch2(arr, target):
	lo = 0
	hi = len(arr) - 1
	while lo <= hi:
		mid = (lo + hi) // 2
		if arr[mid] == target:
			if mid != len(arr) - 1:
				if arr[mid + 1] != target:
					return mid
				else:
					lo += 1
			else:
				return mid
			continue
		if arr[mid] > target:
			hi = mid - 1
		else:
			lo = mid + 1

def ngr(arr, n):
	stack = []
	ans = []
	for i in range(n - 1, -1, -1):
		if len(stack) == 0:
			ans.append(-1)
		else:
			while len(stack) > 0:
				if stack[-1][0] < arr[i]:
					stack.pop()
				else:
					break
			if len(stack) == 0:
				ans.append(-1)
			else:
				ans.append(stack[-1][1])
		stack.append([arr[i], i])
	ans.reverse()
	return ans

def alperm(nums, path, result):
	if not nums:
		result.add(tuple(path))
		return
	for i in range(0, len(nums)):
		alperm(nums[:i] + nums[i + 1:], path + [nums[i]], result)
	return result

def minsum(arr, n, m, res, l):
	if n == 1 and m == 1:
		res += arr[0][0]
		l.append(res)
	else:
		if n != 1:
			p = res + arr[n - 1][m - 1]
			minsum(arr, n - 1, m, p, l)
		if m != 1:
			p = res + arr[n - 1][m - 1]
			minsum(arr, n, m - 1, p, l)
	return min(l)

def subset(arr, n, ans, c):
	if n == 0:
		print(c)
		ans.add(tuple(sorted(c)))
		return
	else:
		op = c + [arr[n - 1]]
		subset(arr, n - 1, ans, op)
		subset(arr, n - 1, ans, c)

def catalan(n):
	if n == 0 or n == 1:
		return 1
	catalan = [0] * (n + 1)
	catalan[0] = 1
	catalan[1] = 1
	for i in range(2, n + 1):
		for j in range(i):
			catalan[i] += catalan[j] * catalan[i - j - 1]
	return catalan[n]

def isP(p, i, j):
	if j <= i:
		return True
	if p[i] != p[j]:
		return False
	return isP(p, i + 1, j - 1)

def main():
	t = 1
	for _ in range(t):
		n = int(input())
		t = defaultdict(list)
		v = set()
		s = 0
		q = [(1, 1, 0)]
		for _ in range(n - 1):
			(a, b) = sep()
			t[a].append(b)
			t[b].append(a)
		while q:
			(u, cnt, num) = q.pop()
			v.add(u)
			dep = 0
			for i in t[u]:
				if i not in v:
					dep += 1
			if dep == 0:
				s += cnt * num
			else:
				for i in t[u]:
					if i not in v:
						q.append((i, cnt / dep, num + 1))
		print(s)
main()


from sys import stdin, setrecursionlimit
from collections import *
import threading

class graph:

	def __init__(self, gdict=None):
		if gdict is None:
			gdict = defaultdict(list)
		(self.gdict, self.edges, self.l) = (gdict, [], defaultdict(int))

	def addEdge(self, node1, node2, w=None):
		self.gdict[node1].append(node2)
		self.gdict[node2].append(node1)
		self.l[node1] += 1
		self.l[node2] += 1

	def bfs(self, i):
		(self.visit, ans) = ([0] * (n + 1), [])
		(queue, self.visit[i]) = (deque([[i, 0]]), 1)
		while queue:
			(s, dist) = queue.popleft()
			for i in self.gdict[s]:
				if self.visit[i] == 0:
					queue.append([i, dist + 1])
					self.visit[i] = 1
			if self.l[s] == 1 and s != 1:
				ans.append(dist)
		return 0 if not ans else (n - 1) / len(ans)

	def DfsUtil(self, v):
		(self.visit[v], val) = (1, [0, 0])
		for i in self.gdict[v]:
			if self.visit[i] == 0:
				val[0] += self.DfsUtil(i)
				val[1] += 1
		if self.l[v] == 1 and v != 1:
			return 0.0
		else:
			return val[0] / val[1] + 1.0

	def dfs(self, n):
		self.visit = [0] * (n + 1)
		return self.DfsUtil(1)

def main():
	(n, g) = (int(stdin.readline()), graph())
	for i in range(n - 1):
		(u, v) = map(int, stdin.readline().split())
		g.addEdge(u, v)
	print('{:.10f}'.format(g.dfs(n)) if n > 1 else '{:.10f}'.format(0))
setrecursionlimit(10 ** 6)
threading.stack_size(102400000)
thread = threading.Thread(target=main)
thread.start()


from collections import defaultdict
from decimal import *
n = int(input())
adj = defaultdict(list)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	adj[u].append(v)
	adj[v].append(u)
v = [0] * (n + 1)
q = [(1, 1, 0)]
ans = 0
while q:
	(e, prob, d) = q.pop()
	v[e] = 1
	cmps = 0
	for cmp in adj[e]:
		if not v[cmp]:
			cmps += 1
	if cmps == 0:
		ans += prob * d
	else:
		for cmp in adj[e]:
			if not v[cmp]:
				q.append((cmp, prob / cmps, d + 1))
print(ans)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd

def solve():
	ans = 0
	stack = [[1, 1, 0]]
	while stack:
		a = stack.pop()
		chil = 0
		for i in d[a[0]]:
			chil += 1
		if chil:
			for i in d[a[0]]:
				stack.append([i, a[1] / chil, a[2] + 1])
		else:
			ans += a[1] * a[2]
	return ans
n = int(input())
dx = {i: set() for i in range(1, n + 1)}
d = {i: set() for i in range(1, n + 1)}
for i in range(n - 1):
	(a, b) = map(int, input().split())
	dx[a].add(b)
	dx[b].add(a)
stack = [1]
while stack:
	a = stack.pop()
	for i in dx[a]:
		d[a].add(i)
		stack.append(i)
		dx[i].remove(a)
print(solve())


import sys

def r():
	return list(map(int, input().split()))
n = int(input())
edge = [r() for i in range(n - 1)]
adj = [[] for i in range(n + 1)]
for e in edge:
	adj[e[0]].append(e[1])
	adj[e[1]].append(e[0])
prob = [0.0 for i in range(n + 1)]
d = [0 for i in range(n + 1)]
visited = [False for i in range(n + 1)]
prob[1] = 1
ans = 0.0
st = [1]
visited[1] = True
while st:
	u = st.pop()
	cnt = len(adj[u])
	if u != 1:
		cnt -= 1
	if cnt == 0:
		ans = ans + prob[u] * d[u]
	else:
		for v in adj[u]:
			if not visited[v]:
				visited[v] = True
				prob[v] = prob[u] * (1.0 / cnt)
				d[v] = d[u] + 1
				st.append(v)
print(ans)


from collections import defaultdict
graph = defaultdict(list)
n = int(input())
for _ in range(n - 1):
	(u, v) = list(map(int, input().split()))
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
distances = {}
prob = [0 for i in range(n)]
q = [(0, 0)]
prob[0] = 1
visited = [False for i in range(n)]
visited[0] = True
while q != []:
	(node, dist) = q[0]
	q.pop(0)
	leaf = True
	m = 0
	for i in graph[node]:
		if visited[i] == False:
			m += 1
	for j in graph[node]:
		if visited[j] == False:
			visited[j] = True
			leaf = False
			prob[j] = prob[node] / m
			q.append((j, dist + 1))
	if leaf:
		distances[node] = dist
ans = 0
for i in distances:
	ans += prob[i] * distances[i]
print(ans)


def zip_sorted(a, b):
	(a, b) = zip(*sorted(zip(a, b)))
	sorted(zip(a, b), key=lambda x: x[1])
	return (a, b)
import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
S = lambda : list(map(str, input().split()))

def solve(adj, visited, degree, root):
	q = [root]
	s = [0]
	p = [1]
	prob = []
	prob1 = []
	i = 0
	visited[root] = 1
	while i < len(q):
		cur = q[i]
		if degree[cur] == 1 and cur != root:
			prob.append(s[i])
			prob1.append(p[i])
			i += 1
			continue
		count = 0
		for j in range(len(adj[cur])):
			if visited[adj[cur][j]] != 1:
				count += 1
		for j in range(len(adj[cur])):
			if visited[adj[cur][j]] != 1:
				q.append(adj[cur][j])
				s.append(s[i] + 1)
				p.append(p[i] * (1 / count))
				visited[adj[cur][j]] = 1
		i += 1
	return (prob, prob1)
(n,) = I()
adj = [[] for j in range(n)]
degree = [0] * n
visited = [0] * n
for i in range(n - 1):
	(a1, b1) = I()
	adj[a1 - 1].append(b1 - 1)
	adj[b1 - 1].append(a1 - 1)
	degree[a1 - 1] += 1
	degree[b1 - 1] += 1
(a, b) = solve(adj, visited, degree, 0)
sum1 = 0
for i in range(len(a)):
	sum1 += a[i] * b[i]
print(sum1)


import collections
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)
v = [-1] * n
v[0] = 0
p = [0.0] * n
p[0] = 1.0
d = [0] * n
q = collections.deque([0])
l = 0
while q:
	x = q.popleft()
	c = 0
	for j in g[x]:
		if v[j] < 0:
			c += 1
			v[j] = x
			d[j] = d[x] + 1
			q.append(j)
	if c == 0:
		l += d[x] * p[x]
	else:
		c = 1 / c * p[x]
		for j in g[x]:
			if v[j] == x:
				p[j] = c
print(l)


n = int(input(''))
Map = {s: set() for s in range(1, n + 1)}
for i in range(n - 1):
	(x, y) = map(int, input().split())
	Map[x].add(y)
	Map[y].add(x)
sum = 0
cities = set()
a = [[0, 1, 1]]
while a != []:
	near_cities = 0
	number = a[-1][0]
	city = a[-1][1]
	pro = a[-1][2]
	cities.add(city)
	near_cities = near_cities + len(Map[city] - cities)
	a.pop()
	if near_cities != 0:
		for next_city in Map[city] - cities:
			a.append([number + 1, next_city, pro / near_cities])
	else:
		sum = sum + pro * number
print(sum)


from collections import deque, defaultdict
n = int(input())
g = defaultdict(list)
for i in range(n - 1):
	(a, b) = map(int, input().split())
	g[a].append(b)
	g[b].append(a)
q = deque()
q.append((1, 0, 1))
visited = set()
res = 0
while q:
	(v, d, p) = q.pop()
	visited.add(v)
	unique = 0
	for x in g[v]:
		if x not in visited:
			unique += 1
	for x in g[v]:
		if x not in visited:
			q.append((x, d + 1, p / unique))
	if unique == 0:
		res += p * d
print(res)


from collections import deque

def edge_input(m):
	edges = []
	for i in range(m):
		edges.append(list(map(int, input().split())))
	return edges

def convert(edges):
	l = {i: [] for i in range(1, n + 1)}
	for i in edges:
		(c1, c2) = (i[0], i[1])
		l[c1].append(c2)
		l[c2].append(c1)
	return l
n = int(input())
l = convert(edge_input(n - 1))
v = {i: False for i in l}
d = {i: -1 for i in l}
p = {i: 1 for i in l}
end = deque([])

def bfs(x):
	d[x] = 0
	q = deque([x])
	v[x] = True
	while len(q) != 0:
		temp = q.popleft()
		c = 0
		for i in l[temp]:
			if v[i]:
				continue
			d[i] = d[temp] + 1
			c += 1
			q.append(i)
		if c == 0:
			end.append(temp)
		else:
			for i in l[temp]:
				if v[i]:
					continue
				v[i] = True
				p[i] = p[temp] * (1 / c)
	return d
d = bfs(1)
ans = 0
for i in end:
	ans += p[i] * d[i]
print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict, deque

def dfs(node):
	vis[node] = 1
	q = deque([node])
	lis = []
	while q:
		cur = q.popleft()
		lis.append(cur)
		for j in edge[cur]:
			if vis[j] == 0:
				vis[j] = 1
				q.append(j)
				child[cur].append(j)
	lis.reverse()
	return lis
n = int(input())
edge = defaultdict(list)
child = defaultdict(list)
for i in range(n - 1):
	(u, v) = list(map(int, input().split()))
	edge[u].append(v)
	edge[v].append(u)
vis = [0] * (n + 1)
dist = [0] * (n + 1)
lis = dfs(1)
for i in lis:
	ans = 0
	b = 0
	for j in child[i]:
		ans += dist[j]
		b += 1
	if b > 0:
		dist[i] = ans / b + 1
print(dist[1])


from collections import defaultdict

def bfs(g, n):
	ans = []
	q = []
	visited = [True] * (n + 1)
	q.append((1, 0, 1))
	visited[1] = False
	while len(q) != 0:
		(city, l, p) = q.pop()
		neighbours = []
		for i in g[city]:
			if visited[i]:
				neighbours.append(i)
		x = len(neighbours)
		if x == 0:
			ans.append(l * p)
		else:
			new_p = p / x
			for nbs in neighbours:
				q.append((nbs, l + 1, new_p))
		visited[city] = False
	return ans
g = defaultdict(list)
n = int(input())
for i in range(n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
a = bfs(g, n)
print(sum(a))


from sys import stdin, stdout
from math import gcd, ceil, sqrt
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007

def bfs(d, n):
	queue = [[1, 1, 0]]
	res = 0
	visited = [0] * (n + 1)
	while len(queue):
		cur = queue.pop(0)
		visited[cur[0]] = 1
		flag = 0
		for i in d[cur[0]]:
			if not visited[i]:
				prop = cur[1] / len(d[cur[0]])
				queue.append([i, prop, cur[2] + 1])
				flag = 1
			d[i].remove(cur[0])
		if flag == 0:
			res += cur[1] * cur[2]
	return res
n = ii1()
d = {}
if n > 1:
	for i in range(n - 1):
		(a, b) = iia()
		d.setdefault(a, []).append(b)
		d.setdefault(b, []).append(a)
	print(bfs(d, n))
else:
	print(0)


n = int(input())
g = [[] for i in range(n + 1)]
for i in range(n - 1):
	(a, b) = [int(x) for x in input().split()]
	g[a].append(b)
	g[b].append(a)
d = [0 for i in range(n + 1)]
v = [0 for i in range(n + 1)]
e = [0 for i in range(n + 1)]
p = [0.0 for i in range(n + 1)]
p[1] = 1.0
en = 0
q = [1]
while len(q):
	c = q.pop(0)
	v[c] = 1
	a = 0
	for ne in g[c]:
		if not v[ne]:
			q.append(ne)
			d[ne] = d[c] + 1
			p[ne] = p[c] / len(g[c]) if c == 1 else p[c] / (len(g[c]) - 1)
			a += 1
	if a == 0:
		e[c] = 1
		en += 1
ave = 0.0
for i in range(n + 1):
	if e[i]:
		ave += d[i] * p[i]
print(ave)


from collections import defaultdict
n = int(input())
g = defaultdict(set)
visited = set()
for i in range(0, n - 1):
	(u, v) = [int(j) for j in input().split()]
	g[u].add(v)
	g[v].add(u)
s = []
e = 0
s.append((1, 0, 1))
while s:
	(c, l, p) = s.pop()
	neighbors = [y for y in g[c] if y not in visited]
	_n = len(neighbors)
	if _n == 0:
		e += l * p
	else:
		new_p = p / _n
		for neighbor in neighbors:
			s.append((neighbor, l + 1, new_p))
	visited.add(c)
print(e)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	g = [[] for _ in range(n)]
	ans = 0
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	visited = [False for _ in range(n)]
	stack = [(0, 1, 0)]
	while stack != []:
		(node, prob, depth) = stack.pop()
		visited[node] = True
		adj_count = 0
		for adj_node in g[node]:
			if not visited[adj_node]:
				adj_count += 1
		if adj_count == 0:
			ans += prob * depth
		else:
			for adj_node in g[node]:
				if not visited[adj_node]:
					stack.append((adj_node, prob / adj_count, depth + 1))
					visited[adj_node] = True
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


gr = []
stack = [[0, -1]]

def dfs(visited):
	new = []
	while len(stack) != 0:
		current = stack[-1]
		new.append(stack.pop())
		visited[current[0]] = 1
		for neighbours in gr[current[0]][1:]:
			if visited[neighbours[0]] != 1:
				stack.append(neighbours)
	while len(new):
		k = new[-1]
		new.pop()
		visited[k[0]] = 0
		if len(gr[k[0]]) == 2 and k[0] != 0:
			gr[k[0]][0][1] = 0
		else:
			comb = 0
			for a in gr[k[0]][1:]:
				if visited[a[0]] == 0:
					comb += gr[a[0]][0][1]
			if len(gr[k[0]]) > 2 and k[0] != 0:
				comb = 1 + comb / (len(gr[k[0]]) - 2)
			else:
				comb = 1 + comb / (len(gr[k[0]]) - 1)
			gr[k[0]][0][1] = comb
	print(gr[0][0][1])

def main():
	n = int(input())
	global gr
	for i in range(n):
		gr.append([[i, -1]])
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		gr[u - 1].append([v - 1, -1])
		gr[v - 1].append([u - 1, -1])
	if n == 1:
		print(0)
	elif n == 2:
		print(1)
	else:
		try:
			v = [0] * n
			v[0] = 1
			dfs(v)
		except RecursionError:
			print(1)
main()


import queue
n = int(input())
dic = {}
for i in range(n + 1):
	dic[i] = []
for i in range(n - 1):
	(u, v) = [int(x) for x in input().split()]
	dic[u].append(v)
	dic[v].append(u)
weight = {1: (0, 1)}
q = queue.Queue()
q.put(1)
while q.empty() == False:
	city = q.get()
	choice = len(dic[city])
	if city > 1:
		choice = choice - 1
	for to_city in dic[city]:
		if to_city not in weight:
			weight[to_city] = (weight[city][0] + 1, weight[city][1] / choice)
			q.put(to_city)
	if choice > 0:
		weight[city] = (weight[city][0], 0)
sum = 0
for city in weight:
	sum = sum + weight[city][0] * weight[city][1]
print('%.15f' % sum)


n = int(input())
graph = {_: [] for _ in range(1, n + 1)}
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	graph[a].append(b)
	graph[b].append(a)
s = 0
seen = set()
queue = [(1, 1, 0)]
while queue:
	(u, cnt, num) = queue.pop()
	seen.add(u)
	dep = 0
	for i in graph[u]:
		if i not in seen:
			dep += 1
	if dep == 0:
		s += cnt * num
	else:
		for i in graph[u]:
			if i not in seen:
				queue.append((i, cnt / dep, num + 1))
print(s)


class Node:

	def __init__(self):
		self.neighs = set()
		self.path_length = 0
		self.prob = 1
		self.visited = False

	def connect(self, node):
		self.neighs.add(node)

def read_graph_from_input():
	nodes = {}
	n = int(input())
	for i in range(1, n + 1):
		nodes[i] = Node()
	for _ in range(0, n - 1):
		(i, j) = map(int, input().split())
		nodes[i].connect(nodes[j])
		nodes[j].connect(nodes[i])
	return nodes[1]

def get_math_exp(root):
	expectation = 0
	nodes = [root]
	while nodes:
		node = nodes.pop()
		not_visited_neighs = set(filter(lambda x: not x.visited, node.neighs))
		if len(not_visited_neighs) == 0:
			expectation += node.path_length * node.prob
		else:
			sub_prob = node.prob / len(not_visited_neighs)
			for neigh in not_visited_neighs:
				neigh.path_length = node.path_length + 1
				neigh.prob = sub_prob
				nodes.append(neigh)
		node.visited = True
	return expectation

def main():
	root = read_graph_from_input()
	print(get_math_exp(root))
main()


from collections import deque

def expected_value(net_of_cities, n):
	nodes = []
	dist = [None] * n
	dist[0] = 0
	prob = [0] * n
	prob[0] = 1
	prev_nodes = [False] * n
	prev_nodes[0] = True
	current_nodes = deque([0])
	while current_nodes != deque([]):
		where = current_nodes.popleft()
		is_node = True
		node_count = 0
		for i in net_of_cities[where]:
			if prev_nodes[i] == False:
				node_count += 1
		if node_count > 1:
			prob[where] /= node_count
		for direction in net_of_cities[where]:
			if not prev_nodes[direction]:
				current_nodes.append(direction)
				dist[direction] = dist[where] + 1
				prob[direction] = prob[where]
				prev_nodes[direction] = True
				is_node = False
		if is_node == True:
			nodes.append(where)
	expected_value = 0
	for i in nodes:
		expected_value += dist[i] * prob[i]
	return expected_value
n = int(input())
net_of_cities = [list() for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	net_of_cities[u - 1].append(v - 1)
	net_of_cities[v - 1].append(u - 1)
print(expected_value(net_of_cities, n))


n = int(input())
t = {x: [] for x in range(1, n + 1)}
v = set()
s = 0
q = [(1, 1, 0)]
for _ in range(n - 1):
	(a, b) = map(int, input().split())
	t[a].append(b)
	t[b].append(a)
while q:
	(u, cnt, num) = q.pop()
	v.add(u)
	dep = 0
	for i in t[u]:
		if i not in v:
			dep += 1
	if dep == 0:
		s += cnt * num
	else:
		for i in t[u]:
			if i not in v:
				q.append((i, cnt / dep, num + 1))
print(s)


import sys
from collections import deque
read = lambda : sys.stdin.readline().rstrip()
readi = lambda : int(sys.stdin.readline())
writeln = lambda x: sys.stdout.write(str(x) + '\n')
write = lambda x: sys.stdout.write(x)
N = readi()
if N == 1:
	writeln(0)
	exit()
G = [set() for _ in range(N)]
for _ in range(N - 1):
	(u, v) = map(int, read().split())
	G[u - 1].add(v - 1)
	G[v - 1].add(u - 1)
visited = [0] * N
prev = [0] * N
visited[0] = 1
prev[0] = 1
q = deque([0])
lengths = []
ev = 0
while q:
	cur = q.popleft()
	n_neighbor = len(G[cur])
	if cur == 0:
		divs = n_neighbor
	else:
		divs = n_neighbor - 1
	if n_neighbor == 1 and cur != 0:
		ev += (visited[cur] - 1) * prev[cur]
		continue
	for nxt in G[cur]:
		if not visited[nxt]:
			visited[nxt] = visited[cur] + 1
			prev[nxt] = 1 / divs * prev[cur]
			q.append(nxt)
print('%.12f' % ev)


n = int(input())
a = []
for i in range(0, n):
	a.append([])
for i in range(0, n - 1):
	(u, v) = map(int, input().split())
	a[u - 1].append(v - 1)
	a[v - 1].append(u - 1)
parent = []
t1 = []
t2 = []
ff = []
for i in range(0, n):
	ff.append(True)
ff[0] = False
parent.append([0, -1, 0])
t1.append(0)
count = 1
while len(t1) > 0:
	for i in range(0, len(t1)):
		for j in range(0, len(a[t1[i]])):
			if ff[a[t1[i]][j]]:
				t2.append(a[t1[i]][j])
				parent.append([count, t1[i], a[t1[i]][j]])
				ff[a[t1[i]][j]] = False
	count += 1
	(t1, t2) = (t2, t1)
	t2 = []
parent.sort()
cost = []
for i in range(0, n):
	cost.append(0)
cost[0] = 1
for i in range(1, n):
	if parent[i][1] == 0:
		cost[parent[i][2]] = cost[parent[i][1]] / len(a[parent[i][1]])
	else:
		cost[parent[i][2]] = cost[parent[i][1]] / (len(a[parent[i][1]]) - 1)
ans = 0
if len(a[0]) > 0:
	ans += 1
for i in range(1, n):
	if len(a[i]) > 1:
		ans += cost[i]
print(ans)


from collections import deque
s = 0
n = int(input())
ls = [[] for i in range(n + 1)]
for i in range(1, n):
	(a, b) = list(map(int, input().split()))
	ls[a].append(b)
	ls[b].append(a)
arr = [0 for i in range(n + 1)]
q = deque()
q.append([1, 1, 0])
while q:
	x = q.pop()
	node = x[0]
	arr[node] = 1
	to_explore = []
	for i in ls[node]:
		if arr[i] == 0:
			to_explore.append(i)
	if len(to_explore) == 0:
		s = s + x[1] * x[2]
		continue
	n = len(to_explore)
	for i in to_explore:
		q.append([i, x[1] / n, x[2] + 1])
print(s)


from collections import deque

class CodeforcesTask839CSolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.roads = []

	def read_input(self):
		self.n = int(input())
		for x in range(self.n - 1):
			self.roads.append([int(y) for y in input().split(' ')])

	def process_task(self):
		expected_value = 0.0
		graph = [[] for x in range(self.n)]
		for edge in self.roads:
			graph[edge[0] - 1].append(edge[1])
			graph[edge[1] - 1].append(edge[0])
		visited = [False] * self.n
		to_visit = deque([(1, 1, 0)])
		root = True
		while to_visit:
			visiting = to_visit.popleft()
			if not visited[visiting[0] - 1]:
				visited[visiting[0] - 1] = True
				if len(graph[visiting[0] - 1]) == 1 and visited[graph[visiting[0] - 1][0] - 1]:
					expected_value += visiting[1] * visiting[2]
				else:
					l = len(graph[visiting[0] - 1]) - 1
					if root:
						l += 1
					to_visit.extend([(x, visiting[1] / l, visiting[2] + 1) for x in graph[visiting[0] - 1]])
			root = False
		self.result = str(expected_value)

	def get_result(self):
		return self.result
Solution = CodeforcesTask839CSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


n = int(input())
graph = []
for i in range(n):
	graph.append([])
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	graph[u - 1].append(v - 1)
	graph[v - 1].append(u - 1)
ans = 0
visited = [0] * n
stack = [(0, 1)]
while stack:
	(curr, prob) = stack.pop()
	visited[curr] = 1
	ans += prob
	r = []
	for i in graph[curr]:
		if not visited[i]:
			r.append(i)
	if r:
		newprob = prob / len(r)
		for i in r:
			stack.append((i, newprob))
print(ans - 1)


from collections import defaultdict
n = int(input())
tree = defaultdict(set)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	tree[u].add(v)
	tree[v].add(u)
Q = [(0, 1.0, 1)]
visited = {1}
ans = 0
while Q:
	(depth, prob, src) = Q.pop()
	for nei in tree[src]:
		if nei not in visited:
			visited.add(nei)
			Q.append((depth + 1, prob / (len(tree[src]) - bool(depth)), nei))
	if depth and len(tree[src]) == 1:
		ans += prob * depth
print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
mod2 = 998244353
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def IF(c, t, f):
	return t if c else f

def YES(c):
	return IF(c, 'YES', 'NO')

def Yes(c):
	return IF(c, 'Yes', 'No')

def main():
	t = 1
	rr = []
	for _ in range(t):
		n = I()
		uv = [LI_() for _ in range(n - 1)]
		e = collections.defaultdict(set)
		for (u, v) in uv:
			e[u].add(v)
			e[v].add(u)
		v = [None] * n
		q = [0]
		v[0] = 1
		for i in range(n):
			c = q[i]
			for u in e[c]:
				if v[u]:
					continue
				q.append(u)
				v[u] = 1
		r = [-1] * n
		for i in q[::-1]:
			t = []
			for u in e[i]:
				if r[u] >= 0:
					t.append(r[u])
			if len(t) == 0:
				r[i] = 0
			else:
				r[i] = sum(t) / len(t) + 1
		rr.append(r[0])
	return JA(rr, '\n')
print(main())


def f():
	n = int(input())
	if n == 1:
		print(0)
		return
	road = {}
	visited = {}
	for i in range(n - 1):
		(u, v) = input().split()
		if u in road:
			road[u].append(v)
		else:
			road[u] = [v]
		if v in road:
			road[v].append(u)
		else:
			road[v] = [u]
		visited[u] = False
		visited[v] = False
	prob = {}
	length = {}
	res = []
	queue = []
	for k in road['1']:
		prob[k] = 1.0 / len(road['1'])
		length[k] = 1
		queue.append(k)
		visited['1'] = True
	while len(queue) > 0:
		cur = queue[0]
		del queue[0]
		dest = []
		for k in road[cur]:
			if not visited[k]:
				dest.append(k)
		if len(dest) == 0:
			res.append((cur, prob[cur], length[cur]))
			continue
		for k in dest:
			prob[k] = prob[cur] / len(dest)
			length[k] = length[cur] + 1
			queue.append(k)
			visited[cur] = True
	val = 0.0
	for item in res:
		val += item[1] * item[2]
	print(val)
f()


from collections import deque
INF = -1
nVertices = int(input())
g = [[] for _ in range(nVertices + 1)]
g[1].append(0)
for _ in range(nVertices - 1):
	(u, cur) = map(int, input().split())
	g[u].append(cur)
	g[cur].append(u)
dist = [0, 0] + [INF] * nVertices
prob = [1] * (nVertices + 1)
q = deque([1])
while q:
	cur = q.pop()
	for to in g[cur]:
		if dist[to] == INF:
			dist[to] = 1 + dist[cur]
			prob[to] *= prob[cur] * (1 / (len(g[cur]) - 1))
			q.appendleft(to)
ret = 0
for v in range(1, nVertices + 1):
	if len(g[v]) == 1:
		ret += dist[v] * prob[v]
print(ret)


from math import sqrt, gcd, ceil, floor, log, factorial
from itertools import permutations, combinations
from collections import Counter, defaultdict
import collections, sys, threading
import collections, sys, threading
sys.setrecursionlimit(10 ** 9)
threading.stack_size(10 ** 8)

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def msi():
	return map(str, input().split())

def li():
	return list(mi())

def solve():

	def dfs(node, par, g, d, parent, prob):
		d[node] = 1 + d[par]
		parent[node] = par
		if node == 1:
			prob[1] = 1
		elif par == 1:
			prob[node] = prob[par] / len(g[par])
		else:
			prob[node] = prob[par] / (len(g[par]) - 1)
		for i in g[node]:
			if i != par:
				dfs(i, node, g, d, parent, prob)
	n = ii()
	if n == 1:
		print(0)
	else:
		d = {0: -1}
		parent = {}
		prob = {}
		g = defaultdict(list)
		for _ in range(n - 1):
			(u, v) = mi()
			g[u].append(v)
			g[v].append(u)
		dfs(1, 0, g, d, parent, prob)
		ans = 0
		for i in range(2, n + 1):
			if len(g[i]) == 1:
				ans += prob[i] * d[i]
		print(ans)
threading.Thread(target=solve).start()


import sys, os, io
import math, bisect, operator
(inf, mod) = (float('inf'), 10 ** 9 + 7)
from itertools import groupby, accumulate
from heapq import heapify, heappop, heappush
from collections import deque, Counter, defaultdict
I = lambda : int(sys.stdin.buffer.readline())
Neo = lambda : list(map(int, sys.stdin.buffer.readline().split()))
n = I()
G = defaultdict(list)
for i in range(n - 1):
	(x, y) = Neo()
	G[x] += [y]
	G[y] += [x]
vis = [0] * (n + 1)
Ans = 0
st = deque([(1, -1, 0, 1)])
while st:
	(node, parent, lenth, p) = st.pop()
	vis[node] = 1
	k = 0
	for i in G[node]:
		if not vis[i]:
			k += 1
	if k > 0:
		p *= k
	for i in G[node]:
		if not vis[i]:
			st.append((i, node, lenth + 1, p))
	if len(G[node]) == 1 and G[node][0] == parent:
		Ans += lenth / p
print(Ans)


import sys

def fill_d(adj_list, visited, stack, d, leaf, p):
	node = stack.pop()
	if visited[node]:
		return
	visited[node] = True
	num_children = len(adj_list[node]) - 1
	if node == 1:
		num_children += 1
	if num_children == 0:
		leaf[node] = True
	else:
		ppc = p[node] / num_children
	for e in adj_list[node]:
		if visited[e] == False:
			stack.append(e)
			d[e] = d[node] + 1
			p[e] = ppc
	return

def answer(n, u, v):
	visited = [False for _ in range(n + 1)]
	adj_list = [[] for _ in range(n + 1)]
	for i in range(n - 1):
		adj_list[v[i]].append(u[i])
		adj_list[u[i]].append(v[i])
	stack = []
	stack.append(1)
	d = [-1 for _ in range(n + 1)]
	leaf = [False for _ in range(n + 1)]
	p = [0 for _ in range(n + 1)]
	p[1] = 1
	d[1] = 0
	while len(stack) > 0:
		fill_d(adj_list, visited, stack, d, leaf, p)
	dist = 0
	for i in range(1, n + 1):
		if leaf[i]:
			dist += d[i] * p[i]
	return dist

def main():
	n = int(sys.stdin.readline())
	u = [0 for _ in range(n - 1)]
	v = [0 for _ in range(n - 1)]
	for i in range(n - 1):
		(u[i], v[i]) = map(int, sys.stdin.readline().split())
	print(answer(n, u, v))
	return
main()


from collections import defaultdict

class Graph:

	def __init__(self):
		self.dict = defaultdict(set)

def main():
	n_cities = int(input())
	g = Graph()
	s = []
	visited = set()
	for i in range(0, n_cities - 1):
		(u, v) = (int(j) for j in input().split())
		g.dict[u].add(v)
		g.dict[v].add(u)
	e = 0
	s.append((1, 0, 1))
	while s:
		(city, l, p) = s.pop()
		neighbors = [c for c in g.dict[city] if c not in visited]
		n = len(neighbors)
		if n == 0:
			e += l * p
		else:
			new_p = p / n
			for neighbor in neighbors:
				s.append((neighbor, l + 1, new_p))
		visited.add(city)
	print(e)
main()


import sys
import inspect
import re
import math
import threading
from collections import defaultdict
from pprint import pprint as pp
mod = 998244353
MAX = 10 ** 15

def deb(p):
	for line in inspect.getframeinfo(inspect.currentframe().f_back)[3]:
		m = re.search('\\bdeb\\s*\\(\\s*([A-Za-z_][A-Za-z0-9_]*)\\s*\\)', line)
		print('%s %d' % (m.group(1), p))

def vector(size, val=0):
	vec = [val for i in range(size)]
	return vec

def matrix(rowNum, colNum, val=0):
	mat = []
	for i in range(rowNum):
		collumn = [val for j in range(colNum)]
		mat.append(collumn)
	return mat

def dmain():
	sys.setrecursionlimit(100000000)
	threading.stack_size(40960000)
	thread = threading.Thread(target=main)
	thread.start()
g = defaultdict(list)

def dfs(ch, par):
	(sum, cnt) = (0, 0)
	for x in g[ch]:
		if x != par:
			sum += dfs(x, ch) + 1
			cnt += 1
	if cnt:
		sum /= cnt
	return sum

def main():
	n = int(input())
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		g[u].append(v)
		g[v].append(u)
	ans = dfs(1, 0)
	print(ans)
dmain()


n = int(input())
gr = [None] * (n + 1)
vis = [0] * (n + 1)
ans = 0
for i in range(1, n):
	(x, y) = map(int, input().split())
	if gr[x] == None:
		gr[x] = [y]
	else:
		gr[x].append(y)
	if gr[y] == None:
		gr[y] = [x]
	else:
		gr[y].append(x)
t = [1, 0, 1.0]
import queue
q = queue.Queue(maxsize=1000000)
q.put(t)
vis[1] = 1
while not q.empty():
	if n == 1:
		break
	t = q.get()
	cnt = 0
	for i in gr[t[0]]:
		if vis[i] == 0:
			cnt += 1
	if cnt == 0:
		ans += t[1] * t[2]
	else:
		t[1] += 1
		t[2] /= cnt
		for i in gr[t[0]]:
			if vis[i] == 0:
				t[0] = i
				q.put(list(t))
				vis[i] = 1
print(ans)


from collections import defaultdict
from collections import deque
from sys import stdin
lines = deque((line.strip() for line in stdin.readlines()))

def nextline():
	return lines.popleft()

def types(cast):
	return tuple((int(x) for x in nextline().split()))

def ints():
	return types(int)

def strs():
	return nextline().split()

def main():
	n = int(nextline())
	graph = defaultdict(list)
	for _ in range(1, n):
		(a, b) = ints()
		graph[a].append(b)
		graph[b].append(a)
	stack = [(1, 1, 0)]
	visited = set()
	expected = 0
	while stack:
		(city, denominator, length) = stack.pop()
		visited.add(city)
		choices = [choice for choice in graph[city] if choice not in visited]
		if choices:
			for choice in choices:
				stack.append((choice, denominator * len(choices), length + 1))
		else:
			expected += length / denominator
	print(expected)

def __starting_point():
	main()
__starting_point()


import sys
readline = sys.stdin.readline

def i1():
	return int(readline())

def nl():
	return [int(s) for s in readline().split()]
n = i1()
nodes = [[] for i in range(n + 1)]
depth = [0] * (n + 1)
notseen = [True] * (n + 1)
fa = [0] * (n + 1)
for i in range(1, n):
	(u, v) = nl()
	nodes[u].append(v)
	nodes[v].append(u)
leaf = [len(nodes[i]) == 1 for i in range(n + 1)]
leaf[1] = len(nodes[1]) < 1
stk = [(1, 0, 1)]
ans = 0
while stk:
	(r, depth, weight) = stk.pop()
	if leaf[r]:
		ans += weight * depth
		continue
	ch = nodes[r]
	weight /= len(ch) - (r != 1)
	for c in ch:
		if notseen[c]:
			notseen[c] = False
			stk.append((c, depth + 1, weight))
print(ans)


import sys
sys.setrecursionlimit(1000000)
n = int(input())
lis = [[] for _ in range(n)]
lis[0].append(0)
for k in range(1, n):
	(a, i) = map(int, input().split())
	lis[a - 1].append(i - 1)
	lis[i - 1].append(a - 1)

def cnt(root, count, div, zero):
	stack = [(root, count, div, zero)]
	while stack:
		(spot, depth, prb, origin) = stack.pop()
		if visited[spot]:
			continue
		visited[spot] = True
		for k in lis[spot]:
			if k != origin:
				prby[k] = (depth + 1) / (prb * (len(lis[spot]) - 1))
				stack.append((k, depth + 1, prb * (len(lis[spot]) - 1), spot))
prby = [0] * n
visited = [False] * n
esp = 0
cnt(0, 0, 1, 0)
for k in range(n - 1, 0, -1):
	if len(lis[k]) == 1:
		esp += prby[k]
print(esp)


n = int(input())
mp = dict()
for i in range(n - 1):
	(x, y) = [int(j) for j in input().split()]
	mp.setdefault(x, []).append(y)
	mp.setdefault(y, []).append(x)
st = list()
visited = [False for i in range(n + 1)]
st.append([1, 0, 1])
visited[1] = True
ans = 0
count = 0
while len(st) != 0:
	(cur_node, fee, prop) = st.pop()
	if cur_node not in mp:
		continue
	if len(mp[cur_node]) == 1 and visited[mp[cur_node][0]]:
		ans += fee * prop
	t = 0
	for next_node in mp[cur_node]:
		if visited[next_node]:
			continue
		t += 1
	for next_node in mp[cur_node]:
		if visited[next_node]:
			continue
		visited[next_node] = True
		st.append([next_node, fee + 1, prop / t])
print(ans)


from sys import setrecursionlimit
import threading
length = 0
visited = None
g = None

def dfs(v, path_length, chance):
	nonlocal length
	visited.add(v)
	edges = 0
	for n in g[v]:
		if n not in visited:
			edges += 1
	for n in g[v]:
		if n not in visited:
			dfs(n, path_length + 1, chance * (1 / edges))
	if edges == 0:
		length += path_length * chance

def main():
	nonlocal visited, g
	vert = int(input())
	g = [[] for _ in range(vert + 1)]
	visited = set()
	for _ in range(vert - 1):
		(a, b) = list(map(int, input().split()))
		g[a].append(b)
		g[b].append(a)
	dfs(1, 0, 1)
	print(length)

def __starting_point():
	setrecursionlimit(10 ** 6)
	threading.stack_size(134217728)
	thread = threading.Thread(target=main)
	thread.start()
__starting_point()


import sys
import threading
sys.setrecursionlimit(1000000)
threading.stack_size(10 ** 8)

def dfs(x):
	global v
	global adj
	global l1
	v[x] = 1
	a = True
	for i in adj[x]:
		if not v[i]:
			a = False
			l1[x] += dfs(i)
	if a == True:
		return 0
	else:
		if x != 1:
			l1[x] = l1[x] / (len(adj[x]) - 1) + 1
		else:
			l1[x] = l1[x] / len(adj[x]) + 1
		return l1[x]

def main():
	global adj
	global l1
	global v
	n = int(input())
	adj = []
	for i in range(n + 1):
		adj.append([])
	v = [0] * (n + 1)
	l1 = [0] * (n + 1)
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		adj[x].append(y)
		adj[y].append(x)
	dfs(1)
	print(l1[1])
t = threading.Thread(target=main)
t.start()
t.join()


n = int(input())
r = [[] for _ in range(n + 1)]
for _ in range(n - 1):
	(u, v) = list(map(int, input().split()))
	u -= 1
	v -= 1
	r[u].append(v)
	r[v].append(u)
if n == 1:
	print(0)
else:
	st = [(0, 0, 1 / len(r[0]))]
	ans = 0
	rsum = 0
	visit = [False] * n
	visit[0] = True
	while st:
		(v, t, m) = st.pop()
		for l in r[v]:
			if not visit[l]:
				if l != 0 and len(r[l]) == 1:
					ans += (t + 1) * m
					rsum += 1
				else:
					st.append((l, t + 1, m / (len(r[l]) - 1)))
				visit[l] = True
	print(ans)


import sys
import re
import collections

def dfs():
	global result
	global stack
	while len(stack) != 0:
		pos = stack.pop()
		visit[pos] = 1
		length = len(edges[pos])
		if pos != 0 and length == 1:
			result += depth[pos] * p[pos]
		for i in range(length):
			if visit[edges[pos][i]] != 1:
				stack.append(edges[pos][i])
				depth[edges[pos][i]] = depth[pos] + 1
				if pos == 0:
					p[edges[pos][i]] = p[pos] / length
				else:
					p[edges[pos][i]] = p[pos] / (length - 1)
n = int(sys.stdin.readline())
a = [list(map(lambda x: int(x) - 1, sys.stdin.readline().split())) for i in range(n - 1)]
edges = [[] for i in range(n)]
visit = [0] * n
depth = [0] * n
p = [0] * n
result = 0
stack = []
for i in range(n - 1):
	edges[a[i][0]].append(a[i][1])
	edges[a[i][1]].append(a[i][0])
depth[0] = 0
p[0] = 1
stack.append(0)
dfs()
print(result)


n = int(input())
d = {x: [] for x in range(1, n + 1)}
for x in range(n - 1):
	(s, de) = map(int, input().split())
	d[s].append(de)
	d[de].append(s)

def dfs():
	lst = [(0, 1.0, 1)]
	visited = set({1})
	ans = 0
	while lst:
		(depth, prob, source) = lst.pop()
		for neigh in d[source]:
			if neigh not in visited:
				visited.add(neigh)
				lst.append((depth + 1, prob * (1 / (len(d[source]) - (1 if depth != 0 else 0))), neigh))
		if depth != 0 and len(d[source]) == 1:
			ans += prob * depth
	return ans
print('{:.8f}'.format(dfs()))


import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
dict = {}

def bfs(start, n, visited, dict):
	out = [0] * n
	q = [start]
	q = deque(q)
	visited[start] = 1
	while len(q) != 0:
		y = dict[q[0]]
		count = 0
		for j in y:
			if visited[j] == 0:
				visited[j] = 1
				q.append(j)
				count += 1
		out[q[0]] = count
		q.popleft()
	return out

def bfs1(start, n, visited, dict, out):
	distance = [0] * n
	prob = [0] * n
	q = [start]
	q = deque(q)
	prob[start] = 1
	ans = 0
	visited[start] = 1
	count = 0
	while len(q) != 0:
		y = dict[q[0]]
		flag = True
		for j in y:
			if visited[j] == 0:
				visited[j] = 1
				flag = False
				distance[j] = distance[q[0]] + 1
				prob[j] += prob[q[0]] / out[q[0]]
				q.append(j)
		if flag == True:
			count += 1
			ans += prob[q[0]] * distance[q[0]]
		q.popleft()
	return ans
for i in range(n):
	dict[i] = []
for i in range(n - 1):
	l = list(map(int, input().split()))
	a = l[0] - 1
	b = l[1] - 1
	dict[a].append(b)
	dict[b].append(a)
visited = [0] * n
out = bfs(0, n, visited, dict)
visit = [0] * n
a1 = bfs1(0, n, visit, dict, out)
print(a1)


import bisect
import collections
import copy
import functools
import heapq
import itertools
import math
import random
import re
import sys
import time
import string
from typing import *
import operator
sys.setrecursionlimit(99999)
n = int(input())
g = [[] for _ in range(n + 1)]
flag = [0] * (n + 1)
for _ in [0] * (n - 1):
	(u, v) = map(int, input().split())
	g[u].append(v)
	g[v].append(u)
q = collections.deque()
q.append((1, 1.0, 0))
ans = 0
while q:
	(node, ch, l) = q.popleft()
	flag[node] = 1
	c = sum((flag[x] == 0 for x in g[node]))
	if c == 0:
		ans += l * ch
		continue
	for nc in g[node]:
		if flag[nc] == 0:
			q.append((nc, ch * 1 / c, l + 1))
print(ans)


import sys, threading

def dfs(v, d, par=0):
	sum = 0
	for i in d[v]:
		if i == par:
			continue
		sum += dfs(i, d, v) + 1
	if sum:
		return sum / (len(d[v]) - (par != 0))
	return 0.0

def main():
	I = lambda : list(map(int, input().split()))
	n = I()[0]
	d = {i: [] for i in range(1, n + 1)}
	for i in range(n - 1):
		(u, v) = I()
		d[u].append(v)
		d[v].append(u)
	print('%.10f' % dfs(1, d))
sys.setrecursionlimit(10 ** 6)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()


class PathNode:

	def __init__(self, i):
		self.index = i
		self.children = []
		self.i = 0
		self.total = 0
		self.child_visit = 0
		self.avg = 0
		self.pending = False
n = int(input())
tree = [PathNode(i) for i in range(n + 1)]
for _ in range(n - 1):
	(u, v) = map(int, input().split(' '))
	tree[u].children.append(v)
	tree[v].children.append(u)
stack = [1]
visited = set()
result = None
while stack:
	current = tree[stack[-1]]
	if current.pending:
		current.total += result
		current.i += 1
		current.child_visit += 1
		current.pending = False
	if len(current.children) > current.i:
		if current.children[current.i] not in visited:
			stack.append(current.children[current.i])
			visited.add(current.index)
			current.pending = True
		else:
			current.i += 1
	else:
		if current.child_visit:
			current.avg = current.total / current.child_visit
		result = current.avg + 1
		stack.pop()
		if current.index in visited:
			visited.remove(current.index)
print(tree[1].avg)


from sys import stdin, stdout
import math, collections, itertools
mod = 998244353

def bfs(adj, node, s, pr0b):
	lvl = {node: 0}
	frn = [node]
	i = 1
	while frn:
		next = []
		for u in frn:
			temp = 0
			for v in adj[u]:
				if v not in lvl:
					next.append(v)
					temp += 1
			for v in adj[u]:
				if v not in lvl:
					lvl[v] = i
					pr0b[v] = pr0b[u] / temp
				if len(adj[v]) == 1 and adj[v][0] == u:
					s[v] = lvl[v]
		frn = next
		i += 1
adj = collections.defaultdict(list)
for _ in range(int(stdin.readline()) - 1):
	(u, v) = map(int, stdin.readline().split())
	adj[u].append(v)
	adj[v].append(u)
s = {}
pr0b = {1: 1}
bfs(adj, 1, s, pr0b)
ans = 0
for i in s:
	ans += s[i] * pr0b[i]
stdout.write(str(ans) + '\n')


n = int(input())
graph = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = input().split()
	graph[int(u) - 1].append(int(v) - 1)
	graph[int(v) - 1].append(int(u) - 1)
ans = 0
visited = [False for i in range(n)]
queue = []
visited[0] = True
for i in graph[0]:
	queue.append((i, 1, 1 / len(graph[0])))
while queue:
	p = queue.pop(0)
	visited[p[0]] = True
	flag = False
	for i in graph[p[0]]:
		if not visited[i]:
			queue.append((i, p[1] + 1, p[2] / (len(graph[p[0]]) - 1)))
			flag = True
	if not flag:
		ans += p[1] * p[2]
print(ans)


import sys
input = sys.stdin.readline
from collections import deque

def bfs():
	q = deque([(0, 1)])
	dist = [-1] * n
	dist[0] = 0
	res = 0
	while q:
		(v, p) = q.popleft()
		flag = True
		for nv in G[v]:
			if dist[nv] == -1:
				dist[nv] = dist[v] + 1
				if v == 0:
					np = p * len(G[v])
				else:
					np = p * (len(G[v]) - 1)
				q.append((nv, np))
				flag = False
		if flag:
			res += dist[v] / p
	return res
n = int(input())
G = [[] for _ in range(n)]
for _ in range(n - 1):
	(u, v) = map(int, input().split())
	G[u - 1].append(v - 1)
	G[v - 1].append(u - 1)
print(bfs())


from collections import defaultdict
n = int(input())
d = defaultdict(list)
for _ in range(n - 1):
	(a, b) = input().split(' ')
	a = int(a)
	b = int(b)
	d[a - 1] += [b - 1]
	d[b - 1] += [a - 1]
visited = [0] * n
level = [0] + [0] * (n - 1)
queue = [0]
c = 0
s = 0
sum1 = 0
prob = [1.0] * n
while queue:
	k = queue.pop()
	count = 0
	visited[k] = 1
	if len(d[k]) == 1 and k != 0:
		sum1 += level[k] * prob[k]
	for i in d[k]:
		if not visited[i]:
			count += 1
	for i in d[k]:
		if not visited[i]:
			visited[i] = 1
			level[i] = level[k] + 1
			prob[i] = prob[k] / count
			queue += [i]
print('{0:.15f}'.format(sum1))


n = int(input())
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	graph[u].append(v)
	graph[v].append(u)
l = []
visited = [0] * (n + 1)
s = [0] * (n + 1)
prob = 1
stack = [(1, prob)]
while len(stack):
	m = 0
	(c, prob) = stack.pop()
	for i in graph[c]:
		if visited[i] == 0:
			m += 1
	if visited[c] == 0:
		visited[c] = 1
		f = 0
		for i in graph[c]:
			if visited[i] == 1:
				s[c] = 1 + s[i]
			else:
				f = 1
				stack.append((i, prob / m))
		if f == 0:
			l.append(s[c] * prob)
print(sum(l))


import math
import sys

def bfs(start):
	q = [start]
	used[start] = 0
	while q != []:
		rt = 0
		for u in g[q[0]]:
			if used[u] == -1:
				rt += 1
		if rt == 0:
			E[0] += used[q[0]] / ver[q[0]]
			ver[q[0]] = 0
		for u in g[q[0]]:
			if used[u] == -1:
				used[u] = used[q[0]] + 1
				ver[u] = ver[q[0]] * rt
				q.append(u)
		del q[0]
n = int(input())
g = [[] for i in range(n)]
for i in range(n - 1):
	(u, v) = map(int, input().split())
	v -= 1
	u -= 1
	g[u].append(v)
	g[v].append(u)
used = [-1] * n
ver = [0] * n
ver[0] = 1
E = [0]
bfs(0)
print('%.12f' % E[0])


from collections import defaultdict
n = int(input())
tree = defaultdict(set)
for i in range(n - 1):
	(u, v) = map(int, input().split())
	tree[u].add(v)
	tree[v].add(u)
visited = set()
ans = 0
Q = [(1, 1, 0)]
while Q:
	(u, cnt, num) = Q.pop()
	visited.add(u)
	dep = 0
	for i in tree[u]:
		if i not in visited:
			dep += 1
	if dep == 0:
		ans += cnt * num
	else:
		for i in tree[u]:
			if i not in visited:
				Q.append((i, cnt / dep, num + 1))
print(ans)


from __future__ import division, print_function
import itertools, os, sys

def ii():
	return int(input())

def si():
	return str(input())

def mi():
	return map(int, input().strip().split(' '))

def li():
	return list(mi())
from collections import deque, Counter, OrderedDict, defaultdict
import threading

def dmain():
	sys.setrecursionlimit(100000000)
	threading.stack_size(40960000)
	thread = threading.Thread(target=main)
	thread.start()
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p1
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
graph = defaultdict(list)

def dfs(v, prev):
	sum = 0
	cnt = 0
	for i in graph[v]:
		if i != prev:
			sum += dfs(i, v) + 1
			cnt += 1
	if cnt:
		sum /= cnt
	return sum

def main():
	n = ii()
	for i in range(n - 1):
		(x, y) = mi()
		graph[x].append(y)
		graph[y].append(x)
	s = dfs(1, 0)
	print(s)
dmain()


import collections
n = int(input(''))
graph = collections.defaultdict(list)
for i in range(n - 1):
	edge = list(map(int, input('').split(' ')))
	graph[edge[0]].append(edge[1])
	graph[edge[1]].append(edge[0])
result = 0
visited = [False] * (n + 1)
stack = [(1, 1, 0)]
while stack:
	(node, curr_prob, depth) = stack.pop(0)
	visited[node] = True
	count = 0
	for children in graph[node]:
		if visited[children] == False:
			count += 1
	if count == 0:
		result += curr_prob * depth
	for children in graph[node]:
		if visited[children] == False:
			stack.append((children, curr_prob / count, depth + 1))
print(result)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(200000)

def main():

	def dfs(graph, start=0):
		n = len(graph)
		visited = [False] * n
		lens = [0] * n
		ps = [1] * n
		ends = []
		l = 0
		p = 1
		stack = [start]
		while stack:
			start = stack[-1]
			l = lens[start]
			p = ps[start]
			c = len(graph[start])
			if start == 0:
				c += 1
			if not visited[start]:
				visited[start] = True
				if c == 1:
					ends.append(l * p)
				else:
					for child in graph[start]:
						if not visited[child]:
							lens[child] = l + 1
							ps[child] = p / (c - 1)
							stack.append(child)
			else:
				stack.pop()
		return sum(ends)
	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)
	print(dfs(g, 0))
main()