树哈希与换根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×y∈x∑dpy2+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
采用的树哈希函数是: 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 dpxwxy∈x∑dpy2wx2 发现从 x x x 到 y y y 时只有 x x x 与 y y y 的哈希值会变化,分别维护即可 #include<bits/stdc.h&…...

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

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

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

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

【操作系统笔记十一】进程间通信
Linux文件系统 inode 节点 (index node):给每个文件赋予一个称为 i 节点的数据结构。 inode 一开始是存储在硬盘中的,只有当文件被打开的时候,其对应的 i 节点才加载到内存中。 总结: Linux 中,…...
【操作系统】聊聊Linux软中断
什么是中断 中断是系统用来响应硬件设备请求的一种机制,会打断进程的正常调度和执行,转而去执行内核中的中断处理程序。 比如你正在看书,你女朋友叫你出去逛街。你就需要先放下手里的事情,然后逛街。回来之后,在接着看…...

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

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

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

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

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

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推出两款大模型应用: 对话式检索与开发 打破代码语言屏障
更多技术交流、求职机会,欢迎关注字节跳动数据平台微信公众号,回复【1】进入官方交流群 自上世50年代,以“计算机”作为代表性象征的信息革命开始,社会对于先进生产力的认知便开始逐步更迭——从信息化(通常认为是把企…...

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

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

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

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

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

VS2022创建控制台应用程序后没有Main了,如何显示Main?
文章目录 问题描述原因解决方案简单的顶级语句试用计算器 其他文章 问题描述 用VS2022创建一个控制台应用后,没有名称空间和Main函数了,只有一个WriteLine,如下所示。 // See https://aka.ms/new-console-template for more information Co…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...

Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...

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

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

AI病理诊断七剑下天山,医疗未来触手可及
一、病理诊断困局:刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断",医生需通过显微镜观察组织切片,在细胞迷宫中捕捉癌变信号。某省病理质控报告显示,基层医院误诊率达12%-15%,专家会诊…...
tomcat指定使用的jdk版本
说明 有时候需要对tomcat配置指定的jdk版本号,此时,我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...