当前位置: 首页 > news >正文

旅游规划(树型dp)

 

W 市的交通规划出现了重大问题,市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。

但由于人员不足,W 市市长决定只在最需要安排人员的路口安排人员。

具体来说,W 市的交通网络十分简单,由 n 个交叉路口和 n−1 条街道构成,交叉路口路口编号依次为 0,1,…,n−1 。

任意一条街道连接两个交叉路口,且任意两个交叉路口间都存在一条路径互相连接。

经过长期调查,结果显示,如果一个交叉路口位于 W 市交通网最长路径上,那么这个路口必定拥挤不堪。

所谓最长路径,定义为某条路径 p=(v1,v2,…,vk),路径经过的路口各不相同,且城市中不存在长度大于 k 的路径(因此最长路径可能不唯一)。

因此 W 市市长想知道哪些路口位于城市交通网的最长路径上。

输入格式

第一行包含一个整数 n

之后 n−1行每行两个整数 u,v,表示编号为 u和 v 的路口间存在着一条街道。

输出格式

输出包括若干行,每行包括一个整数——某个位于最长路径上的路口编号。

为了确保解唯一,请将所有最长路径上的路口编号按编号顺序由小到大依次输出。

数据范围

1≤n≤2×105

输入样例:

10
0 1
0 2
0 4
0 6
0 7
1 3
2 5
4 8
6 9

输出样例:

0
1
2
3
4
5
6
8
9

两次dfs第一次求树的直径和当前点向下的最大值和次大值,第二次求当前点向上的最大值 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
constexpr int N=1e6+7;
int n,d1[N],d2[N],p[N],up[N];
int h[N],e[N],ne[N],idx;
int maxd;
void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
void dfs_d(int u,int f){for(int i=h[u];i!=-1;i=ne[i]) {int j = e[i];if (j != f) {dfs_d(j, u);int dis = d1[j] + 1;if (dis > d1[u]) {d2[u] = d1[u], d1[u] = dis;p[u] = j;} else if (dis > d2[u]) {d2[u] = dis;}}}maxd= max(maxd,d1[u]+d2[u]);
}
void dfs_u(int u,int f){for(int i=h[u];i!=-1;i=ne[i]) {int j = e[i];if (j != f) {up[j]=up[u]+1;if(p[u]==j) up[j]= max(up[j],d2[u]+1);else up[j]= max(up[j],d1[u]+1);dfs_u(j,u);}}
}
int main(){memset(h,-1,sizeof h);scanf("%d",&n);for(int i=1;i<n;i++){int a,b;scanf("%d%d",&a,&b);add(a,b),add(b,a);}dfs_d(0,-1);dfs_u(0,-1);for (int i = 0; i < n; i++){int a[3] = {up[i], d1[i], d2[i]};sort(a, a + 3);if (a[1] + a[2] == maxd){printf("%d\n",i);}}return 0;
}

 

相关文章:

旅游规划(树型dp)

W 市的交通规划出现了重大问题&#xff0c;市政府下定决心在全市各大交通路口安排疏导员来疏导密集的车流。 但由于人员不足&#xff0c;W 市市长决定只在最需要安排人员的路口安排人员。 具体来说&#xff0c;W 市的交通网络十分简单&#xff0c;由 n 个交叉路口和 n−1 条街道…...

【C++】string类的模拟实现

当你将放弃作为一种习惯&#xff0c;你一辈子也不会有出息… 文章目录一、Default member functions1.Constructor2.Copy constructor&#xff08;代码重构&#xff1a;传统写法和现代写法&#xff09;3.operator&#xff08;代码重构&#xff1a;传统写法和现代写法&#xff…...

笔记(一)——STL容器

容器分类&#xff1a;序列式容器&#xff1a;每个元素都有固定位置&#xff0c;取决于插入的时机和地点&#xff0c;和元素无关&#xff0c;如vector、deque、list、stack、queue。关联式容器&#xff1a;元素位置取决于特定的排序准则&#xff0c;和插入顺序无关&#xff0c;如…...

红黑树

红黑树是一个相对的平衡&#xff0c;减少了旋转的消耗 一个节点不是红的就是黑的根节点是黑的一个节点是红的&#xff0c;孩子是黑的&#xff08;没有连续的红色节点&#xff09;对于每个节点&#xff0c;从该节点到后代节点的简单路径&#xff0c;都包含相同的黑色&#xff0…...

RIP路由协议的更新(电子科技大学TCP/IP第二次实验)

一&#xff0e;实验目的 1、掌握 RIP 协议在路由更新时的发送信息和发送方式 2、掌握 RIP 协议的路由更新算法 二&#xff0e;预备知识 1、静态路由选择和动态路由选择 2、内部网关协议和外部网关协议 3、距离向量路由选择 三&#xff0e;实验原理 RIP 协议&#xff08…...

基于JWT实现用户身份认证

常见场景 账号/密码登录、手机号验证码登录、微信扫码登录 解决方案 基于Session认证方案 什么是session认证方案 服务端生成httpsession认证(内存-sessionId)sessionId写到浏览器cookie浏览器请求的header中自动带sessionId到服务端服务端校验sessionId是否合法 优点 .…...

SaltStack 远程命令执行漏洞(CVE-2020-16846)

目录 (一)漏洞描述 (二)漏洞复现 1、在vulhub上启动docker 2、访问docker靶机 https /ip:8000...

SAP 详细解析成本收集器

成本收集器作为成本对象&#xff0c;主要应用于按期间进行成本核算的情况&#xff0c;在这种情况下会把产品创建为成本收集器&#xff0c;实际成本的收集和差异的结算全部按照成本收集器进行处理&#xff0c;财务的成本分析也针对成本收集器进行。 成本收集器是按期间核算&am…...

Vision Transformer学习了什么-WHAT DO VISION TRANSFORMERS LEARN? A VISUAL EXPLORATION

WHAT DO VISION TRANSFORMERS LEARN? A VISUAL EXPLORATION 文章地址 代码地址 摘要 视觉转换器( Vision Transformers&#xff0c;ViTs )正在迅速成为计算机视觉的事实上的架构&#xff0c;但我们对它们为什么工作和学习什么知之甚少。虽然现有研究对卷积神经网络的机制进…...

一种全新的图像滤波理论的实验(三)

一、前言 2023年02月22日&#xff0c;我发布了滤波后&#xff0c;为针对异常的白色和黑色像素进行处理的实验&#xff0c;本次发布基于上下文处理的方案的实验&#xff0c;目的是通过基于加权概率模型滤波后&#xff0c;在逆滤波时直接修复大量的白色和黑色的异常像素&#xf…...

CV——day79 读论文:基于小目标检测的扩展特征金字塔网络

Extended Feature Pyramid Network for Small Object DetectionI. INTRODUCTIONII. RELATED WORKA. 深层物体探测器B. 跨尺度特征C. 目标检测中的超分辨率III. OUR APPROACHA. 扩展特征金字塔网络B. 特征纹理传输C. 交叉分辨蒸馏IV. EXPERIMENTSA. Experimental Settings1&…...

智能家居项目(五)测试串口功能

目录 一、写一个单独测试串口的demo 二、直接运行上一篇智能家居的代码 一、写一个单独测试串口的demo 1、TTL串口与树莓派的连接方式 &#xff08;1&#xff09;TTL的RXD和TXD针脚连接到树莓的TXD和RXD上&#xff08;T–>R R–>T&#xff09;&#xff0c;交叉连&…...

2023年全国最新道路运输从业人员精选真题及答案7

百分百题库提供道路运输安全员考试试题、道路运输从业人员考试预测题、道路安全员考试真题、道路运输从业人员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 71.根据《中华人民共和国安全生产法》&#xff0c;生产经营单位…...

python的所有知识点(含讲解),不看就亏死了

目录 简介 特点 搭建开发环境 版本 hello world 注释 文件类型 变量 常量 数据类型 运算符和表达式 控制语句 数组相关 函数相关 字符串相关 文件处理 对象和类&#xff0c;注&#xff1a;不是那个对象&#xff01;&#xff01;&#xff01;&#xff01;&…...

【Servlet篇】Response对象详细解读

文章目录Response 继承体系Response 设置响应数据设置响应行数据设置响应头数据设置响应体数据Response 重定向Response 响应字符数据Response 响应字节数据Response 继承体系 前面说到&#xff0c;我们使用 Request 对象来获取请求数据&#xff0c;使用 Response 对象来设置响…...

SAP FICO期初开账存货导入尾差

一、问题 1.AFS物料网格级别库存导入先除再乘有尾差&#xff1a; 旧系统数据迁移自两个系统&#xff1a;一个管理数量账&#xff08;网格级别&#xff09;&#xff0c;一个管理金额账&#xff08;物料级别&#xff09; 2.MB52分工厂与MB5L分工厂统计差异&#xff1a; M…...

微信商城小程序怎么做_分享实体店做微信商城小程序制作步骤

各行各业都在用微商城小程序开店&#xff0c;不管是餐饮店还是便利店&#xff0c;还是五金店。都是可以利用微信小程序开一个线上店铺。实现线上跟线下店铺更加全面的结合。维护好自己的老客户。让您的客户给您拉新&#xff0c;带来新客户。小程序经过这几年的快速发展和不断升…...

【moment.js】时间格式化插件

Moment.js 用于在JavaScript中解析&#xff0c;验证&#xff0c;操作和显示日期和时间。是一款在项目中使用频率极高的时间格式化工具&#xff0c;Ant Design Vue 组件中就是使用它来处理时间的。 安装 npm install moment --save # npm yarn add moment # Ya…...

微信小程序开发【壹】

随手拍拍&#x1f481;‍♂️&#x1f4f7; 日期: 2023.02.24 地点: 杭州 介绍: 2023.02.24上午十点&#xff0c;路过学院的教学楼时&#x1f3e2;&#xff0c;突然看见了一团粉红色。走进一看是一排梅花&#x1f338;&#xff0c;赶在它们凋零前&#xff0c;将它们定格在我的相…...

2 k-近邻算法

0 问题引入 想一想&#xff1a;下面图片中有三种豆&#xff0c;其中三颗豆品种未知&#xff0c;如何判断他们类型&#xff1f; 1 KNN概述 1.1 KNN场景 电影可以按照题材分类&#xff0c;那么如何区分 动作片 和 爱情片 呢&#xff1f; 动作片&#xff1a;打斗次数更多爱情…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》

在注意力分散、内容高度同质化的时代&#xff0c;情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现&#xff0c;消费者对内容的“有感”程度&#xff0c;正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中&#xff0…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...