Expected diameter of a tree

Expected diameter of a tree

关键

1.记忆化暴力，不然会T，记忆化的话，复杂度是开根号
2.虽然是求期望，但是不是传统的期望dp，而是枚举所有的组合，只是统计答案的时候采用了一些优化
3.用小的匹配大的，可以保证复杂度
4.每个点距离最远的点，一定是直径的两个点之一
5.多次dfs，找dep和far

代码

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
const int M=1e5+5;

int h[M],ne[M<<1],e[M<<1],tot;
void add(int from,int to) {
    e[++tot]=to;  ne[tot]=h[from];  h[from]=tot;
    e[++tot]=from;ne[tot]=h[to];    h[to]=tot;
}

vector<int>v[M],sum[M];
bool vis[M];
int id[M],dep[M],far[M],mx[M],rot,cnt;
void dfs(int now,int fa,bool t) {
    if(t)vis[now]=1,id[now]=cnt,v[cnt].push_back(now);
    else if(dep[now]>far[now])far[now]=dep[now];
    if(dep[now]>dep[rot])rot=now;
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        if(to==fa)continue;
        dep[to]=dep[now]+1;
        dfs(to,now,t);
    }
}

void init(int now,int fa) {
    dep[now]=0;
    for(int i=h[now];i;i=ne[i]) {
        int to=e[i];
        if(to==fa)continue;
        init(to,now);
    }
}

bool cmp(int x,int y) {
    return far[x]<far[y];
}

//能够到达的最远的点，一定是直接上的两个点之一
//走两次dfs，找到最远的两个点，期间只需要将p进行 调换一下子就可以了，看dep进行变换
//每一次变换之后需要进行清空
//找到两个最远的点之后，就找每个点最远的点，一共三次dfs,并且记录最大far
//对far进行排序，并且记录后缀和
void go(int x) {
    cnt++;
    rot=x;
    dfs(x,0,1);init(x,0);
    dfs(rot,0,0);init(rot,0);
    dfs(rot,0,0);init(rot,0);
    mx[cnt]=far[rot];
    sort(v[cnt].begin(),v[cnt].end(),cmp);
    for(int i=0;i<=v[cnt].size();i++)sum[cnt].push_back(0);
    for(int i=v[cnt].size()-1;i>=0;i--)
        sum[cnt][i]=sum[cnt][i+1]+far[v[cnt][i]];
}
map<pii,double>mp;

int solve(int x,int y,int t) {
    int l=0,r=v[y].size(),ans=r+1;
    while(l<=r) {
        int mid=(l+r)>>1;
        if(x+far[v[y][mid]]+1>t)ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}

int main() {
    int n,m,q;
    cin>>n>>m>>q;
    while(m--) {
        int x,y;
        cin>>x>>y;
        add(x,y);
    }
    for(int i=1;i<=n;i++)
        if(vis[i]==0)go(i);
    while(q--) {
        int x,y;
        cin>>x>>y;
        x=id[x],y=id[y];
        if(v[x].size()>v[y].size())swap(x,y);//用小的匹配大的
        if(x==y)cout<<"-1\n";
        else if(mp.count({x,y}))printf("%.10lf\n",mp[{x,y}]);//记忆化
        else {
            double ans=0;
            for(int i=0;i<v[x].size();i++) {//二分处理
                int p=solve(far[v[x][i]],y,max(mx[x],mx[y]));
                //求出，再那个点以后，就是我们两的距离直接相加
                ans+=1.0*p*max(mx[x],mx[y])+1.0*(v[y].size()-p)*(far[v[x][i]]+1)+1.0*sum[y][p];
            }
            ans/=1.0*v[x].size()*v[y].size();//除上总的方案数
            printf("%.10lf\n",mp[{x,y}]=ans);
        }
    }
    return 0;
}
//很多时候都可以用暴力的记忆化