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: …...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
