【BZOJ4675】点对游戏

Description

桑尼、露娜和斯塔在玩点对游戏,这个游戏在一棵节点数为n的树上进行。
桑尼、露娜和斯塔三人轮流从树上所有未被占有的节点中选取一点,归为己有,轮流顺序为桑尼、露娜、斯塔、桑尼、露娜……。该选取过程直到树上所有点都被选取后结束。
选完点后便可计算每人的得分。点对游戏中有m个幸运数,在某人占据的节点中,每有一对点的距离为某个幸运数,就得到一分。(树上两点之间的距离定义为两点之间的简单路径的边数)
你的任务是,假设桑尼、露娜和斯塔每次选取时,都是从未被占有的节点中等概率选取一点,计算每人的期望得分。

Input

第一行两个整数n、m,分别表示树的节点数和幸运数的数目。
第二行m个互异正整数,表示m个幸运数。
以下n-1行,每行两个整数u、v,表示节点u和节点v之间有边。节点从1
到n编号。
3 <= n <= 50000, m <= 10,幸运数大小 <= n

Output

三行实数,分别表示桑尼、露娜和斯塔的期望得分,保留两位小数。

Sample Input

5 2
1 3
1 2
1 5
2 3
2 4

Sample Output

0.60
0.60
0.00

题解:本题的做法比较神。

先用点分治统计出所有幸运点对的个数,然后分别统计每个人都选出了多少个点对,用选出的点对数*幸运点对数/总点对数 即是答案。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=50010;
int sum;
int n,m,cnt,rt,mn,tot;
int to[maxn<<1],next[maxn<<1],head[maxn],dep[maxn],vis[maxn],siz[maxn],luck[20],f[maxn],g[maxn],md[maxn];
double ans[maxn],s[maxn];
void getrt(int x,int fa)
{
siz[x]=1;
int tmp=0;
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa&&!vis[to[i]])
getrt(to[i],x),siz[x]+=siz[to[i]],tmp=max(tmp,siz[to[i]]);
tmp=max(tmp,tot-siz[x]);
if(tmp<mn) mn=tmp,rt=x;
}
void getmd(int x,int fa,int dep)
{
siz[x]=1,md[x]=0;
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa&&!vis[to[i]])
getmd(to[i],x,dep+1),siz[x]+=siz[to[i]],md[x]=max(md[x],md[to[i]]+1);
}
void getdep(int x,int fa,int dep)
{
g[dep]++;
for(int i=1;i<=m;i++) if(dep<=luck[i]) sum+=f[luck[i]-dep];
for(int i=head[x];i!=-1;i=next[i]) if(to[i]!=fa&&!vis[to[i]]) getdep(to[i],x,dep+1);
}
void dfs(int x)
{
vis[x]=1;
getmd(x,0,0);
f[0]=1;
for(int i=head[x];i!=-1;i=next[i]) if(!vis[to[i]])
{
getdep(to[i],x,1);
for(int j=0;j<=md[to[i]]+1;j++) f[j]+=g[j],g[j]=0;
}
memset(f,0,sizeof(f[0])*(md[x]+2));
for(int i=head[x];i!=-1;i=next[i]) if(!vis[to[i]]) tot=siz[to[i]],mn=1<<30,getrt(to[i],x),dfs(rt);
}
inline void add(int a,int b)
{
to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
int main()
{
//freopen("game0.in","r",stdin);
//freopen("game.out","w",stdout);
n=rd(),m=rd();
int i,a,b;
for(i=1;i<=m;i++) luck[i]=rd();
memset(head,-1,sizeof(head));
for(i=1;i<n;i++) a=rd(),b=rd(),add(a,b),add(b,a);
tot=n,mn=1<<30,getrt(1,0),dfs(rt);
a=(n+2)/3,printf("%.2lf\n",1.0*a*(a-1)*sum/(1.0*n*(n-1)));
a=(n+1)/3,printf("%.2lf\n",1.0*a*(a-1)*sum/(1.0*n*(n-1)));
a=n/3,printf("%.2lf\n",1.0*a*(a-1)*sum/(1.0*n*(n-1)));
return 0;
}

最新文章

  1. Cinder 组件详解 - 每天5分钟玩转 OpenStack(47)
  2. 学习zepto.js(对象方法)[2]
  3. 在centos7中安装Robot Framework
  4. js类型检测
  5. Atitit.&#160;Atiposter&#160;发帖机 新特性 poster new feature v11 &#160;.docx
  6. XML真正强大的功能是来自其元素与封装的内容
  7. Rhel6-sersync配置文档
  8. ASP.NET MVC 开篇
  9. JPA 系列教程3-单向多对一
  10. Strategic Game
  11. BZOJ 1411&amp;&amp;Vijos 1544 : [ZJOI2009]硬币游戏【递推,快速幂】
  12. 【JAVA】SWING_ 界面风格
  13. 设置python爬虫IP代理(urllib/requests模块)
  14. 数据库索引使用数据结构及算法, 及MySQL不同引擎索引实现
  15. ELK-ElasticSearch索引详解
  16. 刷shipid 简便方法
  17. HDU 1556-Color the ball-树状数组
  18. Web开发——HTML基础(高级文本格式 列表/style)
  19. react 子元素修改父元素值的一个偏方,虽然简单,但是不建议用,
  20. 1066: 单词游戏(game)

热门文章

  1. JS -判断、监听屏幕横竖屏切换事件
  2. .Net并行编程高级教程(二)-- 任务并行
  3. JVM虚拟机(一):java虚拟机的基本结构
  4. WCF基础教程——vs2013创建wcf应用程序
  5. container_of学习笔记
  6. 如何让sublime text 2/3支持中文编码
  7. [elk]elastalert邮箱告警
  8. 安装Eclipse插件长时间卡在 calculating requirements and dependencies
  9. 将json形式的时间字符串转换成正常的形式
  10. Vue 混合