题目
YJC最近在学习图的有关知识。今天，他遇到了这么一个概念：随机游走。随机游走指每次从相邻的点中随机选一个走过去，重复这样的过程若干次。YJC很聪明，他很快就学会了怎么跑随机游走。为了检验自己是不是欧洲人，他决定选一棵树，每条边边权为1，选一对点s和t，从s开始随机游走，走到t就停下，看看要走多长时间。但是在走了10000000步之后，仍然没有走到t。YJC坚信自己是欧洲人，他认为是因为他选的s和t不好，即从s走到t的期望距离太长了。于是他提出了这么一个问题：给一棵n个点的树，问所有点对(i,j)(1≤i,j≤n)中，从i走到j的期望距离的最大值是多少。YJC发现他不会做了，于是他来问你这个问题的答案。
分析
套路：
首先知道期望是可以累加的，即i通过j去到k的期望，等于i去到j的期望加j去到k的期望。
所以令d[i]表示i的出度，F[i]表示从i到i的父亲的期望，G[i]表示i的父亲到i的期望，j表示i其中任意一个儿子，k表示i的父亲，l表示k其中任意一个儿子，e表示k的父亲。
很容易推出：
\[F[i]=\dfrac{1}{d[i]}+\dfrac{1}{d[i]}\sum(1+F[j]+F[i])
\]
\[G[i]=\dfrac{1}{d[k]}+\dfrac{1}{d[k]}(1+G[k]+G[i])+\dfrac{1}{d[k]}\sum(1+F[l]+G[i])
\]
简化后得
\[F[i]=\sum{F[j]}+d[i]
\]
\[G[i]=G[k]+\sum{F[l]}+d[k]
\]
枚举(i,j)的lca，
记录在以lca为根的子树中，
从lca出发，和到达lca的最大期望值，
为了防止两个最大值的lca不是枚举了lca，记录枚举儿子中的最大值，
取最大次大值比较。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
const int mo=1000000007;
const int N=100005;
using namespace std;
int f[N],g[N];
int n,m,next[N*3],last[N*3],to[N*3],d[N],tot,deep[N],mx[N*2][8],ans;
int bj(int x,int y)
{
next[++tot]=last[x];
last[x]=tot;
to[tot]=y;
}
int dg(int x,int fa)
{
f[x]=d[x];
for(int i=last[x];i;i=next[i])
{
int j=to[i];
if(j!=fa)
{
deep[j]=deep[x]+1;
dg(j,x);
f[x]+=f[j];
}
}
}
int dg1(int x,int fa)
{
int sum1f=0;
for(int i=last[x];i;i=next[i])
{
int j=to[i];
if(j!=fa)
{
g[j]+=g[x]+d[x];
sum1f+=f[j];
}
}
for(int i=last[x];i;i=next[i])
{
int j=to[i];
if(j!=fa)
{
g[j]+=sum1f-f[j];
dg1(j,x);
}
}
}
int dg2(int x,int fa)
{
for(int i=last[x];i;i=next[i])
{
int j=to[i];
if(j!=fa)
{
dg2(j,x);
if(mx[j][0]+f[j]>=mx[x][0])
{
mx[x][1]=mx[x][0];
mx[x][0]=mx[j][0]+f[j];
mx[x][5]=mx[x][4];
mx[x][4]=j;
}
else
if(mx[j][0]+f[j]>mx[x][1])
{
mx[x][1]=mx[j][0]+f[j];
mx[x][5]=j;
}
if(mx[j][2]+g[j]>=mx[x][2])
{
mx[x][3]=mx[x][2];
mx[x][2]=mx[j][2]+g[j];
mx[x][7]=mx[x][6];
mx[x][6]=j;
}
else
if(mx[j][2]+g[j]>mx[x][3])
{
mx[x][3]=mx[j][2]+g[j];
mx[x][7]=j;
}
}
}
if(mx[x][4]!=mx[x][6])
{
if(mx[x][0]+mx[x][2]>ans) ans=mx[x][0]+mx[x][2];
}
if(mx[x][5]!=mx[x][6])
{
if(mx[x][1]+mx[x][2]>ans) ans=mx[x][1]+mx[x][2];
}
if(mx[x][4]!=mx[x][7])
{
if(mx[x][0]+mx[x][3]>ans) ans=mx[x][0]+mx[x][3];
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
{
int x,y;
scanf("%d%d",&x,&y);
d[x]++;
d[y]++;
bj(x,y);
bj(y,x);
}
deep[1]=1;
dg(1,0);
dg1(1,0);
dg2(1,0);
printf("%d.00000",ans);
}
