2020-2021:teams:manespace:atcoder_beginner_contest_173
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:atcoder_beginner_contest_173 [2020/07/15 14:46] iuiou |
2020-2021:teams:manespace:atcoder_beginner_contest_173 [2020/07/15 14:56] (当前版本) iuiou |
||
|---|---|---|---|
| 行 18: | 行 18: | ||
| =====F Intervals on Tree===== | =====F Intervals on Tree===== | ||
| - | 题意：给定一棵树，定义$f(l,r)(l<r)$为l节点到r节点中所有点在在树中组成的子图中连通块的个数。求$$ | + | 题意：给定一棵树，定义$f(l,r)(l<r)$为$l$节点到$r$节点中所有点在在树中组成的子图中连通块的个数。求$\sum_{l=1}^{l=n}\sum_{r=l}^{r=n}f(l,r)$ |
| + | |||
| + | 题解：其实就是让我们求连通块的个数，有个比较显然的结论，加一条边会让连通块的数量$+1$，而初始的情况一个点就是一个连通块，所以我们可以还原建树的过程来解决这道题。通过找规律，比较容易发现，在l到r建一条边会使总答案减少$l*(n-r+1)$个,之后$O(n)$处理即可。 | ||
2020-2021/teams/manespace/atcoder_beginner_contest_173.1594795584.txt.gz · 最后更改: 2020/07/15 14:46 由 iuiou
