首页 > 其他分享 >[ABC148F] Playing Tag on Tree

[ABC148F] Playing Tag on Tree

时间:2023-05-01 16:11:06浏览次数:49  
标签:题目 ABC148F 短路 Tree Tag Playing

2023-03-04

题目

题目传送门

翻译

翻译

难度&重要性(1~10):5

题目来源

AtCoder

题目算法

最短路

解题思路

考虑到 T 想活得久, A 想尽早追上 T ,所以我们就将问题转化为在树上找一条最长链,使得 T 能比 A 先到达这条链。
所以我们就可以在树上跑两遍单源最短路,因为边权为 \(1\),所以用 BFS 就可以了

完成状态

已完成

标签:题目,ABC148F,短路,Tree,Tag,Playing
From: https://www.cnblogs.com/OIerBoy/p/17366632.html

相关文章

  • CF 1709E XOR Tree(树上启发式合并)
    题目链接:https://codeforces.com/contest/1709/problem/E解题思路:定义sum(x,y)为x→y路径上的点的异或和,dx 为x→root路径上的点的异或和。对于一个点权树,sum(x,y)=dx ^dy ^vallca(x,y)。考虑修改一个点,可以将它改为一个很大的2为底数的幂,则经过此点的所有的不合......
  • AtCoder Regular Contest 117 D Miracle Tree
    洛谷传送门AtCoder传送门第一步就没想到可以考虑化简限制。设所有点按\(E_i\)从小到大排序后顺序是\(p_1,p_2,...,p_n\)。发现只需满足\(E_{p_{i+1}}-E_{p_i}\ge\operatorname{dis}(p_i,p_{i+1})\)。证明是对于任意\(i<j<k\),若\(p_i,p_j\)和\(p_j,p_k\)均满......
  • Grids for mac(Instagram客户端工具)v8.5.5免注册版
    GridsforMac是一款允许您在桌面上访问Instagram的应用程序。使用网格,您可以像在手机上一样查看您的Instagram提要、故事和探索页面。您还可以发布照片和视频,对帖子点赞和评论,以及向其他用户发送直接消息。Grids具有简洁、直观的界面,易于使用。它还提供了多种自定义选项,包......
  • Codeforces 1799H - Tree Cutting(树形 dp)
    思考的时候一直卡在不会在低于\(O(n)\)的时间内储存一个连通块的\(siz\)有关的信息,看了洛谷题解之后才发现我真是个小丑。树形DP。对于一条我们需要操作的边\((i,fa_i)\),我们将其分为保留子树和删除子树两种类型,对于删除子树,我们在判定其是否合法时候改为判定删除的连通块......
  • 二叉树Binary Tree
    二叉树BinaryTree1.树的一些常用术语2.二叉树的概念树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树;二叉树的子节点分为左子节点和右子节点;以下三种均为二叉树:若该二叉树的所有叶子节点都在最后一层,且节点总数n==\(2^k\)-1,k为层数,则称为满二叉树......
  • 现在告诉你MySQL为什么选择B+Tree呢?
    大家都知道MySQL数据库选择的是B+Tree作为索引的数据结构,那为什么会选择B+Tree呢?本文分四种数据结构来分析:二叉查找树平衡二叉树多路平衡查找树加强版多路平衡查找树(B+Tree)二叉查找树二叉搜索树的特点:左子树的键值小于根的键值,右子树的键值大于根的键值。   从上面的2个图来看......
  • el-tree实现树形结构叶子节点和非叶子节点的区分显示的写法
    需求,非叶子节点显示主题名称+主题下的指标;叶子节点显示代码+名称1、设置prop属性<el-tree:data="dimListTree"ref="dimListTree"row-key="getGroup":props="treeProps":allow-drop="al......
  • 【图文详解】一文全面彻底搞懂HBase、LevelDB、RocksDB等NoSQL背后的存储原理:LSM-tree
    LSM树广泛用于数据存储,例如RocksDB、ApacheAsterixDB、Bigtable、HBase、LevelDB、ApacheAccumulo、SQLite4、Tarantool、WiredTiger、ApacheCassandra、InfluxDB和ScyllaDB等。在这篇文章中,我们将深入探讨LogStructuredMergeTree,又名LSM树:许多高度可扩展的NoSQL分......
  • Ant Design - 组件之 Tree树形控件
    AntDesign-组件之Tree树形控件针对tree树形组件封装了一个树形组件1.组件ui 2.组件名称ThemeCatalog 上面是image目录中的svg3.组件代码index.jsimportReact,{useEffect,useState}from'react';importPropTypesfrom'prop-types';importIcon,{Folde......
  • 关于为element Tree组件实现仿文件夹效果及右键菜单
    <template><divclass="custom-tree-container"@contextmenu.native="handlePaste($event)"><!--<el-tree:data="dataSource"show-checkboxnode-key="id"default-expand-all:expand-on-click-n......