思路:发现如果一个人一共选了x个点，那么选中某一个点对的概率都是一样的，一个人选x个点的总方案是C(n,x)，一个人选中某个点对的总方案是C(n-2,x-2)，这样，那么选中某个点对的概率就是 x*(x-1)/（n*(n-1)），这样，我们就用树分治求出有多少对符合条件的对数，然后乘上每个人的概率即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #define inf 0x7fffffff 7 int son[200005],F[200005],root,vis[200005],pd[200005],c[200005]; 8 int n,go[200005],tot,first[200005],next[200005],dis[200005],num,sz,m,b[200005]; 9 int ans,cnt[200005];10 double Ans;11 int read(){12     int t=0,f=1;char ch=getchar();13     while (ch<'0'||ch>'9'){
   if (ch=='-')f=-1;ch=getchar();}14     while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();}15     return t*f;16 }17 void insert(int x,int y){18     tot++;19     go[tot]=y;20     next[tot]=first[x];21     first[x]=tot;22 }23 void add(int x,int y){24     insert(x,y);insert(y,x);25 }26 void findroot(int x,int fa){27     son[x]=1;F[x]=0;28     for (int i=first[x];i;i=next[i]){29         int pur=go[i];30         if (vis[pur]||pur==fa) continue;31         findroot(pur,x);32         son[x]+=son[pur];33         F[x]=std::max(F[x],son[pur]);34     }35     F[x]=std::max(F[x],num-son[x]);36     if (F[x]
          
           =dis[c[i]])53 ans+=cnt[b[j]-dis[c[i]]];54 for (int i=1;i<=t;i++)55 cnt[dis[c[i]]]++; 56 }57 void solve(int x,int fa){58 vis[x]=1;sz++;59 memset(cnt,0,sizeof cnt);cnt[0]=1;60 for (int i=first[x];i;i=next[i]){61 int pur=go[i];62 if (vis[pur]) continue;63 bfs(pur);64 }65 int Sum=num;66 for (int i=first[x];i;i=next[i]){67 int pur=go[i];68 if (vis[pur]) continue;69 if (son[pur]>son[x]) num=Sum-son[x];70 else num=son[pur];71 root=0;72 findroot(pur,0);73 solve(root,x);74 }75 }76 int main(){77 n=read();m=read();78 for (int i=1;i<=m;i++){79 b[i]=read();80 }81 std::sort(b+1,b+1+m);82 for (int i=1;i