洛谷 P6419 COCI2014/2015 #1 Kamp 题解
题意
一颗树 n n n 个点, n − 1 n-1 n−1 条边,经过每条边都要花费一定的时间,任意两个点都是联通的。
有 k k k 个人(分布在 k k k 个不同的点)要集中到一个点举行聚会。
聚会结束后需要一辆车从举行聚会的这点出发,把这 K K K 个人分别送回去。
请你回答,对于 i = 1 ∼ n i=1 \sim n i=1∼n ,如果在第 i i i 个点举行聚会,司机最少需要多少时间把 k k k 个人都送回家。
1 ≤ k ≤ n ≤ 5 × 1 0 5 1 \le k \le n \leq 5\times 10^5 1≤k≤n≤5×105, 1 ≤ x , y ≤ n 1 \le x,y \le n 1≤x,y≤n, 1 ≤ z ≤ 1 0 8 1 \le z \le 10^8 1≤z≤108 。
思路
这是一道换根dp
直接计算从一个点出发,经过所有家之后最后在一个点停下的最短路程,是比较难的。但是可以维护从一个点出发,再回到自己的最短路程,减去该点到其中一个家的最长链,那也是答案。
第一个dfs
经典地,先用第一个dfs处理子树内信息。
用 v i s u vis_u visu标记 u u u是否为一个家, s v u sv_u svu表示 u u u子树内有多少有家之人。
令 g u g_u gu表示,在 u u u子树内,从 u u u出发走完所有有家之人再回到 u u u的最短距离,那么在处理边 ( u , v ) (u,v) (u,v),边权为 w w w时,有:
g u = 2 w + ∑ v ∈ s o n u g v g_u=2w+\sum_{v\in son_u}g_v gu=2w+v∈sonu∑gv
w w w要乘 2 2 2是因为要走来回。
那么到维护最长链了,先维护子树内的最长链;不过为了在第2次dfs中,处理全局的最长链信息,涉及到两个点 ( u , v ) (u,v) (u,v)的次序问题(即 u u u成为 v v v子树内的一点),还需要维护一个次长链来保证正确性。
令 D u D_u Du表示 u u u节点开始子树内最长链, s D u sD_u sDu表示 u u u节点开始子树内次长链;可以用一个 n x u nx_u nxu记录该最长链上, u u u的下一个节点(因为在最长链上任一节点 x x x子树的、由 x x x开始的最长链,必然与 u u u开始的最长链重合)
void dfs1(ll u,ll fa)
{if(vis[u])sv[u]=1;for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(v==fa)continue;dfs1(v,u);if(sv[v]){g[u]+=g[v]+2*w;if(w+D[v]>=D[u]){sD[u]=D[u];D[u]=w+D[v];nx[u]=v;}else if(w+D[v]>sD[u])sD[u]=w+D[v];}sv[u]+=sv[v];}
}
第二个dfs
在第二个dfs中,我们将处理整棵树内的信息了。
令 f u f_u fu表示,在整棵树中,从 u u u出发走完所有有家之人再回到自己的最短路程。
在第一个dfs中,我们记录了 s v u sv_u svu表示 u u u子树内有多少有家之人;对于一个节点 u u u和后继结点 v v v,考虑利用 s v u sv_u svu或 s v v sv_v svv进行分类讨论:
s v v = k sv_v=k svv=k
那么和子树的情况没有区别,也不必更新最长链、次长链了,直接 f v = g v f_v=g_v fv=gv即可。
s v v = 0 sv_v=0 svv=0
那么说明 v v v的子树内没有人有家,在第一次dfs时 u u u并没有往 v v v的方向更新。此处可以看作 u u u是在 v v v的子树内,需要倒着用 u u u来更新 v v v。(并且可以直接更新,比大小都可以不需要qwq)
其余情况
u u u和 v v v子树内都有有家之人。设最长链分布如图所示:

设 w w w为边 ( u , v ) (u,v) (u,v)的边权
更新 D v D_v Dv
若 D u + w ≥ D v D_u+w \ge D_v Du+w≥Dv且 n x u ≠ v nx_u \ne v nxu=v(即 v v v不在 u u u的原本的最长链上),直接更新 D v D_v Dv,若 n x u = v nx_u=v nxu=v则不能更新。
若 s D u + w ≥ D v sD_u+w \ge D_v sDu+w≥Dv,并没有影响,直接继承即可。
更新 s D v sD_v sDv
与上相同
void dfs2(ll u,ll fa)
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(v==fa)continue;if(!sv[v])//v子树内无家,倒着更新 {if(D[u]+w>=D[v]){sD[v]=D[v];D[v]=D[u]+w;f[v]=f[u]+2*w;} }else if(k-sv[v]==0)f[v]=g[v];else //更新D(v) {f[v]=f[u];if(D[u]+w>=D[v]&&nx[u]!=v){sD[v]=D[v];D[v]=D[u]+w;nx[v]=u;}else if(sD[u]+w>=D[v]){sD[v]=D[v];D[v]=sD[u]+w;nx[v]=u;}else if(D[u]+w>=sD[v]&&nx[u]!=v)sD[v]=D[u]+w;else if(sD[u]+w>=sD[v])sD[v]=sD[u]+w;}dfs2(v,u);}
}
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=5e5+9;
ll n,k;
ll idx,head[N];
ll sv[N],vis[N],D[N],sD[N],nx[N],f[N],g[N];
//sv(u):u子树内总共多少有家之人
//D/sD(u):u起点最长次长链
//nx(u): 最长链上下一个节点
//g(u):u子树内走完所有有家之人回u的最短距离
//f(u):整棵树内走完所有有家之人回u的最短距离
struct edge
{ll to,next,w;
}e[N<<1];
void addedge(ll u,ll v,ll w)
{idx++;e[idx].to=v;e[idx].next=head[u];e[idx].w=w;head[u]=idx;
}
void dfs1(ll u,ll fa)
{if(vis[u])sv[u]=1;for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(v==fa)continue;dfs1(v,u);if(sv[v]){g[u]+=g[v]+2*w;if(w+D[v]>=D[u]){sD[u]=D[u];D[u]=w+D[v];nx[u]=v;}else if(w+D[v]>sD[u])sD[u]=w+D[v];}sv[u]+=sv[v];}
}
void dfs2(ll u,ll fa)
{for(int i=head[u];i;i=e[i].next){ll v=e[i].to,w=e[i].w;if(v==fa)continue;if(!sv[v])//v子树内无家,倒着更新 {if(D[u]+w>=D[v]){sD[v]=D[v];D[v]=D[u]+w;f[v]=f[u]+2*w;} }else if(k-sv[v]==0)f[v]=g[v];else //更新D(v) {f[v]=f[u];if(D[u]+w>=D[v]&&nx[u]!=v){sD[v]=D[v];D[v]=D[u]+w;nx[v]=u;}else if(sD[u]+w>=D[v]){sD[v]=D[v];D[v]=sD[u]+w;nx[v]=u;}else if(D[u]+w>=sD[v]&&nx[u]!=v)sD[v]=D[u]+w;else if(sD[u]+w>=sD[v])sD[v]=sD[u]+w;}dfs2(v,u);}
}
int main()
{scanf("%lld%lld",&n,&k);for(int i=1;i<n;i++){ll u,v,w;scanf("%lld%lld%lld",&u,&v,&w);addedge(u,v,w);addedge(v,u,w);}for(int i=1;i<=k;i++){ll u;scanf("%lld",&u);vis[u]=1;}dfs1(1,0);f[1]=g[1];dfs2(1,0);for(int i=1;i<=n;i++)printf("%lld\n",f[i]-D[i]);return 0;
}
相关文章:
洛谷 P6419 COCI2014/2015 #1 Kamp 题解
题意 一颗树 n n n 个点, n − 1 n-1 n−1 条边,经过每条边都要花费一定的时间,任意两个点都是联通的。 有 k k k 个人(分布在 k k k 个不同的点)要集中到一个点举行聚会。 聚会结束后需要一辆车从举行聚会的这点…...
在 Vue 项目中使用 SQLite 数据库的基础应用
目录 一、环境准备二、数据库连接与操作1. 创建数据库连接2. 创建表3. 插入数据4. 查询数据5. 更新数据6. 删除数据 三、在 Vue 组件中使用 SQLite 一、环境准备 安装 Node.js 和 npm:确保已安装 Node.js 和 npm。 创建 Vue 项目:使用 Vue CLI 创建一个…...
AI会话问答的页面滚动处理(参考deepseek页面效果)
近期在接入deepseekR1的深度思考,研究了下deepseek官网的滚动效果,大概如下:用户发出消息后,自动滚动到页面最底部,让最新消息展示在视野中,这时候,我们先处理一次滚动: const scrol…...
GRN前沿:DGCGRN:基于有向图卷积网络的基因调控网络推理
1.论文原名:Inference of gene regulatory networks based on directed graph convolutional networks 2.发表日期:2024 DGCGRN框架 中心节点和节点的构建 局部增强策略 1. 问题背景 在基因调控网络中,许多节点的连接度较低(即…...
MongoDB 入门操作指南
文章目录 MongoDB 入门操作指南1. 连接到 MongoDB 数据库2. 查看当前数据库3. 显示所有数据库4. 切换或创建数据库5. 查看当前数据库中的所有集合6. 创建集合7. 插入文档插入单个文档插入多个文档 8. 查询文档查询所有文档查询匹配条件的文档格式化查询输出 9. 更新文档更新单个…...
共享设备管理难?MDM助力Kiosk模式一键部署
目录 1. 简化设备部署与配置:实现一键式部署 2. 自动化应用更新与内容推送:确保设备始终保持最新状态 3. 权限控制与设备安全:防止滥用与数据泄露 4. 远程管理与故障诊断:保障设备长期稳定运行 5. 数据分析与报告:…...
HttpClient-Java程序中发送Http请求
配置 <dependency><groupId>org.apache.httpcomponents</groupId><artifactId>httpclient</artifactId><version>4.5.13</version> </dependency> ps:aliyun-sdk-oss中已引入上述配置 HttpClient的核心API: Htt…...
硬件-电源-隔离与非隔离的区别
文章目录 一:隔离电源与非隔离电源1.1 充电器触电新闻1.2 电路拓扑1.3 隔离电源与非隔离电源的优缺点1.3 隔离电源与非隔离电源的选择1.3.1 隔离电源1.3.2 非隔离电源 二:注意事项2.1 隔离电源结构图2.1 隔离耐压测试方法 三:感悟道友&#x…...
Kubernetes 最佳实践:Top 10 常见 DevOps/SRE 面试问题及答案
1. 如何在 Kubernetes 中设置资源请求和限制? 资源请求确保容器有最小资源量(CPU/内存),而限制则强制容器消耗的最大资源量。这有助于高效资源分配并防止资源争用。 示例: resources:requests:memory: "256Mi&…...
Training for Computer Use
Training for Computer Use 核心事件:多家科技公司推出能操控计算机的智能体,字节跳动和清华大学团队引入UI - TARS模型,展示了训练模型实现计算机操控能力的新成果。 UI - TARS模型 基本信息:是视觉 - 语言模型Qwen2 - VL的微调版…...
PH热榜 | 2025-02-14
1. Beatoven.ai 标语:能创作完美背景音乐的AI作曲家 介绍:Beatoven.ai 能根据简单的提示生成惊艳的背景音乐,用于你的内容创作。它是由世界各地的真实音乐家倾力打造(并使用了大量数据)。无需任何音乐专业知识&#…...
工业物联网远程监控系统优化方案,基于巨控GRM553Y-CHE
工业物联网远程监控系统优化方案 ——基于巨控GRM553Y-CHE的西门子S7-1500 PLC多站点无线集成方案 1. 项目背景与概述 巨控科技作为工业物联网解决方案提供商,专注于PLC无线通信与远程监控技术研发,其YunPLC安全平台已服务超30,000工业终端,…...
报名丨Computer useVoice Agent :使用 TEN 搭建你的 Mac Assistant
与 TEN 相聚在「LET’S VISION 2025」大会,欢迎来展位上跟我们交流。这次我们还准备了一场聚焦「computer use」的工作坊,功能新鲜上线,线下首波体验! 📅 TEN 展位:2025年3月1日-2日 TEN workshop&#x…...
Flutter 中的生命周期
在 Flutter 中,StatefulWidget 和 StatelessWidget 这两种 Widget 的生命周期不同,主要关注的是 StatefulWidget,因为它涉及到状态的管理和更新。 StatefulWidget 的生命周期: 1. 创建阶段 (Create) createState():…...
深度整理总结MySQL——redoLog日志工作原理
redo log的工作原理 前言概念为什么需要redo log修改undo页面,会记录对应的redo log吗redo log 和undo log 区别在哪什么是WAL技术redo log要写入磁盘,数据也要写入磁盘,为什么多此一举产生的redo log直接写入磁盘吗redo log 什么时候刷盘innodb_flush_log_at_trx_commit 参数参…...
备战蓝桥杯 Day1 回顾语言基础
开启蓝桥杯刷题之路 Day1 回顾语言基础 1.配置dev 工具->编译选项->勾选编译时加入以下命令->设定编译器配置(release和debug)都要-> -stdc11 ->代码生成/优化->代码生成/优化->语言标准(-std)->ISO C11 ->代码警告->显示最多警告信息(-Wall)…...
小记大模型本地部署:vllm, lmdeploy, ollama
记录一下最近折腾的大模型本地部署。由于学校有部署deepseek的竞赛(觉得扯不?)所以首选ollama这种超级简单的来过关,但我最希望的还是用专门的推理工具部署,因为做应用开发推理速度一定最重要。所以先尝试自己想搞的vl…...
MySQL查看存储过程和存储函数
【图书推荐】《MySQL 9从入门到性能优化(视频教学版)》-CSDN博客 《MySQL 9从入门到性能优化(视频教学版)(数据库技术丛书)》(王英英)【摘要 书评 试读】- 京东图书 (jd.com) MySQL9数据库技术_夏天又到了…...
从零到一:开发并上线一款极简记账本小程序的完整流程
从零到一:开发并上线一款极简记账本小程序的完整流程 目录 前言需求分析与功能设计 2.1 目标用户分析2.2 核心功能设计2.3 技术栈选择 开发环境搭建 3.1 微信开发者工具安装与配置3.2 项目初始化3.3 版本控制与协作工具 前端开发 4.1 页面结构与布局4.2 组件化开发…...
卷积神经网络实战人脸检测与识别
文章目录 前言一、人脸识别一般过程二、人脸检测主流算法1. MTCNN2. RetinaFace3. CenterFace4. BlazeFace5. YOLO6. SSD7. CascadeCNN 三、人脸识别主流算法1.deepface2.FaceNet3.ArcFace4.VGGFace5.DeepID 四、人脸识别系统实现0.安装教程与资源说明1. 界面采用PyQt5框架2.人…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
DBAPI如何优雅的获取单条数据
API如何优雅的获取单条数据 案例一 对于查询类API,查询的是单条数据,比如根据主键ID查询用户信息,sql如下: select id, name, age from user where id #{id}API默认返回的数据格式是多条的,如下: {&qu…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
【实施指南】Android客户端HTTPS双向认证实施指南
🔐 一、所需准备材料 证书文件(6类核心文件) 类型 格式 作用 Android端要求 CA根证书 .crt/.pem 验证服务器/客户端证书合法性 需预置到Android信任库 服务器证书 .crt 服务器身份证明 客户端需持有以验证服务器 客户端证书 .crt 客户端身份…...
如何把工业通信协议转换成http websocket
1.现状 工业通信协议多数工作在边缘设备上,比如:PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发,当设备上用的是modbus从站时,采集设备数据需要开发modbus主站;当设备上用的是西门子PN协议时…...
高效的后台管理系统——可进行二次开发
随着互联网技术的迅猛发展,企业的数字化管理变得愈加重要。后台管理系统作为数据存储与业务管理的核心,成为了现代企业不可或缺的一部分。今天我们要介绍的是一款名为 若依后台管理框架 的系统,它不仅支持跨平台应用,还能提供丰富…...
【工具教程】多个条形码识别用条码内容对图片重命名,批量PDF条形码识别后用条码内容批量改名,使用教程及注意事项
一、条形码识别改名使用教程 打开软件并选择处理模式:打开软件后,根据要处理的文件类型,选择 “图片识别模式” 或 “PDF 识别模式”。如果是处理包含条形码的 PDF 文件,就选择 “PDF 识别模式”;若是处理图片文件&…...
