II.BZOJ4675: 点对游戏
（因为C++11的缘故在BZOJ上交会CE）
思路：
我们首先使用淀粉质找出所有长度为“幸运数”的路径数量，设为\(tot\)。然后，设\(f(x)\)表示\(x\)个点间所有的路径数量（即为\(\dfrac{x(x-1)}{2}\)），则答案即为\(\dfrac{tot\times f(x)}{f(n)}\)，其中\(x\)为某一个人分到的点的数量。因为是期望，所以是正确的。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,sz[50100],msz[50100],ROOT,SZ,buc[50100],dep[50100],tp,tot,a,b,c,luc[50100];
vector<int>v[50100];
bool vis[50100];
void getroot(int x,int fa){
sz[x]=1,msz[x]=0;
for(auto y:v[x])if(!vis[y]&&y!=fa)getroot(y,x),sz[x]+=sz[y],msz[x]=max(msz[x],sz[y]);
msz[x]=max(msz[x],SZ-sz[x]);
if(msz[x]<msz[ROOT])ROOT=x;
}
void getdis(int x,int fa,int DEP){
dep[++tp]=DEP;
for(auto y:v[x])if(!vis[y]&&y!=fa)getdis(y,x,DEP+1);
}
void calc(int x){
tp=0;
for(auto y:v[x]){
if(vis[y])continue;
int las=tp;
getdis(y,x,1);
for(int i=las+1;i<=tp;i++)for(int j=1;j<=m;j++)if(luc[j]>=dep[i])tot+=buc[luc[j]-dep[i]];
for(int i=las+1;i<=tp;i++)buc[dep[i]]++;
}
for(int i=1;i<=tp;i++)buc[dep[i]]=0;
}
void solve(int x){
calc(x),vis[x]=true;
for(auto y:v[x]){
if(vis[y])continue;
SZ=sz[y],ROOT=0,getroot(y,x),solve(ROOT);
}
}
double one;
int main(){
scanf("%d%d",&n,&m),buc[0]=1;
for(int i=1;i<=m;i++)scanf("%d",&luc[i]);
for(int i=1,x,y;i<n;i++)scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
msz[0]=0x3f3f3f3f,ROOT=0,SZ=n,getroot(1,0),solve(ROOT);
a=b=c=n/3;
if(a+b+c<n)a++;
if(a+b+c<n)b++;
one=1.0*tot/(1ll*n*(n-1)/2);
printf("%.2lf\n%.2lf\n%.2lf\n",one*a*(a-1)/2,one*b*(b-1)/2,one*c*(c-1)/2);
return 0;
}