首页 / 资讯中心 / 文章详情

洛谷-P6838 [IOI 2020] 网络站点 题解

📅 2026/7/2 3:25:12 👁️ 次浏览
洛谷-P6838 [IOI 2020] 网络站点 题解
无根树不好想钦定 00 为根转化成有根树。从 s 出发要么走向父亲要么走向某个儿子。需要通过标签判断 t 是否在某个儿子的子树内。容易想到记录每个点 u 对应的 dfn 区间 [,][lu​,ru​] 就能把子树关系转成区间包含关系。我们直接把 [,][lu​,ru​] 存进编号比如存 ×1000lu​×1000ru​。但是这样会有不少冗余。事实上只需要知道 lu​ 和所有儿子的 r或者反之就能确定子树结构。考虑交错存储奇数层存 l偶数层存 r。不过还有一个问题对于奇数层的点 urfau​​ 等于最后一个儿子的 r导致分不清这两个点。为何偶数层没有这个问题呢因为 lfau​​dfnfau​​不会等于第一个儿子的 l。这启发我们让所有偶数层的点 u 满足 ru​dfnu​。也就是奇数层前序 dfs偶数层后序 dfs。Code#include stations.h#include bits/stdc.h#define rep(i,a,b) for(int i(a);ib;i)#define rept(i,a,b) for(int i(a);ib;i)#define eb emplace_backusing namespace std;constexpr int N1e35;vectorint g[N],res;int d[N],cnt;void dfs(int u,int pre){ // 奇数层前序偶数层后序if(d[u]1) res[u]cnt;for(int v:g[u]) if(v^pre) d[v]d[u]1,dfs(v,u);if(~d[u]1) res[u]cnt;}vectorint label(int n,int k,vectorint u,vectorint v){res.resize(n),cnt0;rep(i,0,n) g[i].clear(),d[i]0;rep(i,0,u.size()) g[u[i]].eb(v[i]),g[v[i]].eb(u[i]);dfs(0,0);return res;}int find_next_station(int s,int t,vectorint c){if(c[0]s){sort(c.begin(),c.end());int fac.back(),lsts1;c.pop_back();for(int x:c){if(lstttx) return x;lstx1;}return fa;}else{sort(c.begin(),c.end(),greaterint());int fac.back(),lsts-1;c.pop_back();for(int x:c){if(xttlst) return x;lstx-1;}return fa;}}

相关新闻

智能体从“会执行”到“会进化”：持续学习与自我迭代的系统设计

智能体从“会执行”到“会进化”：持续学习与自我迭代的系统设计

引言：智能体进化的分水岭时刻 2026年，AI智能体正站在一个关键的分水岭上。 根据中国信通院2026年6月发布的《2026智能体十大关键词》，“智能体学习进化”与“智能体记忆”“智能体技能”并列成为产业演进的核心方向。与此同时，一个惊人的数据浮出水面：2026年第二季度平均…

📅 2026/7/2 3:25:12
缠论自动化分析终极指南：5分钟掌握ChanlunX核心价值

缠论自动化分析终极指南：5分钟掌握ChanlunX核心价值

缠论自动化分析终极指南：5分钟掌握ChanlunX核心价值 【免费下载链接】ChanlunX 缠中说禅炒股缠论可视化插件 项目地址: https://gitcode.com/gh_mirrors/ch/ChanlunX 还在为缠论分析中的复杂笔段划分而烦恼吗？ChanlunX缠论插件正是为你量身定制的…

📅 2026/7/2 3:23:12
武汉农商银行13名员工手工拼接碎币，帮失智老人兑换养老金

武汉农商银行13名员工手工拼接碎币，帮失智老人兑换养老金

6月30日，武汉农商银行发布消息称，该行13名员工耗时22天，手工拼接一名八旬失智老人撕碎的养老金纸币，并最终完成兑换。此次被拼接的现金原本预计约为20万元，经过整理、拼接和鉴定后，最终兑换金额达到266600元…

📅 2026/7/2 3:23:12
Day2：AI 时代普通人的核心护城河是什么

Day2：AI 时代普通人的核心护城河是什么

教学重点拆解 AI 无法复刻的 5 大人类独有核心能力，搭建普通人专属职业护城河；区分 “AI 擅长事” 与 “人类不可替代事”，教会学员把五大能力转化为职场竞争力。一、课堂导入（承接 Day1 内容）昨天我们明确&#xff1a…

📅 2026/7/2 4:39:19
三步实现B站缓存视频永久保存：m4s-converter工具使用全指南

三步实现B站缓存视频永久保存：m4s-converter工具使用全指南

三步实现B站缓存视频永久保存：m4s-converter工具使用全指南 【免费下载链接】m4s-converter 一个跨平台小工具，将bilibili缓存的m4s格式音视频文件合并成mp4 项目地址: https://gitcode.com/gh_mirrors/m4/m4s-converter 当你发现收藏的B站视频突…

📅 2026/7/2 4:39:19
数字人源头贴牌OEM，开启自己的数字人品牌

数字人源头贴牌OEM，开启自己的数字人品牌

这两年，AI数字人越来越火。很多企业开始用数字人做短视频、做老板IP、做产品介绍、做客户沟通。对于中小企业来说，数字人真正解决的不是“炫酷”问题，而是内容生产成本太高、老板不愿出镜、团队难以持续更新的问题。过去企业做短视频&#xf…

📅 2026/7/2 4:39:19
Dify知识库数据断裂漏洞：附件ID校验缺失与竞态条件分析

Dify知识库数据断裂漏洞：附件ID校验缺失与竞态条件分析

1. 项目概述：一个被忽视的“小”漏洞最近在排查一个线上Dify应用的数据问题时，发现了一个相当隐蔽但后果可能很严重的问题。这个问题源于Dify在处理文件上传和知识库构建时，对附件ID的校验逻辑存在一个潜在的漏洞。简单来说，在某些…

📅 2026/7/2 4:37:19
Selenium元素定位全解析：从八大方法到实战策略

Selenium元素定位全解析：从八大方法到实战策略

1. 项目概述：从“找东西”到“精准操控” 做自动化测试，尤其是Web UI自动化，最核心也最让人头疼的一步是什么？不是写复杂的业务逻辑，也不是处理异步加载，而是最基础的—— 让程序找到页面上那个你想操作的…

📅 2026/7/2 0:00:33
移动端UI自动化测试框架Maestro终极指南：从入门到实战

移动端UI自动化测试框架Maestro终极指南：从入门到实战

1. 项目概述：为什么是Maestro？ 如果你正在寻找一个能让你快速上手、告别繁琐配置、并且对移动端UI自动化测试真正友好的框架，那么Maestro很可能就是你一直在等的那个答案。我接触过Appium、Espresso、XCUITest，也折腾过各种基于图…

📅 2026/7/2 0:00:33
审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？

审计来了，数据权限全开——审计走了，怎么确保权限全部关掉？

引言：审计结束三个月了，审计员的权限还没关某城商行每年按照监管要求开展至少一次数据安全审计。审计期间，内审部门需要抽样检查各类业务数据——交易流水、客户信息、员工操作日志、权限配置记录。这些数据分布在不同系统中，审计…

📅 2026/7/1 15:35:39
基于Dify与DeepSeek构建私有知识库问答系统实战指南

基于Dify与DeepSeek构建私有知识库问答系统实战指南

在业务中快速构建一个能理解私有文档、准确回答专业问题的智能助手，是很多开发团队面临的共同挑战。传统方案往往需要从零开始搭建复杂的 RAG（检索增强生成）系统，涉及文档解析、向量化、检索、大模型调用等多个环节，整…

📅 2026/7/1 0:00:39
FAE放射组学分析工具：医学影像特征探索的完整解决方案

FAE放射组学分析工具：医学影像特征探索的完整解决方案

FAE放射组学分析工具：医学影像特征探索的完整解决方案 【免费下载链接】FAE FeAture Explorer 项目地址: https://gitcode.com/gh_mirrors/fae/FAE 你是否曾经面对海量医学影像数据感到无从下手？想要从CT、MRI等影像中提取有价值的定量特征&#…

📅 2026/7/2 1:36:45