Travel on M-ary tree
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

有一颗高度为的满叉树,牛牛当前在结点。牛牛随机生成了一个长度为的结点序列,随后,牛牛按顺序依次遍历结点,最终停留在点(每次从一个结点走到另一个结点,牛牛都会沿最短路径行走)。定义一条路径的长度为路径上所经过的边的数量,求牛牛走的期望距离

输入描述:

输入包含输入包含组测试用例,第一行一个整数
每组测试用例三个整数

输出描述:

输出行,第行为第组测试用例的答案。
示例1

输入

复制
1
2 2 2

输出

复制
555555561

说明

{u_1=1,u_2=1}:dis=0
{u_1=1,u_2=2}:dis=1
{u_1=1,u_2=3}:dis=1
{u_1=2,u_2=1}:dis=2
{u_1=2,u_2=2}:dis=1
{u_1=2,u_2=3}:dis=3
{u_1=3,u_2=1}:dis=2
{u_1=3,u_2=2}:dis=3
{u_1=3,u_2=3}:dis=1
答案为{\frac{0+1+1+2+1+3+2+3+1}{9}=\frac{14}{9}}

备注: