【JZOJ4890】【NOIP2016提高A组集训第14场11.12】随机游走

题目描述

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

数据范围

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

解法

预处理出每条边的期望长度；
然后树形动态规划。

代码

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#define ll long long
using namespace std;
const char* fin="rw.in";
const char* fout="rw.out";
const int inf=0x7fffffff;
const int maxn=100007,maxm=maxn*2;
int n,i,j,k;
int fi[maxn],la[maxm],ne[maxm],tot;
int f[maxn],g[maxn];
int h[maxn][4],ans,id[maxn][4];
void add_line(int a,int b){
    tot++;
    ne[tot]=fi[a];
    la[tot]=b;
    fi[a]=tot;
}
void getf(int v,int from){
    int i,j=0,k;
    for (k=fi[v];k;k=ne[k]) j++;
    f[v]=j;
    for (k=fi[v];k;k=ne[k])
        if (la[k]!=from){
            getf(la[k],v);
            f[v]+=f[la[k]];
        }
}
void getg(int v,int from){
    int i,j=0,k;
    for (k=fi[v];k;k=ne[k])
        if (la[k]!=from) j+=1+f[la[k]];
        else j+=1+g[v];
    for (k=fi[v];k;k=ne[k])
        if (la[k]!=from){
            g[la[k]]=j-f[la[k]];
            getg(la[k],v);
        }
}
void dfs(int v,int from){
    int i,j,k;
    h[v][0]=h[v][1]=h[v][2]=h[v][3]=0;
    for (k=fi[v];k;k=ne[k])
        if (la[k]!=from){
            dfs(la[k],v);
            i=g[la[k]]+h[la[k]][0];
            j=f[la[k]]+h[la[k]][1];
            if (i>h[v][0]){
                id[v][0]=la[k];
                h[v][2]=h[v][0];
                h[v][0]=i;
            }else h[v][2]=max(h[v][2],i);
            if (j>h[v][1]){
                id[v][1]=la[k];
                h[v][3]=h[v][1];
                h[v][1]=j;
            }else h[v][3]=max(h[v][3],j);
        }
    if (id[v][0]!=id[v][1]) ans=max(ans,h[v][0]+h[v][1]);
    else ans=max(ans,max(h[v][0]+h[v][3],h[v][2]+h[v][1]));
}
int main(){
    freopen(fin,"r",stdin);
    freopen(fout,"w",stdout);
    scanf("%d",&n);
    for (i=1;i<n;i++){
        scanf("%d%d",&j,&k);
        add_line(j,k);
        add_line(k,j);
    }
    getf(1,0);
    getg(1,0);
    dfs(1,0);
    printf("%d.00000",ans);
    return 0;
}

启发

从固定长度开始推期望值。