今天切了一道期望dp的难(shui)题，写写这一道更难的题
YJC最近在学习图的有关知识。今天，他遇到了这么一个概念：随机游走。随机游走指每次从相邻的点中随机选一个走过去，重复这样的过程若干次。YJC很聪明，他很快就学会了怎么跑随机游走。为了检验自己是不是欧洲人，他决定选一棵树，每条边边权为1，选一对点s和t，从s开始随机游走，走到t就停下，看看要走多长时间。但是在走了10000000步之后，仍然没有走到t。YJC坚信自己是欧洲人，他认为是因为他选的s和t不好，即从s走到t的期望距离太长了。于是他提出了这么一个问题：给一棵n个点的树，问所有点对(i,j)(1≤i,j≤n)中，从i走到j的期望距离的最大值是多少。YJC发现他不会做了，于是他来问你这个问题的答案。
这个比今天的期望dp难多了，当时刚刚见到题直接懵逼
后来看着facico巨神的solution才渐渐搞明白了
简单说一说
我们假设f[x]为x走到父亲的期望步数，g[x]为父亲走到x的期望步数，d[x]为x的度数
我们可以列出一个方程:f[x]=1/d[x]+(1/d[x])*Σ(f[x]+f[v]+1){v∈son[x]}
解释一下，x随机游走有两种情况，一种是直接走到父亲，代价为1，一种是走到儿子再走到父亲
让后做化简可以得到(1/d[x])f[x]=1+(1/d[x])*Σ(f[v]){v∈son[x]}
所以 f[x]=d[x]+Σf[v]{v∈son[x]}
让后列出关于g[x]的方程，设p为x的父亲:
g[x]=1/d[p]+(1/d[p])*Σ(f[v]+g[x]+1){v∈son[p]&&v!=x}+(1/d[p])*(g[p]+g[x]+1)
p游走有三种情况，直接到x，到了v走回来再到x，到了p的父亲在走回来在走到x
化简得到g[x]=d[p]+Σf[v]{v∈son[p]&&v!=x}+g[p]
然而我们有f,g并没有什么卵用
我们还需要求出期望距离最长的路径
这个和求树的直径有点像（然而并不能dfs求）
我们对于每个子树，求出f,g的最长链和次长链
我们令df[x],rf[x]表示x所有子树v中f期望最长，次长的距离
dg[x]和rg[x]类似，是g期望最长距离
显然，df[x]=max(df[v]+f[v]),dg=max(dg[v]+g[v])
那么最后统计经过x的期望最长路径时就可以那dg和df加起来（如果同属于一个子树那就拿次长）
(z注意，本题期望没有要求取模，因为有一点是显然的，期望步数肯定是个整数!)
#include<stdio.h>
#include<algorithm>
#define N 100010
using namespace std;
struct Edge{ int v,nt; } G[N*2];
long long s[N],f[N],g[N],df[N],dg[N],rf[N],rg[N],ans=0;
int vf[N],vg[N],h[N],d[N],n,c=0;
inline void adj(int x,int y){
G[++c]=(Edge){y,h[x]}; h[x]=c;
}
void dfs(int x,int p){
s[x]=0;
for(int v,i=h[x];i;i=G[i].nt)
if((v=G[i].v)!=p){
dfs(v,x);
s[x]+=f[v];
}
f[x]=s[x]+d[x];
}
void dgs(int x,int p){
for(int v,i=h[x];i;i=G[i].nt)
if((v=G[i].v)!=p){
g[v]=g[x]+s[x]-f[v]+d[x];
dgs(v,x);
}
}
void dijk(int x,int p){
for(int v,i=h[x];i;i=G[i].nt)
if((v=G[i].v)!=p){
dijk(v,x);
if(f[v]+df[v]>df[x]){
rf[x]=df[x];
df[x]=f[v]+df[v];
vf[x]=v;
} else if(f[v]+df[v]>rf[x]) rf[x]=f[v]+df[v];
if(g[v]+dg[v]>dg[x]){
rg[x]=dg[x];
dg[x]=g[v]+dg[v];
vg[x]=v;
} else if(g[v]+dg[v]>rg[x]) rg[x]=g[v]+dg[v];
}
if(vf[x]!=vg[x]) ans=max(ans,df[x]+dg[x]);
else ans=max(ans,max(df[x]+rg[x],dg[x]+rf[x]));
}
int main(){
freopen("rw.in","r",stdin);
freopen("rw.out","w",stdout);
scanf("%d",&n);
for(int x,y,i=1;i<n;++i){
scanf("%d%d",&x,&y);
adj(x,y); adj(y,x); d[x]++; d[y]++;
}
dfs(1,0);
dgs(1,0);
dijk(1,0);
printf("%lld.00000
",ans);
}