P3565 [POI2014] HOT-Hotels
~~~~~ P3565 [POI2014] HOT-Hotels ~~~~~ 总题单链接
思路
~~~~~ 设 g [ u ] [ i ] g[u][i] g[u][i] 表示在 u u u 的子树内,距离 u u u 为 i i i 的点的个数。
~~~~~ 设 d p [ u ] [ i ] dp[u][i] dp[u][i] 表示: u u u 的子树内存在两个点 x , y x,y x,y,设 d i s ( x , l c a ) = d i s ( y , l c a ) = d dis(x,lca)=dis(y,lca)=d dis(x,lca)=dis(y,lca)=d, d i s ( l c a , u ) = k dis(lca,u)=k dis(lca,u)=k, i = d − k i=d-k i=d−k。举个栗子:

~~~~~ 上图中 d p [ 1 ] [ 1 ] = 3 dp[1][1]=3 dp[1][1]=3({x=4,y=5},{x=4,y=8},{x=6,y=8})。
~~~~~ 对于每个 u u u:
~~~~~ a n s = a n s + d p [ u ] [ 0 ] ans=ans+dp[u][0] ans=ans+dp[u][0]
~~~~~ a n s = a n s + ∑ x , y ∈ s o n ( u ) , x ! = y d p [ x ] [ j + 1 ] ∗ g [ y ] [ j − 1 ] ans=ans+\sum_{x,y\in son(u),x!=y}dp[x][j+1]*g[y][j-1] ans=ans+∑x,y∈son(u),x!=ydp[x][j+1]∗g[y][j−1],为什么是 j + 1 j+1 j+1 和 j − 1 j-1 j−1?因为 u u u 和 y y y 已经补了两个,不懂的同学可以画个图看一下。
~~~~~ d p [ u ] [ i ] = d p [ u ] [ i ] + g [ x ] [ i − 1 ] ∗ g [ y ] [ i − 1 ] dp[u][i] =dp[u][i]+g[x][i-1]*g[y][i-1] dp[u][i]=dp[u][i]+g[x][i−1]∗g[y][i−1],这是 k = 0 k=0 k=0 的情况。
~~~~~ d p [ u ] [ i ] = d p [ u ] [ i ] + d p [ v ] [ i − 1 ] dp[u][i]=dp[u][i]+dp[v][i-1] dp[u][i]=dp[u][i]+dp[v][i−1]
~~~~~ 以上公式可以用前缀和做到 O ( N ) O(N) O(N) 转移。
~~~~~ 时间复杂度 O ( N 2 ) O(N^2) O(N2),空间复杂度 O ( N 2 ) O(N^2) O(N2)。
~~~~~ 发现这道题可以用长链剖分将时间复杂度优化至 O ( N ) O(N) O(N),但这个以后再将。
代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;ll ans;vector<int>eg[5002];
int f[5002][5002],g[5002][5002];
inline void dfs(int fa,int p)
{f[p][0]=1;for(int v:eg[p]) {if(v==fa)continue;dfs(p,v);for(int i=0;i<=n;i++)ans+=g[p][i]*(i==0?0:f[v][i-1])+g[v][i+1]*f[p][i];for(int i=0;i<=n;i++)g[p][i]+=f[p][i]*(i==0?0:f[v][i-1])+g[v][i+1];for(int i=1;i<=n;i++)f[p][i]+=f[v][i-1];}
}
signed main(){cin>>n;for(int i=1;i<n;i++) {int u,v;cin>>u>>v;eg[u].push_back(v);eg[v].push_back(u);}dfs(0,1);cout<<ans;return 0;
}
相关文章:
P3565 [POI2014] HOT-Hotels
~~~~~ P3565 [POI2014] HOT-Hotels ~~~~~ 总题单链接 思路 ~~~~~ 设 g [ u ] [ i ] g[u][i] g[u][i] 表示在 u u u 的子树内,距离 u u u 为 i i i 的点的个数。 ~~~~~ 设 d p [ u ] [ i ] dp[u][i] dp[u][i] 表示: u u u 的子树内存在两个点 x , …...
设计模式 | 单例模式
定义 单例设计模式(Singleton Pattern)是一种创建型设计模式,它确保一个类只有一个实例,并提供一个全局访问点来获取该实例。这种模式常用于需要控制对某些资源的访问的场景,例如数据库连接、日志记录等。 单例模式涉…...
Web安全之CSRF攻击详解与防护
在互联网应用中,安全性问题是开发者必须时刻关注的核心内容之一。跨站请求伪造(Cross-Site Request Forgery, CSRF),是一种常见的Web安全漏洞。通过CSRF攻击,黑客可以冒用受害者的身份,发送恶意请求&#x…...
IDEA运行Java程序提示“java: 警告: 源发行版 11 需要目标发行版 11”
遇到这个提示一般是在pom.xml中已经指定了构建的Java版本环境是11例如(此时添加了build插件的情况下虽然不能直接运行代码但是maven是可以正常打包构建): <build><plugins><plugin><groupId>org.apache.maven.plugins</groupId><…...
车载测试| 汽车的五域架构 (含线控技术知识)
汽车的五域架构是一种将汽车电子控制系统按照功能进行划分的架构模式,主要包括动力域、底盘域、座舱域、自动驾驶域和车身域。(汽车三域架构通常是指将汽车电子系统划分为三个主要领域:动力域、底盘域和智能座舱域(或车身舒适域&a…...
【Linux】gcc/g++ 、make/Makefile、git、gdb 的使用
目录 1. Linux编译器-gcc/g1.1 编译器gcc/g的工作步骤1.2 函数库1.2.1 函数库的作用及分类1.2.2 动态链接和静态链接1.2.3 动态库和静态库的优缺点 1.3 gcc选项 2. Linux项目自动化构建工具-make/Makefile2.1 .PHONY2.2 尝试编写进度条程序 3. git3.1 安装 git3.2 下载项目到本…...
Elastic Stack--ES的DSL语句查询
前言:本博客仅作记录学习使用,部分图片出自网络,如有侵犯您的权益,请联系删除 学习B站博主教程笔记: 最新版适合自学的ElasticStack全套视频(Elk零基础入门到精通教程)Linux运维必备—Elastic…...
ARM基础知识---CPU---处理器
目录 一、ARM架构 1.1.RAM---随机存储器 1.2.ROM---只读存储器 1.3.flash---闪存存储器 1.4.时钟(振晶) 1.5.复位 二、CPU---ARM920T 2.1.R0~R12---通用寄存器 2.2.PC程序计数器 2.3.LR连接寄存器 2.4.SP栈指针寄存器 2.5.CPSR当前程序状态寄存…...
将星 x17 安装ubuntu 20.04 双系统
准备工作,包含关闭快速启动,关闭Secret Boot 1.进入控制面板选择小图标,找到电源选项 2.点击更改当前不可用的设置,关闭快速启动 3.开机启动时快速按F2,进入BIOS 4.选择Setup Utiltity,选择Security&#…...
E31.【C语言】练习:指针运算习题集(上)
Exercise 1 求下列代码的运行结果 #include <stdio.h> int main() {int a[5] { 1, 2, 3, 4, 5 };int* ptr (int*)(&a 1);printf("%d",*(ptr - 1));return 0; } 答案速查: 分析: Exercise 2 求下列代码的运行结果 //在x86环境下 //假设结…...
git分支的管理
分支管理是 Git 版本控制系统中的一个核心功能,它涉及如何创建、管理、合并和删除分支,以便在团队协作和开发过程中更有效地组织代码。以下是分支管理中的一些关键概念和实践: 1. 分支的创建 创建新分支:在开发新功能、修复 bug…...
对于消息队列的一些思考
如何保证消息不被重复消费 唯一ID:你提到的通过唯一ID解决重复消费问题非常重要。这通常通过业务系统引入唯一消息ID(如UUID)来实现。在消费端,先检查消息ID是否已经被处理,未处理过的才进行处理,确保幂等…...
IM即时通讯软件-WorkPlus私有化部署的局域网即时通讯工具
随着企业对通讯安全和数据掌控的需求不断增加,许多企业开始选择私有化部署的即时通讯工具,以在内部局域网环境中实现安全、高效的沟通与协作。IM-WorkPlus作为一款受欢迎的即时通讯软件,提供了私有化部署的选项,使企业能够在自己的…...
AI大模型的饕餮盛宴,系统学习大模型技术,你想要的书都在这里了
AI大模型的饕餮盛宴,系统学习大模型技术,你想要的书都在这里了 要说现在最热门的技术,可谓非大模型莫属!不少小伙伴都想要学习大模型技术,转战AI领域,以适应未来的大趋势,寻求更有前景的发展~~…...
支付宝开放平台-开发者社区——AI 日报「9 月 9 日」
1 离开 OpenAl 后,llya 拿了10亿美金对抗 Al 作恶 极窖公园 丨阅读原文 lya Sutskever, OpenAl的前联合创始人,成立了SS1 (Safe Superintelligence),旨在构建安全的Al模型。SSl获得了10亿美元的融资,估值达到50亿美元ÿ…...
将AI与情境定位结合以确保品牌安全
你可能会看到一些广告,感觉它们跟你在线阅读或观看的内容有奇怪的关联。这就是上下文广告在起作用。这种基于广告的解决方案在不断变化的数字环境中逐步发展,已经成为每个广告主的必备工具。不过,这种广告不只是把广告和上下文进行匹配这么简…...
OpenAI 联合 SWE 发布 AI 软件工程能力测试集,Gru.ai 荣登榜首
在 9 月 3 日,Gru.ai 在 SWE-Bench-Verified 评估最新发布的数据中以 45.2% 的高分排名第一。SWE-Bench-Verified 是 OpenAI 联合 SWE 发布测试集,旨在更可靠的评估 AI 解决实际软件问题的能力。该测试集经由人工验证打标,被认为是评估 AI 软…...
一文读懂SpringMVC的工作原理
前言 MVC是经典的软件架构设计模式,几乎在各个领域各种开发语言中,均采纳了这个思想。此刻博主突然想到了Thinking in xxx系列设计书籍。换句话说,就是“各人自扫门前雪”和“术业有专攻”。当职责分配得当后,剩下的就是发挥各“…...
【python-斐波那契数列和完美数之间的区别】
斐波那契数列和完美数在数学领域中是两个截然不同的概念,它们之间存在明显的区别。以下是对这两个概念及其区别的详细阐述: 斐波那契数列 定义: 斐波那契数列,又称黄金分割数列,是一个在数学上具有重要意义的数列。它…...
【redis】本地windows五分钟快速安装redis
用处:本地自测,有时候公司redis环境不稳定,用自己的 1.下载,github下载一个解压缩在自己想要的位置 选择版本:Redis-7.4.0-Windows-x64-msys2-with-Service,zip GitHub - redis-windows/redis-windows: …...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
【解密LSTM、GRU如何解决传统RNN梯度消失问题】
解密LSTM与GRU:如何让RNN变得更聪明? 在深度学习的世界里,循环神经网络(RNN)以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而,传统RNN存在的一个严重问题——梯度消失&#…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
Visual Studio Code 扩展
Visual Studio Code 扩展 change-case 大小写转换EmmyLua for VSCode 调试插件Bookmarks 书签 change-case 大小写转换 https://marketplace.visualstudio.com/items?itemNamewmaurer.change-case 选中单词后,命令 changeCase.commands 可预览转换效果 EmmyLua…...
