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

2023NOIP A层联测32 sakuya

题目大意

有一棵有 n n n个节点的树,每条边有一个边权 w w w。有 m m m个特殊点,将这些点记为集合 A A A

A A A中的元素随机打乱得到序列 a a a,求 ∑ i = 2 m d ( a i − 1 , a i ) \sum\limits_{i=2}^md(a_{i-1},a_i) i=2md(ai1,ai)的期望值模 998244353 998244353 998244353后的值,其中 d ( x , y ) d(x,y) d(x,y)表示 x x x y y y的边权和。

q q q次修改,每次修改会将与 x x x相连的边的权值增加 k k k。求每次修改后上述式子的期望值。

1 ≤ n ≤ 5 × 1 0 5 , m ≤ n , 1 ≤ q ≤ 5 × 1 0 5 1\leq n\leq 5\times 10^5,m\leq n,1\leq q\leq 5\times 10^5 1n5×105,mn,1q5×105

1 ≤ w , k ≤ 1 0 9 1\leq w,k\leq 10^9 1w,k109


题解

对于每组特殊点 x , y x,y x,y,我们考虑有多少种方案会计算到 d ( x , y ) d(x,y) d(x,y)的贡献。在确定 x , y x,y x,y a a a中相邻之后,其他 m − 2 m-2 m2个数有 ( m − 2 ) ! (m-2)! (m2)!种放法, x , y x,y x,y中较前的数可以放在第一个到第 m − 1 m-1 m1个位置上,确定了前一个数,则后一个数也确定了,而这两个数的顺序可以为 x , y x,y x,y或者 y , x y,x y,x,所以还要乘 2 2 2,也就是说有 2 ( m − 2 ) ! × ( m − 1 ) = 2 ( m − 1 ) ! 2(m-2)!\times (m-1)=2(m-1)! 2(m2)!×(m1)=2(m1)!种方案会计算到 d ( x , y ) d(x,y) d(x,y)的贡献。而题目要求的是期望值,总共有 m ! m! m!种方案,那么 d ( x , y ) d(x,y) d(x,y)对答案的贡献为 2 ( m − 1 ) ! m ! × d ( x , y ) = 2 m × d ( x , y ) \dfrac{2(m-1)!}{m!}\times d(x,y)=\dfrac 2m\times d(x,y) m!2(m1)!×d(x,y)=m2×d(x,y)

下面,我们要求每条边被多少 d ( x , y ) d(x,y) d(x,y)计算过,这用一个 d f s dfs dfs即可算出,记这个值为 t d i td_i tdi。然后,求出所有边 i i i w i w_i wi t d i td_i tdi之积的和,也就是 ∑ i w i × t d i \sum\limits_iw_i\times td_i iwi×tdi m 2 × ∑ i w i × t d i \dfrac m2\times \sum\limits_iw_i\times td_i 2m×iwi×tdi即为答案。

我们考虑每次修改对答案的贡献。设与 i i i相连的边的 t d td td值之和为 t w i tw_i twi,则每次修改会让 ∑ i w i × t d i \sum\limits_iw_i\times td_i iwi×tdi增加 k × t w i k\times tw_i k×twi。那么,我们可以 O ( 1 ) O(1) O(1)修改。因为题目只需要求答案,所以我们不需要真的去修改 w i w_i wi

时间复杂度为 O ( n + q ) O(n+q) O(n+q)

code

#include<bits/stdc++.h>
using namespace std;
const int N=500000;
const long long mod=998244353;
int n,m,q,z[N+5],siz[N+5];
long long ans,pt,w[N+5],td[N+5],tw[N+5];
vector<pair<int,int>>g[N+5];
long long mi(long long t,long long v){if(!v) return 1;long long re=mi(t,v/2);re=re*re%mod;if(v&1) re=re*t%mod;return re;
}
void dfs(int u,int fa){siz[u]=z[u];for(auto p:g[u]){int v=p.first,id=p.second;if(v==fa) continue;dfs(v,u);siz[u]+=siz[v];td[id]=1ll*(m-siz[v])*siz[v]%mod;}
}
int main()
{
//	freopen("sakuya.in","r",stdin);
//	freopen("sakuya.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1,x,y;i<n;i++){scanf("%d%d%lld",&x,&y,&w[i]);g[x].push_back({y,i});g[y].push_back({x,i});}for(int i=1,x;i<=m;i++){scanf("%d",&x);z[x]=1;}dfs(1,0);for(int i=1;i<n;i++){ans=(ans+td[i]*w[i])%mod;}for(int i=1;i<=n;i++){for(auto p:g[i]){tw[i]=(tw[i]+td[p.second])%mod;}}scanf("%d",&q);long long tq=mi(m,mod-2)*2%mod;for(int o=1,x,k;o<=q;o++){scanf("%d%d",&x,&k);ans=(ans+tw[x]*k)%mod;pt=ans*tq%mod;printf("%lld\n",pt);}return 0;
}

相关文章:

2023NOIP A层联测32 sakuya

题目大意 有一棵有 n n n个节点的树&#xff0c;每条边有一个边权 w w w。有 m m m个特殊点&#xff0c;将这些点记为集合 A A A。 将 A A A中的元素随机打乱得到序列 a a a&#xff0c;求 ∑ i 2 m d ( a i − 1 , a i ) \sum\limits_{i2}^md(a_{i-1},a_i) i2∑m​d(ai−1​…...

竞赛选题 深度学习的视频多目标跟踪实现

文章目录 1 前言2 先上成果3 多目标跟踪的两种方法3.1 方法13.2 方法2 4 Tracking By Detecting的跟踪过程4.1 存在的问题4.2 基于轨迹预测的跟踪方式 5 训练代码6 最后 1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于深度学习的视频多目标跟踪实现 …...

金蝶云星空表单插件获取控件值

文章目录 金蝶云星空表单插件获取控件值获取主键获取文本获取日期获取数值获取基础资料 金蝶云星空表单插件获取控件值 获取主键 正确&#xff1a; this.View.Model.GetPKValue();错误&#xff1a; 获取文本 this.View.Model.GetValue("FBILLNO")获取日期 thi…...

docker自启与容器自启

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

一、认识微服务

目录 一、单体架构 二、分布式架构 三、微服务 1、微服务架构特征&#xff1a; 1.单一职责&#xff1a; 2.面向服务&#xff1a; 3.自治&#xff1a; 4.隔离性强&#xff1a; 2、微服务结构&#xff1a; 3、微服务技术对比&#xff1a; 一、单体架构 二、分布式架构 三…...

Windows server 2012 R2系统服务器远程桌面服务激活服务器RD授权分享

Windows server 2012 R2系统服务器远程桌面服务激活服务器RD授权 二、激活服务器&#xff0c;获取许可证服务器ID和许可证密钥包ID三、激活终端服务器四、配置远程桌面会话主机授权服务器 上期我分享了Windows server 2012 R2系统服务器远程桌面服务的安装教程&#xff0c;若是…...

Vue的计算属性:让你的代码更简洁高效

Vue.js是一种流行的JavaScript框架&#xff0c;它提供了许多功能来帮助开发人员构建交互式Web应用程序。其中一个非常有用的功能是计算属性。在本文中&#xff0c;我们将讨论什么是Vue的计算属性以及如何使用它们来编写更简洁高效的代码。 什么是Vue的计算属性&#xff1f; Vu…...

mysql主从复制-使用心得

文章目录 前言环境配置主库从库 STATEMENTbinloggtidlog-errorDistSQL总结 前言 mysql 主从复制使用感受&#xff0c;遇到一些问题的整理&#xff0c;也总结了一些排查问题技巧。 环境 mysql5.7 配置 附&#xff1a;千万级数据快速插入配置可以参考&#xff1a;mysql千万数…...

今年副业比主业赚得多...

我是从20年开始接触副业的&#xff0c;主要是在程序员外包平台上接单。从一开始的月入0到几百&#xff0c;到现在每个月稳定有小一万的收入。这个月接了一个比较大的项目&#xff0c;结款之后发现今年的副业已经比主业赚得多了&#xff0c;简直美滋滋~ 今年主业收入8w&#xff…...

debian12安装fail2ban

趁着阿里云活动&#xff0c;买了一台一年99的VPS&#xff0c;装了debian12 rootdebian:~# neofetch _,met$$$$$gg. …...

openpnp - 74路西门子飞达控制板(主控板STM32_NUCLEO-144) - 验证

文章目录 openpnp - 74路西门子飞达控制板(主控板STM32_NUCLEO-144) - 验证概述笔记重复数字IO的问题想法手工实现程序实现确定要摘掉的数字重合线自动化测试的问题测试程序的场景测试程序的运行效果测试程序实现备注END openpnp - 74路西门子飞达控制板(主控板STM32_NUCLEO-14…...

从房地产先后跨界通信、文旅演艺领域,万通发展未来路在何方?

近年来&#xff0c;房地产市场可谓负重前行&#xff0c;各大房企纷纷谋求新出路。 作为中国最早的房企之一&#xff0c;万通发展再次处在转型变革的十字路口。自去年以来&#xff0c;万通发展在转型升级之路上动作频频&#xff0c;可谓忙得不亦乐乎。 大幕落下之时&#xff0c;…...

LLM 中的参数单位

M (Mega) 相比于 Million&#xff1a; 1M (Mega) 在计算机科学中等于 ( 2^{20} )&#xff08;即 1,048,576&#xff09;字节。1 Million 等于 ( 10^6 )&#xff08;即 1,000,000&#xff09;。因此&#xff0c;1M (Mega) 在数字上略小于 1 Million。 G (Giga) 相比于 Billion&…...

【探索Linux】—— 强大的命令行工具 P.15(进程间通信 —— system V共享内存)

阅读导航 引言一、system V的概念二、共享内存(1) 概念(2) 共享内存示意图(3) 共享内存数据结构 三、共享内存的使用1. 共享内存的使用步骤&#xff08;1&#xff09;包含头文件&#xff08;2&#xff09;获取键值&#xff08;ftok函数&#xff09;&#xff08;3&#xff09;创…...

MCU通过KT6368A用SPP透传发送1K左右的数据,手机APP显示是3个包或者4个包,但是我看手册说最大一个包是512,理论应该是两个包吧,请问这正常吗?

一、问题简介 MCU通过KT6368A用SPP透传发送1K左右的数据&#xff0c;手机APP显示是3个包或者4个包&#xff0c;但是我看手册说最大一个包是512&#xff0c;理论应该是两个包吧&#xff0c;请问这正常吗&#xff1f; 详细说明 实际测试的截图如下&#xff1a;使用的是安卓app…...

童装CPC认证检测哪些内容?童装上架亚马逊美国站CPC认证办理

童装是指适合儿童穿着的服装。按年龄分&#xff0c;包括婴儿服装、儿童服装、童装、中年童装、大童服装。CPC认证即儿童产品证书&#xff08;CPC&#xff09;&#xff0c;主要针对12岁以下的儿童&#xff0c;如玩具、摇篮、童装等。跨境卖家作为“进口商”&#xff0c;想要将中…...

2023鸿蒙预定未来,环境搭建学习

鸿蒙开发基础知识 鸿蒙的基本概念和特点 鸿蒙&#xff08;HarmonyOS&#xff09;是华为公司开发的一款全场景分布式操作系统。它的设计目标是为各种设备提供统一的、无缝的用户体验。鸿蒙的核心特点包括以下几个方面&#xff1a; 分布式架构&#xff1a;鸿蒙采用分布式架构&…...

技术架构 - 应用数据分离,应用服务集群架构

前言 上一篇文章介绍了单机架构&#xff0c;由于性能瓶颈&#xff0c;满足不了高访问量&#xff0c;所以演化出了数据分离架构。 这种架构也很简单只是将应用服务和数据库服务分离开来&#xff0c;避免单一架构的资源争夺的情况。 一、 应用数据分离架构 1. 简介 应用服务和…...

YOLO目标检测——树叶检测数据集下载分享【含对应voc、coco和yolo三种格式标签】

实际项目应用&#xff1a;生物多样性研究、林业管理、环境监测和教育科研等方面数据集说明&#xff1a;树叶分类检测数据&#xff0c;真实场景的高质量图片数据&#xff0c;数据场景丰富&#xff0c;总共十个类别。标签说明&#xff1a;使用lableimg标注软件标注&#xff0c;标…...

ubuntu 20通过docker安装onlyoffice,并配置https访问

目录 一、安装docker &#xff08;一&#xff09;更新包列表和安装依赖项 &#xff08;二&#xff09;添加Docker的官方GPG密钥 &#xff08;三&#xff09;添加Docker存储库 &#xff08;四&#xff09;安装Docker &#xff08;五&#xff09;启动Docker服务并设置它随系…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

【C++特殊工具与技术】优化内存分配(一):C++中的内存分配

目录 一、C 内存的基本概念​ 1.1 内存的物理与逻辑结构​ 1.2 C 程序的内存区域划分​ 二、栈内存分配​ 2.1 栈内存的特点​ 2.2 栈内存分配示例​ 三、堆内存分配​ 3.1 new和delete操作符​ 4.2 内存泄漏与悬空指针问题​ 4.3 new和delete的重载​ 四、智能指针…...