当前位置: 首页 > 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…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

HDFS分布式存储 zookeeper

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

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...

对象回调初步研究

_OBJECT_TYPE结构分析 在介绍什么是对象回调前&#xff0c;首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例&#xff0c;用_OBJECT_TYPE这个结构来解析它&#xff0c;0x80处就是今天要介绍的回调链表&#xff0c;但是先不着急&#xff0c;先把目光…...