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

树哈希与换根dp:CF763D

采用的树哈希函数是:

d p x = w x × ∑ y ∈ x d p y 2 + w x 2 \Large dp_x=w_x\times \sum_{y\in x}dp_y^2+w_x^2 dpx=wx×yxdpy2+wx2

发现从 x x x y y y 时只有 x x x y y y 的哈希值会变化,分别维护即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar(); while(ch<'0'||
ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
//mt19937 rand(time(0));
//mt19937_64 rand(time(0));
//srand(time(0));
#define N 100010
//#define M
#define mo (int)(1e9+123)
int n, m, i, j, k, T;
int pos, mx, cnt, h[N], w[N], dp[N], f[N], u, v; 
map<int, int>mp; 
vector<int>G[N]; int Mod(int a) {return (a%mo+mo)%mo; 
}void add(int x, int k) {mp[x]+=k; if(mp[x]==1 && k==1) ++cnt; if(mp[x]==0 && k==-1) --cnt; 
//	printf("# %lld (%lld): %lld\n", x, mp[x], cnt); 
}void dfs1(int x, int fa) {
//	int s1, s2=0; w[x]=1; for(int y : G[x]) {if(y==fa) continue; dfs1(y, x); w[x]+=w[y]; f[x]=Mod(f[x]+dp[y]*dp[y]); }dp[x]=Mod(w[x]*f[x]%mo+w[x]*w[x]%mo); add(dp[x], 1); 
//	printf("%lld : %lld\n", x, dp[x]); 
}void dfs2(int x, int fa) {int xw, xf, xdp, yw, yf, ydp; for(int y : G[x]) {if(y==fa) continue; 
//		printf("del [%lld] : %lld\n", x, dp[x]); add(dp[x], -1); xdp=dp[x]; xw=w[x]; xf=f[x]; w[x]=w[x]-w[y]; f[x]=Mod(f[x]-dp[y]*dp[y]); dp[x]=(w[x]*f[x]%mo+w[x]*w[x]%mo); 
//		printf("ins [%lld] %lld : %lld\n", x, w[x], dp[x]); add(dp[x], 1); //		printf("del [%lld] : %lld\n", y, dp[y]); add(dp[y], -1); ydp=dp[y]; yw=w[y]; yf=f[y]; w[y]=n; f[y]=Mod(f[y]+dp[x]*dp[x])%mo; dp[y]=(w[y]*f[y]%mo+w[y]*w[y]%mo); //		printf("ins [%lld] : %lld\n", y, dp[y]); add(dp[y], 1); //		printf("%lld : %lld\n", y, cnt); 
//		for(auto t=mp.begin(); t!=mp.end(); ++t) printf("%lld ", t); if(cnt>mx) mx=cnt, pos=y; dfs2(y, x); add(dp[x], -1); add(dp[y], -1); dp[x]=xdp; w[x]=xw; f[x]=xf; add(dp[x], 1); dp[y]=ydp; w[y]=yw; f[y]=yf; add(dp[y], 1); }
}signed main()
{
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
//	T=read();
//	while(T--) {
//
//	}n=read(); for(i=1, k=1; i<n; ++i) {u=read(); v=read(); G[u].pb(v); G[v].pb(u); } dfs1(1, 0); mx=cnt; pos=1; dfs2(1, 0); printf("%lld", pos); return 0;
}

相关文章:

树哈希与换根dp:CF763D

采用的树哈希函数是&#xff1a; d p x w x ∑ y ∈ x d p y 2 w x 2 \Large dp_xw_x\times \sum_{y\in x}dp_y^2w_x^2 dpx​wx​y∈x∑​dpy2​wx2​ 发现从 x x x 到 y y y 时只有 x x x 与 y y y 的哈希值会变化&#xff0c;分别维护即可 #include<bits/stdc.h&…...

npm、yarn、pnpm如何清除缓存?

前端工程化创建项目会经常使用各种安装包管理工具&#xff0c;安装各种前端依赖包。例如&#xff0c;npm、yarn、pnpm等。时间一长&#xff0c;各种安装包管理工具的在安装依赖时&#xff0c;留下的缓存文件就会变得很大&#xff0c;以至于影响系统的运行&#xff0c;因此必要时…...

12款最火的AI画图软件,助你探索创新设计

ChatGPT火爆出圈&#xff0c;AI画图软件也如雨后春笋般流行起来。各类AI画图的软件工具横空出世&#xff0c;设计师与其焦虑工作会不会被人工智能取代&#xff0c;不如践行“工欲善其事必先利其器”&#xff0c;开拓思路&#xff0c;打开格局&#xff0c;好好地探索下如何利用好…...

cookie信息无法获取问题研究

背景 在oneapi这个前后端都有的开源项目中&#xff0c;我想接入chatnextweb到oneapi的后端。 由于需要二开chatnextweb&#xff0c;添加登录注册功能&#xff0c;考虑到java后端的性能问题和内存占用&#xff0c;决定不重启写个服务&#xff0c;而是将登录注册接入到oneapi的…...

Linux:冯诺依曼系统和操作系统的概念

文章目录 冯诺依曼体系结构冯诺依曼体系的理解 操作系统操作系统的基本定位操作系统的理解1 操作系统的理解2总结 本篇主要总结的是操作系统的基本认知和一些概念 冯诺依曼体系结构 那么上图表示的就是冯诺依曼体系结构&#xff0c;那这个体系结构是什么&#xff1f;为什么要先…...

【操作系统笔记十一】进程间通信

Linux文件系统 inode 节点 &#xff08;index node&#xff09;&#xff1a;给每个文件赋予一个称为 i 节点的数据结构。 inode 一开始是存储在硬盘中的&#xff0c;只有当文件被打开的时候&#xff0c;其对应的 i 节点才加载到内存中。 总结&#xff1a; Linux 中&#xff0c…...

【操作系统】聊聊Linux软中断

什么是中断 中断是系统用来响应硬件设备请求的一种机制&#xff0c;会打断进程的正常调度和执行&#xff0c;转而去执行内核中的中断处理程序。 比如你正在看书&#xff0c;你女朋友叫你出去逛街。你就需要先放下手里的事情&#xff0c;然后逛街。回来之后&#xff0c;在接着看…...

公众号迁移个人可以迁移吗?

公众号账号迁移的作用是什么&#xff1f;只能变更主体吗&#xff1f;很多小伙伴想做公众号迁移&#xff0c;但是不知道公众号迁移有什么作用&#xff0c;今天跟大家具体讲解一下。首先公众号迁移最主要的就是修改公众号的主体了&#xff0c;比如我们公众号原来是A公司的&#x…...

全国职业技能大赛云计算--高职组赛题卷⑤(容器云)

全国职业技能大赛云计算--高职组赛题卷⑤&#xff08;容器云&#xff09; 第二场次题目&#xff1a;容器云平台部署与运维任务2 基于容器的web应用系统部署任务&#xff08;15分&#xff09;任务3 基于容器的持续集成部署任务&#xff08;15分&#xff09;任务4 Kubernetes容器…...

支撑位和阻力位在Renko和烛台图如何使用?FPmarkets澳福3秒回答

很多投资者都知道&#xff0c;Renko图表和普通日本烛台都会采用相同的交易信号&#xff0c;即支撑位和阻力位。那么支撑位和阻力位在Renko和烛台图如何使用?FPmarkets澳福3秒回答。 这些信号在任何时间框架上都会出现&#xff0c;且在蜡烛图交易中颇受欢迎。对于Renko图表而言…...

如何在32位MCU用printf()函数打印64位数据

1. 在32位MCU上定义64位变量&#xff1a; unsigned long long time_base; unsigned long long temp_time;2. 调用打印函数&#xff1a; printf("RFID:time_base:%d\r\n",time_base); printf("RFID:temp_time:%d\r\n",temp_time); printf("RFID:Ru…...

Python爬虫程序设置代理常见错误代码及解决方法

Python爬虫程序设置代理是爬虫程序中常用的技巧&#xff0c;可以有效地绕过IP限制&#xff0c;提高爬虫程序的稳定性和效率。然而&#xff0c;在设置代理时&#xff0c;常会出现各种错误代码&#xff0c;这些错误代码可能会影响程序的正常运行&#xff0c;甚至导致程序崩溃。本…...

3D点云目标检测:Centerformer训练waymo数据集

一、环境准备 项目地址:centerformer 1.0、基础环境 python 3.8.0 torch 1.9.1cu111 waymo-open-dataset-tf-2-6-0 1.4.9 spconv 1.2.1 其余按照requirement.txt里安装就行 pip install -i https://pypi.tuna.tsinghua.edu.cn/simple -r requirements.txt由于我本人是在…...

火山引擎DataLeap推出两款大模型应用: 对话式检索与开发 打破代码语言屏障

更多技术交流、求职机会&#xff0c;欢迎关注字节跳动数据平台微信公众号&#xff0c;回复【1】进入官方交流群 自上世50年代&#xff0c;以“计算机”作为代表性象征的信息革命开始&#xff0c;社会对于先进生产力的认知便开始逐步更迭——从信息化&#xff08;通常认为是把企…...

windows上配置vscode C/C++代码跳转

windows上配置vscode C/C代码跳转 安装插件 C/C 官方的 C/C 插件&#xff0c;必备的插件&#xff0c;是代码跳转、自动补全、代码大纲显示等功能的基础。 Gtags C/C GNU Global GNU Global除了安装该插件之外&#xff0c;还需要在本地下载安装GNU Global工具。多看下插件…...

【Xilinx】基于MPSoC的OpenAMP实现(一)

【Xilinx】基于MPSoC的OpenAMP实现&#xff08;一&#xff09; 一、开发环境1、开发思路2、下载官方bsp包 二、编译Linux1、配置petalinux环境变量2、创建工程3、进入目录4、设置缓存目录&#xff08;重点&#xff1a;可离线编译&#xff0c;加快编译速度&#xff09;5、配置u-…...

代码随想录算法训练营总结篇|完结撒花

完结撒花&#xff0c;真不敢相信60天坚持下来了。 算法一直是我的超级超级弱项&#xff0c;属于小白中的小白。一开始是想自己刷的&#xff0c;打开leetcode第一题&#xff0c;吼哟好家伙&#xff0c;梦开始的地方直接破碎。之前刷B站的时候就有学习up推荐算法可以看看代码随想…...

uniapp、vue实现滑动拼图验证码

uniapp、vue实现滑动拼图验证码 实际开发工作中&#xff0c;在登陆的时候需要短信验证码&#xff0c;但容易引起爬虫行为&#xff0c;需要用到反爬虫验证码&#xff0c;今天介绍一下拼图验证码&#xff0c;解决验证码反爬虫中的滑动验证码反爬虫。滑动拼图验证码是在滑块验证码…...

【ArcGIS】土地利用变化分析详解(矢量篇)

土地利用变化分析详解-矢量篇 土地利用类型分类1 统计不同土地利用类型的面积/占比1.1 操作步骤Step1&#xff1a;Step2&#xff1a;计算面积Step3&#xff1a;计算占比 2 统计不同区域各类土地利用类型的面积2.1 操作步骤 3 土地利用变化转移矩阵3.1 研究思路3.2 操作步骤 4 分…...

VS2022创建控制台应用程序后没有Main了,如何显示Main?

文章目录 问题描述原因解决方案简单的顶级语句试用计算器 其他文章 问题描述 用VS2022创建一个控制台应用后&#xff0c;没有名称空间和Main函数了&#xff0c;只有一个WriteLine&#xff0c;如下所示。 // See https://aka.ms/new-console-template for more information Co…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...