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

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

SpringAI实战:ChatModel智能对话全解

一、引言&#xff1a;Spring AI 与 Chat Model 的核心价值 &#x1f680; 在 Java 生态中集成大模型能力&#xff0c;Spring AI 提供了高效的解决方案 &#x1f916;。其中 Chat Model 作为核心交互组件&#xff0c;通过标准化接口简化了与大语言模型&#xff08;LLM&#xff0…...

Python环境安装与虚拟环境配置详解

本文档旨在为Python开发者提供一站式的环境安装与虚拟环境配置指南&#xff0c;适用于Windows、macOS和Linux系统。无论你是初学者还是有经验的开发者&#xff0c;都能在此找到适合自己的环境搭建方法和常见问题的解决方案。 快速开始 一分钟快速安装与虚拟环境配置 # macOS/…...

Java多线程实现之Runnable接口深度解析

Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...