题解：

还好。。。看懂题目就好做了。（Orzdyh）

首先选择的点是等概率随机的，也就是说每种选择结果的概率都是一样的，所以选择一个点的时候已经选择的点不会有影响，那么就可以直接算出点对个数再求总体的期望。具体来说，每条边会在$\binom{n-2}{\lceil\frac{n}{3}\rceil -1}$种情况中被选择（说不清楚，感性理解一下），再除以总的情况数$\binom{n}{\lceil\frac{n}{3}\rceil}$即可，这一步可以约分，注意要对$n\mod 3$的余数分类讨论。

前面的部分是点分治经典应用，就不说了。我貌似写的很挫，第一次有三个点T了20ms，其他人一共就跑了20ms。。。第二次加了读入优化999ms过了。。。妙不可言

代码：

 #include<algorithm>

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #define inf 2147483647

 #define eps 1e-9

 using namespace std;

 typedef long long ll;

 struct edge{

     int v,next;

 }a[];

 int n,m,u,v,lk[],anss[],sum=,S,rt,tot=,cnt=,head[],siz[],mx[],dis[];

 bool used[];

 double ans1,ans2;

 char buffer[],*hd,*tl;

 inline char Getchar(){

     if(hd==tl){

         int len=fread(buffer,,,stdin);

         hd=buffer,tl=hd+len;

         if(hd==tl)

             return EOF;

     }

     return *hd++;

 }

 inline int rd(){

     register int x=;

     char c;

     do c=Getchar();

     while(!isdigit(c));

     do{

         x=(x<<)+(x<<)+(c^);

         c=Getchar();

     }while(isdigit(c));

     return x;

 }

 inline void add(int u,int v){

     a[++tot].v=v;

     a[tot].next=head[u];

     head[u]=tot;

 }

 inline void dfsrt(int u,int ff){

     siz[u]=;

     mx[u]=;

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         int v=a[tmp].v;

         if(v!=ff&&!used[v]){

             dfsrt(v,u);

             mx[u]=max(mx[u],siz[v]);

             siz[u]+=siz[v];

         }

     }

     mx[u]=max(mx[u],S-siz[u]);

     if(mx[u]<mx[rt])rt=u;

 }

 inline void getdis(int u,int fa,int ds){

     dis[++cnt]=ds;

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         int v=a[tmp].v;

         if(v!=fa&&!used[v])getdis(v,u,ds+);

     }

 }

 inline int gao1(int l,int r,int k){

     int ret=-;

     while(l<=r){

         int mid=(l+r)/;

         if(dis[mid]==k)ret=mid,l=mid+;

         else if(dis[mid]<k)l=mid+;

         else r=mid-;

     }

     return ret;

 }

 inline int gao2(int l,int r,int k){

     int ret=;

     while(l<=r){

         int mid=(l+r)/;

         if(dis[mid]==k)ret=mid,r=mid-;

         else if(dis[mid]<k)l=mid+;

         else r=mid-;

     }

     return ret;

 }

 inline int calc(int u,int w,int K){

     cnt=;

     getdis(u,,w);

     sort(dis+,dis+cnt+);

     //for(int i=1;i<=cnt;i++)printf("%d ",dis[i]);

     //printf("\n");

     int ret=;

     for(int i=;i<=cnt;i++){

         if(dis[i]*>K)break;

         ret+=gao1(i,cnt,K-dis[i])-gao2(i,cnt,K-dis[i])+;

     }

     return ret;

 }

 inline void divide(int u){

     used[u]=true;

     for(int i=;i<=m;i++)anss[i]+=calc(u,,lk[i]);

     for(int tmp=head[u];tmp!=-;tmp=a[tmp].next){

         int v=a[tmp].v;

         if(!used[v]){

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

                 anss[i]-=calc(v,,lk[i]);

             }

             S=siz[v],rt=;

             dfsrt(v,);

             divide(rt);

         }

     }

 }

 int main(){

     memset(head,-,sizeof(head));

     memset(anss,,sizeof(anss));

     //scanf("%d%d",&n,&m);

     n=rd(),m=rd();

     for(int i=;i<=m;i++)lk[i]=rd();//scanf("%d",&lk[i]);

     for(int i=;i<n;i++){

         //scanf("%d%d",&u,&v);

         u=rd();

         v=rd();

         add(u,v);

         add(v,u);

     }

     S=n,mx[rt=]=;

     dfsrt(,);

     divide(rt);

     //for(int i=1;i<=m;i++)printf("%d ",anss[i]);

     for(int i=;i<=m;i++)sum+=anss[i];

     if(n%==||n%==){

         ans1=(double)((double)sum*(n/)*(n/+))/(double)((double)n*(n-));

         if(n%==)printf("%.2lf\n",ans1);

         else printf("%.2lf\n%.2lf\n",ans1,ans1);

     }

     ans2=(double)((double)sum*(n/)*(n/-))/(double)((double)n*(n-));

     if(n%==)printf("%.2lf\n%.2lf\n%.2lf",ans2,ans2,ans2);

     else if(n%==)printf("%.2lf\n%.2lf",ans2,ans2);

     else printf("%.2lf",ans2);

     return ;

 }

巴特西

（WC2018模拟十二）【FJOI2016集训Day7T2】点对游戏

题解：

代码：

最新文章

热门文章