当前位置: 首页 > article >正文

牛客周赛 Round 62

树上期望-《经典期望》

小红的树上移动

题目

小红拿到了一棵树,初始所有节点均为白色。小红初始站在1号节点,并将1号节点染红。小红将不断进行移动直到停止:

  1. 若当前节点的邻点中存在白色节点,则小红随机移动到某个相邻的白色节点,并将该节点染红。
  2. 若当前节点的邻点中不存在白色节点,则停止移动。

请你帮小红求出最终红点数量的期望。

思路

对于每个点的子节点,概率均为 1 s i z e \frac{1}{size} size1, s i z e size size为该点的子节点个数

dfs跑一遍对于每个节点的概率 p i p_i pi

答案就是 Σ p i × 1 \Sigma p_i\times 1 Σpi×1

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
const int mod=1e9+7; 
int ans;
vector<int> e[N];
bool vis[N];
int quickpow(int x,int y){
    int res=1;
    while(y){    
        if(y&1) res=(res*x)%mod;            
        x=(x*x)%mod;
        y>>=1;
    }
    return res;
}
int inv(int x){
    return quickpow(x,mod-2);
}
int add(int x,int y){
    return ((x%mod)+(y%mod))%mod;
}
int sub(int x,int y){
    return ((x-y)%mod+mod)%mod;
}
int mul(int x,int y){
    return (x%mod*y%mod)%mod;    
}
void dfs(int v,int p){
//     cout << v << " " << p << endl;
    vis[v] = 1;
    ans = add(ans,p);
    int num = e[v].size();
    if(v!=1) num--;
    for(auto u : e[v]){
        if(vis[u]) continue;
        dfs(u,mul(p,inv((num))));
    }
}
void solve()
{
 	int n;
    cin >> n;
    for(int i = 1 ; i < n ; i ++){
        int x,y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    
    dfs(1,1);

    cout << ans << endl;
}

signed main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int t=1;
	// cin>>t;
	while(t--){
		solve();
	}
	
	return 0;
}



http://www.kler.cn/a/327303.html

相关文章:

  • 前后端交互之动态列
  • 对PolyMarket的突袭
  • 父组件提交时让各自的子组件验证表格是否填写完整
  • MySQL的编程语言
  • PyTorch——从入门到精通:PyTorch基础知识(张量)【PyTorch系统学习】
  • linux之调度管理(5)-实时调度器
  • 828华为云征文|部署个人文档管理系统 Docspell
  • Kali Linux安全工具
  • 实战OpenCV之形态学操作
  • 网络带宽对于服务器的影响
  • 云原生之运维监控实践-使用Prometheus与Grafana实现对MySQL和Redis服务的监测
  • Drf认证组件
  • Feign 主要负责简化 HTTP API 的调用逻辑; Eureka 负责服务实例的注册和服务发现; Ribbon 则负责实现客户端的负载均衡。
  • UE4_Niagara基础实例—7、如何让粒子照亮周边环境
  • 制造企业各部门如何参与生产成本控制与管理?
  • Leetcode Hot 100 | 543.二叉树的直径 | 递归+优化
  • 【人人保-注册安全分析报告-无验证方式导致安全隐患】
  • 项目:微服务即时通讯系统客户端(基于C++QT)]四,中间界面搭建和逻辑准备
  • git使用“保姆级”教程3——添加暂存区及提交本地库
  • 苹果手机如何录屏?IOS 自带工具与嗨格式录屏大师 APP 详解
  • 只写CURD后台管理的Java后端要如何提升自己
  • RabbitMQ的应用问题
  • ansible学习之 Facts
  • Python知识点:如何使用EdgeX Foundry与Python进行边缘计算
  • 使用iTextPDF库时,设置文字为中文格式
  • 基于微信小程序的美食推荐系统