Codeforces 280C - Game on Tree
2024-08-27 17:53:57
不知道期望是啥的请自行Baidu或Google,(溜了
题目大意,有一棵有根树,每次随机选择一个节点,将这个节点和它的子树删除,问将整棵树删除的期望次数
那我们就来想,如果要计算一个节点的期望的话每个节点和它的祖先是在决策范围内的,所以它的子树我们可以先不用管,需要预处理出每一个点有几个祖先,当然还要加上它本身
因为每一个点的随机变量都是1,所以只需要将概率计算出来求一个和就行,注意题目要求控制精度了。
代码(:逃
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; const int MAXN = (int(1e5)+3)*2; int N, F[MAXN];
double Ans;
int u[MAXN], v[MAXN], first[MAXN], next[MAXN]; inline int read() {
int x = 0, f = 1;
char c = getchar();
while(c < '0'||c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c <= '9'&&c >= '0') {
x = x*10+c-'0';
c = getchar();
}
return x * f;
} void dfs(int x, int from) {
int k = first[x];
while(k != -1) {
if(v[k] == from) {k = next[k]; continue;}
F[v[k]] = F[u[k]]+1;
dfs(v[k], u[k]);
k = next[k];
}
} int main() {
N = read();
memset(first, -1, sizeof(first));
for(int i=1; i<=(N-1)*2; i++) {
u[i] = read(), v[i] = read();
next[i] = first[u[i]];
first[u[i]] = i;
i++;
u[i] = v[i-1], v[i] = u[i-1];
next[i] = first[u[i]];
first[u[i]] = i;
}
F[1] = 1;
dfs(1, 0);
for(int i=1; i<=N; i++) {
Ans += 1.0/double(F[i]);
}
printf("%.10lf", Ans);
}
最新文章
- ubuntu14 查找并删除所有文件名中带有特定关键词的文件
- Oracle --获取绑定变量的值.
- C# 内存信息
- sdut 2449走迷宫【最简单的dfs应用】
- 【BZOJ1208】[HNOI2004]宠物收养所 Splay
- OC面向对象—继承
- iOS 内存管理(一)之基础知识介绍
- for name in loop Shell
- spring batch学习笔记
- bzoj 2002 [Hnoi2010]Bounce 弹飞绵羊(LCT)
- PHP生成压缩文件开发实例
- 选择服务器OS标准
- Java中线程池的学习
- 3分钟利用TurnipBit制作电子时钟
- Asp.net mvc 5 razor
- [Swift]LeetCode30. 与所有单词相关联的字串 | Substring with Concatenation of All Words
- 转 mysql Next-Key Locking
- php发送短信验证码
- vi编辑光标跳到文件开头和结尾以及清空文件命令
- ImageMagick - 设置透明带 AlphaChannel 的 png 图片的透明度
热门文章
- vi/vim命令
- What does jQuery.fn mean?
- [Codeforces 986E] Prince&#39;s Problem
- 【前端】window.resize的优化
- 2010–2011, NEERC, Northern Subregional C.Commuting Functions
- Java IO --ByteArrayOutputStream (六)***
- 30. extjs getEl方法 怎么用
- E20171108-hm
- mysql 根据总分排名
- 公司6:JrVue重用布局