54 lines
1.0 KiB
Python
54 lines
1.0 KiB
Python
try:
|
|
import psyco
|
|
psyco.full()
|
|
except ImportError:
|
|
pass
|
|
|
|
MAX_N = 300
|
|
BRANCH = 4
|
|
|
|
ra = [0] * MAX_N
|
|
unrooted = [0] * MAX_N
|
|
|
|
def tree(br, n, l, sum = 1, cnt = 1):
|
|
global ra, unrooted, MAX_N, BRANCH
|
|
for b in xrange(br + 1, BRANCH + 1):
|
|
sum += n
|
|
if sum >= MAX_N:
|
|
return
|
|
|
|
# prevent unneeded long math
|
|
if l * 2 >= sum and b >= BRANCH:
|
|
return
|
|
|
|
if b == br + 1:
|
|
c = ra[n] * cnt
|
|
else:
|
|
c = c * (ra[n] + (b - br - 1)) / (b - br)
|
|
|
|
if l * 2 < sum:
|
|
unrooted[sum] += c
|
|
|
|
if b < BRANCH:
|
|
ra[sum] += c;
|
|
for m in range(1, n):
|
|
tree(b, m, l, sum, c)
|
|
|
|
def bicenter(s):
|
|
global ra, unrooted
|
|
if not (s & 1):
|
|
aux = ra[s / 2]
|
|
unrooted[s] += aux * (aux + 1) / 2
|
|
|
|
|
|
def main():
|
|
global ra, unrooted, MAX_N
|
|
ra[0] = ra[1] = unrooted[0] = unrooted[1] = 1
|
|
|
|
for n in xrange(1, MAX_N):
|
|
tree(0, n, n)
|
|
bicenter(n)
|
|
print "%d: %d" % (n, unrooted[n])
|
|
|
|
main()
|