描述

Description

YJC最近在学习图的有关知识。今天，他遇到了这么一个概念：随机游走。随机游走指每次从相邻的点中随机选一个走过去，重复这样的过程若干次。YJC很聪明，他很快就学会了怎么跑随机游走。为了检验自己是不是欧洲人，他决定选一棵树，每条边边权为1，选一对点s和t，从s开始随机游走，走到t就停下，看看要走多长时间。但是在走了10000000步之后，仍然没有走到t。YJC坚信自己是欧洲人，他认为是因为他选的s和t不好，即从s走到t的期望距离太长了。于是他提出了这么一个问题：给一棵n个点的树，问所有点对(i,j)(1≤i,j≤n)中，从i走到j的期望距离的最大值是多少。YJC发现他不会做了，于是他来问你这个问题的答案。

Input

第一行包含一个整数n，表示点数。
接下来n-1行，第(i+1)行包含两个整数ui和vi，表示树的一条边。

Output

输出一行，包含一个实数，表示最大的期望距离，保留五位小数。

Sample Input

3
1 2
2 3

Sample Output

4.00000

Data Constraint

对于30%的数据，满足n≤5。
对于50%的数据，满足n≤3000。
对于100%的数据，满足n≤100000。

Hint

s=1，t=3，从1走到2距离为1，从2走到3的期望距离d满足d=0.5(d+2)+0.5，解得d=3，所以从1走到3的期望距离为4。

分析

首先普及一下期望是什么东西。

如果第i个状况的概率为p[i]，所花的代价为w[i]，那么期望e是

e = \sum p [i] * w [i]

期望具有一些奇怪的性质。

在这一题中，如果从X到Y的期望距离为a，从Y到Z的期望距离为b，那么从X到Z的期望距离为a+b

但其实我也不知道是为什么。

首先我们知道，这是一棵树。这意味着两个点之间有且只有一条路径。

所以可以设f[x]表示从x到x的父亲的期望距离，g[x]表示从x的父亲到x的期望距离。

求出f和g后就可以随意地求出两点之间的期望距离了。

考虑树形DP。设d[x]表示x的度（即与其相连的边）

先求f[x]

分两种情况：

1. x直接跳上x的父亲

2. x跳到x的儿子，经过乱跳后跳回x，再乱跳跳到x的父亲

f [x] = 1 d [ x ] * 1 + (\sum s o n 1 d [ x ] * (1 + f [s o n] + f [x]))

第二种情况中，跳到son距离为1，从son跳回来距离为f[son]，再跳上去距离为f[x]

因为左右都有f[x]，我们应将f[x]移到左边。

可以手推一下，就变成下面这个式子

f [x] = d [x] + \sum s o n f [s o n]

再求g

分三种情况：

1. x的父亲直接跳到x

2. x的父亲跳到x的爷爷，再乱跳到x的父亲，再乱跳到x

3. x的父亲跳到x的兄弟，再乱跳回x的父亲，再乱跳到x

g [x] = 1 d [ f a t h e r ] * 1 + 1 d [ f a t h e r ] * (1 + g [f a t h e r] + g [x]) + (\sum b r o t h e r 1 d [ f a t h e r ] * (1 + f [b r o t h e r] + g [x]))

原因差不多了，仔细想一下就行了。

可以化简为

g [x] = d [f a t h e r] + g [f a t h e r] + \sum b r o t h e r f [b r o t h e r]

求f和g，分别用两个递归就能很方便地O(n)求出了。

接下来就很好搞了，类似于求一棵树的直径。若从X到Y，那么路径就是X->LCA(X,Y)->Y

设x.fu表示从x的某个后代到x的最长距离，x.su是次长距离。

x.fd表示从x到某个后代的最长距离，x.sd是次长距离。

求上面的那四个东西只要统计son.fu+f[son]和g[son]+son.fd，求最长和次长。

如果x.fu和x.fd不重复，自然是x.fu+x.fd最长

否则最长为max{x.fu+x.sd,x.su+x.fd}

这样又一个递归，可以O(n)求出。

取个最大值，就是答案了。

代码

#include 
    
     #include 
     
      #include 
      
       using namespace std;int n;struct EDGE{    int to;    EDGE* las;} e[200000];//前向星存边EDGE* last[100001];int d[100001];//d[x]为x的度long long ans;long long f[100001],sum[100001],g[100001];//sum[x]=sum{f[son]}用于省去dfs2中算f[brother]之和的部分void dfs1(int,int);//求fvoid dfs2(int,int);//求gstruct First_and_Second{    long long fu;    int nfu;//这个是fu的编号，用于判断重复    long long fd;    int nfd;//这个是fd的编号，用于判断重复    long long su,sd;    //次大的编号是没有必要标的，因为不需判断fu与sd或su与fd重复，不然fu就不会与fd重复，不影响答案} s[100001];void dfs3(int,int);//求答案int main(){    freopen("rw.in","r",stdin);    freopen("rw.out","w",stdout);    scanf("%d",&n);    int i,j=-1,x,y;    for (i=1;i
       
        las)        if (ei->to!=fa)        {            dfs1(x,ei->to);            sum[x]+=f[ei->to];        }    f[x]=d[x]+sum[x];//方程原因见上}void dfs2(int fa,int x){    EDGE* ei;    for (ei=last[x];ei;ei=ei->las)        if (ei->to!=fa)        {            g[ei->to]=d[x]+g[x]+sum[x]-f[ei->to];//方程原因见上。            dfs2(x,ei->to);        }}void dfs3(int fa,int x){    EDGE* ei;    for (ei=last[x];ei;ei=ei->las)        if (ei->to!=fa)        {            dfs3(x,ei->to);            if (s[ei->to].fu+f[ei->to]>s[x].fu)//和最大作比较            {                s[x].su=s[x].fu;                s[x].fu=s[ei->to].fu+f[ei->to];                s[x].nfu=ei->to;            }            else if (s[ei->to].fu+f[ei->to]>s[x].su)//和次大作比较                s[x].su=s[ei->to].fu+f[ei->to];            if (g[ei->to]+s[ei->to].fd>s[x].fd)//同上            {                s[x].sd=s[x].fd;                s[x].fd=g[ei->to]+s[ei->to].fd;                s[x].nfd=ei->to;            }            else if (g[ei->to]+s[ei->to].fd>s[x].sd)//同上                s[x].sd=g[ei->to]+s[ei->to].fd;        }    if (s[x].nfu!=s[x].nfd)        ans=max(ans,s[x].fu+s[x].fd);    else        ans=max(ans,max(s[x].fu+s[x].sd,s[x].su+s[x].fd));  //原因见上    //有的人可能担心nfu和nfd恰好一样，但可能还会有等于fu或fd的路程。实际上，如果有这种可能，那么有su=fu或sd=fd，不会影响答案。    //如果x只有一个儿子，那么必有nfu==nfd，由于su和sd为0，所以不会影响答案。}