1989: Bonus 奖励计划
数学期望。
总费用=所有边的平均费用和
每条边的费用=被优惠且走过的概率*长度，因为长度都是1，所以就是概率。
被优惠且走过的概率=优惠路径中包含这条边的概率*走过这条边的概率。
=（总包含这条边的路径数/总路径数）^2
包含的路径数用两边的点数乘起来就行了。
[toggle title="code"]
[pascal]
var
n,i,j,k,ee:longint;
sum,an,ans:double;
now:int64;
v,u,next,e,size,head:array[1..20000]of longint;
procedure dfs(u:longint);
var j:longint;
begin
size[u]:=1;
j:=head[u];
while j<>0 do
begin
if size[e[j]]=0 then
begin
dfs(e[j]);
inc(size[u],size[e[j]]);
end;
j:=next[j];
end;
end;
procedure add(u,v:longint);
begin
inc(ee);next[ee]:=head[u];head[u]:=ee;e[ee]:=v;
end;
begin
readln(n);
for i:=1 to n-1 do
begin
readln(u[i],v[i]);
add(u[i],v[i]); add(v[i],u[i]);
end;
dfs(1);
sum:=n*(n-1)/2;
for i:=1 to n-1 do
begin
if size[u[i]]>size[v[i]] then
now:=size[v[i]]*(n-size[v[i]])
else
now:=size[u[i]]*(n-size[u[i]]);
an:=now/sum;
an:=an*an;
ans:=ans+an;
end;
writeln(ans:0:6);
end.
[/pascal]
[/toggle]
-------------------------------------------------------------------------
花有重开日，人无再少年