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

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...