给定一棵 \(n\) 个节点的树,根节点是 \(1\)。这棵树的每一个叶节点都有一只小蚂蚁。每过 \(1\) 秒钟,可以选择让一些蚂蚁向父节点走一步。注意,两只蚂蚁不能同时在一个除去根节点的节点上。
问这些蚂蚁最少用多少秒的时间,使得所有蚂蚁都走到根节点。
根结点的各个子树独立,因此可以各个子树各自求答案然后取 \(\max\)。
先深搜一遍求深度。对于一颗子树,把所有叶子的深度 \(d\) 存进一个数组 \(a\) 里,从小到大排序。
考虑深度为 \(a_i\) 的这只蚂蚁。
-
若 \(a_i>a_{i-1}\),显然前面的蚂蚁都会走在它严格的前面,因此它不会受到任何阻挡,到达根的时间就是 \(a_i\)。
-
否则,它会与 \(a_{i-1}\) 这只蚂蚁在某个结点处相遇,它需要等 \(a_{i-1}\) 过去,时间 \(+1\);加了之后,也不会有任何阻挡,到达时间为 \(a_i+1\)。
这样把 \(a\) 依次调整一遍,最大值就是这颗子树的完工时间。
标签:子树,蚂蚁,题解,leaves,CF622E,节点 From: https://www.cnblogs.com/FLY-lai/p/18538637