首页 > 其他分享 >CF622E Ants in leaves 题解

CF622E Ants in leaves 题解

时间:2024-11-10 22:20:58浏览次数:1  
标签:子树 蚂蚁 题解 leaves CF622E 节点

传送门

给定一棵 \(n\) 个节点的树,根节点是 \(1\)。这棵树的每一个叶节点都有一只小蚂蚁。每过 \(1\) 秒钟,可以选择让一些蚂蚁向父节点走一步。注意,两只蚂蚁不能同时在一个除去根节点的节点上。

问这些蚂蚁最少用多少秒的时间,使得所有蚂蚁都走到根节点。


根结点的各个子树独立,因此可以各个子树各自求答案然后取 \(\max\)。

先深搜一遍求深度。对于一颗子树,把所有叶子的深度 \(d\) 存进一个数组 \(a\) 里,从小到大排序。

考虑深度为 \(a_i\) 的这只蚂蚁。

  1. 若 \(a_i>a_{i-1}\),显然前面的蚂蚁都会走在它严格的前面,因此它不会受到任何阻挡,到达根的时间就是 \(a_i\)。

  2. 否则,它会与 \(a_{i-1}\) 这只蚂蚁在某个结点处相遇,它需要等 \(a_{i-1}\) 过去,时间 \(+1\);加了之后,也不会有任何阻挡,到达时间为 \(a_i+1\)。

这样把 \(a\) 依次调整一遍,最大值就是这颗子树的完工时间。

标签:子树,蚂蚁,题解,leaves,CF622E,节点
From: https://www.cnblogs.com/FLY-lai/p/18538637

相关文章

  • ABC372D ABC379F 题解 单调栈二分
    ABC372DABC379F题解单调栈二分一直觉得AT上面学到的东西比CF要多一些,无意捧一踩一,但可能是我太菜的原因,毕竟ABC的题目普遍要比Div.2简单一些。好多次碰到这个单调栈里面二分的trick了,所以写一篇来总结一下。ABC372D形象地给定一系列Buildings的高度\(h\),保证每个......
  • P2123 皇后游戏 / [USACO12JAN] Mountain Climbing S / P1248 加工生产调度 题解
    P2123皇后游戏/[USACO12JAN]MountainClimbingS/P1248加工生产调度先来看P2123。我们把这个特别重要的公式打出来:\[c_{i}=\begin{cases}a_{1}+b_{1}&,i=1\\\displaystyle\max\left\{c_{i-1},\sum_{j=1}^{i}a_{j}\right\}+b_{i}&,2\leqi\leqn\end{......
  • 历年CSP-J初赛真题解析 | 2019年CSP-J初赛完善程序(34-43)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客矩阵变幻有一个奇幻的矩阵,在不停的变幻,其变幻方式为:数字0变成矩阵[......
  • [NOIP2012 提高组] 国王游戏 题解
    [NOIP2012提高组]国王游戏典贪心。设当前点为\(i\),\(\prod_{k=0}^{i-1}a_k\)为\(x\),则对于\(i,j\)两点的答案:(为了方便,记\(i+1=j\))\[\mathit{res}_1=\max\bigg(\dfracx{b_i},\dfrac{xa_i}{b_j}\bigg)~;\]若交换,则:\[\mathit{res}_2=\max\bigg(\dfracx{b_j},\dfrac{......
  • [luogu1248] 加工生产调度 题解
    考虑\(i\)排在\(j\)前的条件是\(a_i+\max(a_j,b_i)+b_j\lea_j+\max(a_i,b_j)+b_i\),然后发现这一坨东西是皇后游戏中的倒数第三个式子,直接转化为\(\min(a_j,b_i)\ge\min(a_i,b_j)\),然后就按皇后游戏中的排序方法就可以了……#include<bits/stdc++.h>#defineintlonglong......
  • [luogu1248] 加工生产调度 题解
    考虑\(i\)排在\(j\)前的条件是\(a_i+\max(a_j,b_i)+b_j\lea_j+\max(a_i,b_j)+b_i\),然后发现这一坨东西是皇后游戏中的倒数第三个式子,直接转化为\(\min(a_j,b_i)\ge\min(a_i,b_j)\),然后就按皇后游戏中的排序方法就可以了……#include<bits/stdc++.h>#defineintlonglong......
  • [luogu1248] 加工生产调度 题解
    考虑\(i\)排在\(j\)前的条件是\(a_i+\max(a_j,b_i)+b_j\lea_j+\max(a_i,b_j)+b_i\),然后发现这一坨东西是皇后游戏中的倒数第三个式子,直接转化为\(\min(a_j,b_i)\ge\min(a_i,b_j)\),然后就按皇后游戏中的排序方法就可以了……#include<bits/stdc++.h>#defineintlonglong......
  • CCPC 网络赛题解(D/I/J)
    D根据题目给出的构造方式,\(S_n'\)的长度会达到\(2^n\)数量级,没法求出\(S_n'\),所以考虑递推。设\(dp_{i,l,r}\)为\(S_i'\)里\(T\)的\([l,r]\)区间以子序列的方式出现了多少次,可以写出转移方程:\(dp_{i,l,r}=\sumdp_{i-1,l,k}\cdotdp_{i-1,k+1,r}+[a_i=T_k]\cdot......
  • [JXOI2017] 加法 题解
    最小值最大,考虑二分答案,问题转为判断最小值是否能\(\gex\)。假如\(a_i\gex\),那我们肯定不管;假如\(a_i<x\),那最好能让选择的区间\(r\)值更大,用优先队列维护即可。区间增幅可以用树状数组维护。时间复杂度\(O(n\log^2n)\)。#include<bits/stdc++.h>#defineintlonglon......
  • [CF1981E] Turtle and Intersected Segments 题解
    好题好题。难点在建图,因为图的边数将会决定最小生成树的时间复杂度。我们肯定希望能够只建\(O(n)\)级别的边,这样时间复杂度就可以做到\(O(n\logn)\)。观察到当\(i,j,k\)三个区间能够互相连边时(这里假设\(a_i<a_j<a_k\)),我们绝对不会连\((i,k)\)这条边。那么假如我们将......