Codeforces 804D Expected diameter of a tree（树形DP+期望）

【题目链接】 http://codeforces.com/contest/804/problem/D

【题目大意】

　　给你一个森林，每次询问给出u,v，
　　从u所在连通块中随机选出一个点与v所在连通块中随机选出一个点相连，
　　问你此时相连出的树的直径期望是多少？（如果本身就在同一个连通块内，则输出-1）

【题解】

　　我们利用树形dp记录每个点属于的连通块，
　　以及每个点到不同分支最远点的距离，记为mxd[i]
　　一遍搜索计算出向下最远，再次搜索的时候得到向上最远即可。
　　得到各个分支的最远距离之后，我们将其进行排序，
　　通过最远和次远分支计算是否可能成为树的直径，更新所属树的直径的答案diam。
　　考虑连接u和v所属的树X和树Y，
　　如果连接是点x和点y，那么所做的期望贡献就是max(mxdx+mxdy+1,diamX,diamY),
　　考虑枚举每个mxdx和mxdy得到组合来计算期望复杂度过高，我们考虑优化，
　　我们发现当mxdx+mxdy<max(diamX,diamY)的时候，期望均为max(diamX,diamY)
　　那么对于mxdx，我们在mxdy的有序集合Disy中分治查找max(diamX,diamY)-mxdx的位置，
　　就得到对于mxdx来说贡献为max(diamX,diamY)的数量，大于部分则直接求和即可，
　　我们预处理每个有序集Dis的后缀和，以减少求和的复杂度。
　　计算出期望之后，考虑到可能有多组点计算的是同一对树，因此我们用map对答案进行记忆化。

【代码】

#include <cstdio>

#include <algorithm>

#include <utility>

#include <map>

#include <vector>

#include <cstring>

using namespace std;

const int N=100010;

typedef long long LL;

vector<int> v[N];  // 邻接表

vector<int> dis[N]; // 该点各个分支的最远距离

int cc[N],cn; // 从属的连通块编号

int mxd[N],diam[N]; // 到树的最远距离和树的直径

vector<int> Dis[N]; // 每个连通块中各点到树的最远距离集

vector<int> sum[N];

int dfs(int x,int fx){

    cc[x]=cn;

    int Dist=0;

    for(int i=0;i<v[x].size();i++){

        int y=v[x][i];

        if(y==fx)continue;

        dis[x][i]=dfs(y,x)+1;

        Dist=max(Dist,dis[x][i]);

    }return Dist;

}

void dfs2(int x,int fx,int Dis){

    for(int i=0;i<v[x].size();i++){

        int y=v[x][i];

        if(y!=fx)continue;

        dis[x][i]=Dis+1;

    }if(dis[x].size()==0){mxd[x]=0;diam[cc[x]]=0;return;}

    vector<pair<int,int> > Dists(dis[x].size());

    for(int i=0;i<Dists.size();i++)Dists[i]=make_pair(dis[x][i],i);

    sort(Dists.rbegin(),Dists.rend());

    mxd[x]=Dists[0].first;

    diam[cc[x]]=max(mxd[x],diam[cc[x]]);

    if(Dists.size()>1)diam[cc[x]]=max(diam[cc[x]],Dists[0].first+Dists[1].first);

    for(int i=0;i<v[x].size();i++){

        int y=v[x][i];

        if(y==fx)continue;

        if(Dists[0].second!=i)dfs2(y,x,Dists[0].first);

        else if(Dists.size()>1)dfs2(y,x,Dists[1].first);

        else dfs2(y,x,0);

    }

}

LL cal(int x,int y){

    if(Dis[x].size()>Dis[y].size())swap(x,y);

    LL ans=0;

    int mxdiam=max(diam[x],diam[y]);

    for(int i=0;i<Dis[x].size();i++){

        LL len=lower_bound(Dis[y].begin(),Dis[y].end(),mxdiam-Dis[x][i])-Dis[y].begin();

        ans+=len*mxdiam+(Dis[y].size()-len)*(Dis[x][i]+1)+sum[y][len];

    }return ans;

}

void init(){

    memset(cc,0,sizeof(cc));

    memset(v,0,sizeof(v));

    memset(dis,0,sizeof(dis));

    memset(Dis,0,sizeof(Dis));

    memset(sum,0,sizeof(sum));

}

int n,m,q;

int main(){

    while(~scanf("%d%d%d",&n,&m,&q)){

        init();

        for(int i=0;i<m;i++){

            int x,y;

            scanf("%d%d",&x,&y);

            v[x].push_back(y);

            v[y].push_back(x);

            dis[x].push_back(-1);

            dis[y].push_back(-1);

        }cn=0;

        for(int i=1;i<=n;i++)if(!cc[i]){++cn;dfs(i,-1);dfs2(i,-1,0);}

        for(int i=1;i<=n;i++)Dis[cc[i]].push_back(mxd[i]);

        for(int i=1;i<=cn;i++){

            sort(Dis[i].begin(),Dis[i].end());

            sum[i].resize(Dis[i].size()+1);

            sum[i][Dis[i].size()]=0;

            for(int j=Dis[i].size()-1;j>=0;j--)sum[i][j]=sum[i][j+1]+Dis[i][j];

        }

        map<pair<int,int>,double> dp;

        while(q--){

            int x,y;

            scanf("%d%d",&x,&y);

            x=cc[x],y=cc[y];

            if(x==y){puts("-1");continue;}

            if(dp.count(make_pair(x,y))==1)printf("%0.9lf\n",dp[make_pair(x,y)]);

            else{

                LL t=cal(x,y),u=(LL)Dis[x].size()*Dis[y].size();

                double ans=(double)t/u;

                printf("%0.9lf\n",ans);

                dp[make_pair(x,y)]=ans;

            }

        }

    }return 0;

}

巴特西

Codeforces 804D Expected diameter of a tree（树形DP+期望）

最新文章

热门文章