37 lines
728 B
Ruby
37 lines
728 B
Ruby
MAX_N = 500
|
|
BRANCH = 4
|
|
|
|
def tree(br, n, l=n, sum=1, cnt=1)
|
|
for b in br+1 .. BRANCH
|
|
sum += n
|
|
return if sum >= MAX_N
|
|
# prevent unneeded long math
|
|
return if l * 2 >= sum and b >= BRANCH
|
|
if b == br + 1
|
|
c = $ra[n] * cnt
|
|
else
|
|
c = c * ($ra[n] + (b - br - 1)) / (b - br)
|
|
end
|
|
$unrooted[sum] += c if l * 2 < sum
|
|
next if b >= BRANCH
|
|
$ra[sum] += c
|
|
(1...n).each {|m| tree(b, m, l, sum, c)}
|
|
end
|
|
end
|
|
|
|
def bicenter(s)
|
|
return if s.odd?
|
|
aux = $ra[s / 2]
|
|
$unrooted[s] += aux * (aux + 1) / 2
|
|
end
|
|
|
|
$ra = [0] * MAX_N
|
|
$unrooted = [0] * MAX_N
|
|
|
|
$ra[0] = $ra[1] = $unrooted[0] = $unrooted[1] = 1
|
|
for n in 1...MAX_N
|
|
tree(0, n)
|
|
bicenter(n)
|
|
puts "%d: %d" % [n, $unrooted[n]]
|
|
end
|