CF280C

刺骨的言语ヽ痛彻心扉 2024-04-20 10:26 76阅读 0赞

##  ##

CF280C

> ZR补题计划

### 题意： ###

> 一棵有根树，每次选择一个未删除的节点，然后删除它和它的子树内的点，问期望删多少次可以把整个树删完

### 解析： ###

> 显然，通过题面，我们可以知道对于一个点对 $ (u,v) $ ，如果我们删除 $ u $ 那么 $ v $ 也一定会被删除, $ v $ 所在的子树的集合也一定会被删除。  
> 因为期望的线性性，我们可以考虑一个节点被删除的期望次数。  
> 并且我们可以知道，删除一个子树内的节点，只有可能删除这个节点，或者删除这个节点的一个祖先，然后实际上操作在这个点上的概率只有 $ \\frac\{1\}\{depth\[i\]\} $ 。

### CODE: ###

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; #define LL long long const int N = 1e5 + 100; struct Edge { int to,from; } e[N * 2]; int cnt,head[N],depth[N],n; inline void add_edge(int x,int y) { e[++cnt].from = y; e[cnt].to = head[x]; head[x] = cnt; } void dfs(int x,int fa,int deep) { depth[x] = deep; for(int i = head[x] ; i ; i = e[i].to) { int u = e[i].from; if(u == fa) continue; dfs(u,x,deep + 1); } } int main() { scanf("%d",&n); for(int i = 1 ; i < n ; i++) { int a,b; scanf("%d%d",&a,&b); add_edge(a,b); add_edge(b,a); } dfs(1,1,1); double ans = 0; for(int i = 1 ; i <= n ; i++) ans += 1.0 / depth[i]; printf("%.10f \n",ans); //system("pause"); return 0; }

转载于:https://www.cnblogs.com/Repulser/p/11383822.html

发表评论取消回复

表情：

评论列表（有 0 条评论，76人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1217C

CF1217C 题意： > 给定一个01串，一个good01串的定义是这个01串所代表的二进制数字刚好等于它的长度，允许前导零，问这个01串当中有几个goo...

柔光的暖阳◎/ 2024年04月20日 10:34/ 0 赞/ 91 阅读

相关 CF1214C

CF1214C 题意： > 给你一个括号序列，问你时候能仅移动相邻的两个元素，使括号序列合法。解法： > 可以先考虑普通括号序列怎么做 > 这...

亦凉/ 2024年04月20日 10:33/ 0 赞/ 92 阅读

相关 CF1200C

CF1200C 题意： > 问内圆和外圆分别分成n、m份，每份有标号，问是否可以从一个部分走到另一个部分，12点钟位置一定有个线。解法： > 如果...

旧城等待，/ 2024年04月20日 10:32/ 0 赞/ 97 阅读

相关 CF1030C

CF1030C 题意： > 给你一个数字，问能否拆分成k段，使得每一段的每一位数字相加结果相等。解法： > 考虑数位DP。 > 暴力按位考虑每...

ゝ一纸荒年。/ 2024年04月20日 10:31/ 0 赞/ 89 阅读

相关 CF1208C

CF1208C > 这场杜老师大战tourist的比赛怎么这么多人类智慧题。。。题意： > 构造一个 $ n \\times n $ 的矩阵，使得该矩阵...

迈不过友情╰/ 2024年04月20日 10:31/ 0 赞/ 101 阅读

相关 CF1197C

CF1197C 题意： > 有一个递增的数列，把它分成k段，找到这样的分段方法，即每段最大值减最小值的和最小解法： > 分成k段，即要加k-1个隔...

太过爱你忘了你带给我的痛/ 2024年04月20日 10:28/ 0 赞/ 94 阅读

相关 CF1204C

CF1204C-Anna, Svyatoslav and Maps 题意： > [题目传送门][Link 1] > 不想说了，阅读题。解法： ...

阳光穿透心脏的1/2处/ 2024年04月20日 10:26/ 0 赞/ 96 阅读

相关 CF280C

CF280C > ZR补题计划题意： > 一棵有根树，每次选择一个未删除的节点，然后删除它和它的子树内的点，问期望删多少次可以把整个树删完解析： ...

刺骨的言语ヽ痛彻心扉/ 2024年04月20日 10:26/ 0 赞/ 77 阅读

相关 CF985C

CF985C 题意： > 你要组成N个木桶，组成每个木桶需要K个木块，（第二行给你N\*K个木块），使得任意两个木桶之间的差值不超过L的情况，使得所有木桶可...

客官°小女子只卖身不卖艺/ 2024年04月20日 10:26/ 0 赞/ 86 阅读

相关 cf 1179 C

目录 A B C A 模拟出A不是最大值的情况，存起来。最多有n个。当A为最大值的时候，后面n-1个数开始循环。查询分两种情况讨论就行了

比眉伴天荒/ 2021年11月01日 10:20/ 0 赞/ 285 阅读