洛谷 P3478 [POI 2008] STA-Station

【题目链接】

洛谷 P3478 [POI 2008] STA-Station

【题目考点】

1. 树形动规:换根动规

换根动规,又名二次扫描法,一般是给一颗不定根树,通过两次扫描来求解。
我们可以先任选一个根结点root,通过树形动规的思想计算出一个答案。再考虑当root的子结点作为根结点时,答案的变化。
换根动规的三个步骤:

  1. 指定某个结点为根结点root。
  2. 第一次搜索完成预处理,得到以root为根的解。孩子=>根。
  3. 第二次搜索进行换根动规,由已知解的结点推出相邻结点的解。根=>孩子。

【解题思路】

dpdpdp数组,dpudp_udpu表示以结点u为整棵树的根时所有结点的深度之和,在无权图中,就是所有结点到根结点的路径长度之和。
sizusiz_usizu表示在有根树中以u为根的子树的结点数量。
先将结点1设为整棵树的根结点,进行第一趟dfs,深搜时可知访问到的结点的深度,将深度加和保存在dp1dp_1dp1。与此同时可以求出sizsizsiz数组,即以结点1为根的有根树中每个子树的结点数。
接下来第二趟dfs,进行换根动规。dfs从结点u访问到邻接点v时,就尝试将整棵树的根从结点u转移到结点v,考察转移后所有结点到整棵树根结点的路径加和的变化。
以v为根的子树中的结点从考虑到结点u的路径转变为考虑到结点v的路径,每条路径长度减少1,共有sizvsiz_vsizv个结点到根结点的路径长度减少,总减少长度为sizvsiz_vsizv
v的上方子树(除去以v为根的子树外其它结点构成的子树)的结点数为n−sizvn-siz_vnsizv,从考虑这些结点到结点u的路径转为考虑这些结点到结点v的路径,每条路径长度增加1,总增加长度为n−sizvn-siz_vnsizv
因此以结点v为整棵树根结点时,所有结点到v的路径长度加和即所有结点的深度加和为dpv=dpu−sizv+n−sizvdp_v = dp_u-siz_v+n-siz_vdpv=dpusizv+nsizv。这是从双亲到孩子的转移,因此该状态转移方程应该写在调用dfs从孩子开始搜索的语句之前。
最后求出dp数组大值的下标,即为本题的结果。求最大值下标的过程可以在dfs的过程中进行。

【题解代码】

解法1:树形动规 换根动规

#include<bits/stdc++.h>
using namespace std;
#define N 1000005
int n, dep[N], siz[N], mxi = 1;
vector<int> edge[N];
long long dp[N];//dp[u]:整棵树以u为根时所有结点的深度之和 
void dfs1(int u, int fa, int dep)
{dp[1] += dep;siz[u] = 1;for(int v : edge[u]) if(v != fa){dfs1(v, u, dep+1);siz[u] += siz[v];}
}
void dfs2(int u, int fa)
{for(int v : edge[u]) if(v != fa){dp[v] = dp[u]-siz[v]+n-siz[v];dfs2(v, u);}if(dp[u] > dp[mxi])mxi = u;
}
int main()
{int u, v;cin >> n;for(int i = 1; i < n; ++i){cin >> u >> v;edge[u].push_back(v);edge[v].push_back(u);}dfs1(1, 0, 0);dfs2(1, 0);cout << mxi;return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/pingmian/89960.shtml
繁体地址,请注明出处:http://hk.pswp.cn/pingmian/89960.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【爬虫】03 - 爬虫的基本数据存储

爬虫03 - 爬虫的数据存储 文章目录爬虫03 - 爬虫的数据存储一&#xff1a;CSV数据存储1&#xff1a;基本介绍2&#xff1a;基本使用3&#xff1a;高级使用4&#xff1a;使用示例二&#xff1a;JSON数据存储1&#xff1a;基础json读写2&#xff1a;字符串和对象的转换3&#xff…

深入分析计算机网络数据链路层和网络层面试题

计算机网络体系结构1. 请简述 OSI 七层模型和 TCP/IP 四层模型&#xff0c;并比较它们的异同。OSI 七层模型&#xff1a;应用层&#xff1a;直接为用户的应用进程提供服务&#xff0c;如 HTTP&#xff08;超文本传输协议&#xff0c;用于 Web 浏览器与服务器通信&#xff09;、…

云服务器新装的mysql8,无法通过远程连接,然后本地pymysql也连不上

阿里云服务器&#xff0c;用apt-get新装的mysql-server&#xff0c;竟然无法通过远程连接到&#xff0c;竟然是这个原因。不是防火墙&#xff0c;iptables早就关了。也不是安全组&#xff0c;不是人为限制访问的话&#xff0c;根本没必要弄安全组 排查过程 netstat -antop|grep…

质量即服务:从测试策略到平台运营的全链路作战手册

&#xff08;零&#xff09;为什么需要“质量即服务” 当业务方说“今晚一定要上线”&#xff0c; 当开发说“我只改了两行代码”&#xff0c; 当运维说“回滚窗口只有 5 分钟”&#xff0c; 质量必须像水电一样随取随用&#xff0c;而不是上线前的大坝泄洪。 这篇手册提供一张…

Java -- 自定义异常--Wrapper类--String类

自定义异常&#xff1a;概念&#xff1a;当程序中出现了某些错误&#xff0c;但该错误信息并没有在Throwable子类中描述处理&#xff0c;这个时候可以自己设计异常&#xff0c;用于描述该错误信息。步骤&#xff1a;1. 定义类&#xff1a;自定义异常类名&#xff08;程序员自己…

一文速通《线性方程组》

目录 一、解题必记知识点 二、解题必备技巧 三、非齐次线性方程组求解 四、齐次线性方程组求解 ★五、解析题目信息&#xff0c;获取暗含条件 一、解题必记知识点 (1) (2)基础解系线性无关&#xff0c;基础解系 解空间的一个基&#xff0c;基 一组线性无关的、能够生…

【Django】DRF API版本和解析器

讲解 Python3 下 Django REST Framework (DRF) API 版本控制解析器&#xff08;Parser&#xff09;一、DRF API 版本控制详解 API 版本控制是构建健壮、可维护的 RESTful API 的关键&#xff0c;尤其在项目演进中需要兼容不同版本的客户端请求。 1.1 API 版本控制的核心原理 AP…

Windows系统暂停更新工具

功能说明 暂停更新至2999年恢复系统更新彻底禁用更新&#xff08;不可逆&#xff09; 使用方法 下载解压后双击运行 .bat 文件 输入数字选择功能&#xff1a; 输入 1&#xff1a;暂停更新至2999年&#xff08;推荐&#xff09;输入 2&#xff1a;恢复系统更新输入 3&#xf…

git push新版问题解决

git 好像不能通过username:password的方式来git push了。但我的电脑依然弹出username和password的弹窗。转战ssh来git push。由于之前是用git clone克隆的&#xff0c;需要再转换成ssh的url来git push。

PyCharm + AI 辅助编程

PyCharm AI&#xff1a;初学者友好的 2 个实用场景&#xff08;附操作步骤&#xff09; PyCharm 专业版&#xff08;或通过插件集成&#xff09;支持 AI 辅助编程&#xff08;如 JetBrains AI 或 GitHub Copilot&#xff09;&#xff0c;能根据代码上下文自动生成代码、解释逻…

疯狂星期四文案网第15天运营日记

网站运营第15天&#xff0c;点击观站&#xff1a; 疯狂星期四 crazy-thursday.com 全网最全的疯狂星期四文案网站 运营报告 昨日访问量 昨天只有20来ip, 太惨了&#xff0c;感觉和最近没有发新段子有关&#xff0c;也没有发新的外链&#xff0c;不知道这周四会怎么样 昨日搜…

如何解决pip安装报错ModuleNotFoundError: No module named ‘Cython’问题

【Python系列Bug修复PyCharm控制台pip install报错】如何解决pip安装报错ModuleNotFoundError: No module named ‘Cython’问题 摘要 在使用 PyCharm 控制台或命令行执行 pip install Cython 时&#xff0c;常会遇到 ModuleNotFoundError: No module named Cython 的报错。本…

freertos任务调度关键函数理解 vTaskSwitchContext

void vTaskSwitchContext(void) {//my_printf( "uxSchedulerSuspended %d\n", uxSchedulerSuspended );/* 调度器处于挂起状态 */if (uxSchedulerSuspended ! (UBaseType_t)pdFALSE) {/*** The scheduler is currently suspended - do not allow a context* switch.…

CPU 密集型 和 I/O 密集型 任务

文章目录**CPU 密集型任务&#xff08;CPU-bound&#xff09;**定义&#xff1a;特点&#xff1a;常见场景&#xff1a;如何优化 CPU 密集型任务&#xff1a;**I/O 密集型任务&#xff08;I/O-bound&#xff09;**定义&#xff1a;特点&#xff1a;常见场景&#xff1a;如何优化…

[2025CVPR-小目标检测方向]基于特征信息驱动位置高斯分布估计微小目标检测模型

核心问题 ​小目标检测性能差&#xff1a;​​ 尽管通用目标检测器&#xff08;如 Faster R-CNN, YOLO, SSD&#xff09;在常规目标上表现出色&#xff0c;但在检测微小目标&#xff08;如 AI-TOD 基准定义的&#xff1a;非常小目标 2-8 像素&#xff0c;小目标 8-16 像素&…

三大工厂设计模式

1.简单工厂模式1.1需求入手从需求进行入手&#xff0c;可以更深入的理解什么是设计模式。有一个制作披萨的需求&#xff1a;需要便于扩展披萨的种类&#xff0c;便于维护。1.披萨的种类有很多&#xff1a;GreekPizz&#xff0c;CheesePizz等2.披萨的制作流程&#xff1a;prepar…

SpringBoot--Mapper XML 和 Mapper 接口在不同包

&#x1f9e9; 背景说明在 Spring Boot 中&#xff0c;MyBatis 默认要求 Mapper 接口和 XML 文件位于相同包路径。 但在实际项目中&#xff0c;为了模块化或结构清晰&#xff0c;常将 XML 放在 resources/mybatis/... 下&#xff0c;这种做法就必须进行额外配置。&#x1f4c1;…

公交车客流人数统计管理解决方案:智能化技术与高效运营实践

1. 引言公交车作为城市公共交通的核心组成部分&#xff0c;其客流数据的精准统计与管理直接影响运营效率、调度优化和乘客体验。传统的人工统计方式效率低、误差大&#xff0c;难以满足现代智慧交通的需求。随着人工智能&#xff08;AI&#xff09;、物联网&#xff08;IoT&…

正则表达式完全指南:从入门到实战

目录 一、什么是正则表达式&#xff1f; 二、基础语法速查表 三、进阶特性 1.分组与捕获 2.非捕获分组 3.前瞻与后顾 4.贪婪与懒惰匹配 四、实战案例 案例1&#xff1a;验证手机号 案例2&#xff1a;提取网页中所有链接 案例3&#xff1a;密码强度验证 一、什么是正…

SmartETL循环流程的设计与应用

1. 引言 **检索增强生成&#xff08;RAG&#xff09;**是指通过检索对大模型生成进行增强的技术&#xff0c;通过充分利用信息检索&#xff08;尤其是语义检索&#xff09;相关技术&#xff0c;实现大模型快速扩展最新知识、有效减少幻觉的能力。主流RAG框架包括问题理解、知识…