51nod2626 未来常数

51nod2626 未来常数

Description

给定一棵树,定义 \(f(u, l, r)\) 为从 \(u\) 开始走过所有编号在 \([l, r]\) 内的点再回到 \(u\) 所需的最小边数。设 \(g(l, r) = \min_{u \in [l, r]} f(u, l, r)\),对于所有 \(1 \le l \le r \le n\)\(g\) 的期望。

\(n \le 10^5\)

Solution

首先一个经典的结论就是 \(g(l, r)\) 是满足其两侧都有编号在 \([l, r]\) 内的边数的两倍。这样我们就可以对于每一条边统计答案了。我们可以对于每一条边统计出它没有贡献的区间有多少个,那需要处理出其子树内和子树外所有连续段的长度。遍历整棵树,使用线段树合并即可,时间复杂度 \(\mathcal{O}(n \log^2 n)\)

51nod2626 未来常数

上一篇:003子选择器


下一篇:从士兵到程序员再到SOHO程序员