loj2665

题意

loj

做法

下文为方便表示，假定\(\text{bfs}\)序为\(\{1,2,\cdots,n\}\)

定义：令\(dfs_i\)为\(i\)节点的\(\text{dfs}\)序标号，\(pos_i\)为\(\text{dfs}\)序上第\(i\)个点的标号

结论1：对于一种有效的\(\text{bfs}\)分段，其对应恰好一棵树

证明：
考虑构造，遍历段，我们得到若干\(\{(l_i,r_i)\}\)，表示目前还未确定的\((l_i,r_i]\)（\(l_i\)为确定的根）。
然后考虑后面一段，在每个子树，需要保证\(l_i+1\)在该段内，否则不合法。
这样我们构造了一棵树。

推论1：对于一棵能通过\(\text{bfs}\)分段构造出来的树，其与\(\text{bfs}\)分段一一对应

证明：
根据结论1，我们仅需证明两个不同的分段，不会构成一棵相同的树
这显然成立

结论2：对于一种分段\(\{(l_i,r_i)\}\)，其有效，当且仅当满足\(\text{(i)}dfs_{l_i}<dfs_{l_i+1}<\cdots<dfs_{r_i}\)；\(\text{(ii)}dep_{pos_i}+1\ge dep_{pos_{i+1}}\)

证明：
显然这是有效的必要性
如果满足条件，则可以通过结论1的构造方式构造出一棵树

树高显然等价于段数，考虑如何分段

• 若不满足\(dfs_i<dfs_{i+1}\)（即\(dfs_i>dfs_{i+1}\)），则中间必定分一段，这样就满足了结论2中的\(\text{(i)}\)
• 若对于\(\text{dfs}\)序上连续两个点\(pos_i,pos_{i+1}\)，假设其在\(\text{bfs}\)序中不连续（连续的情况在上面处理过了）。
  考虑若满足\(pos_i+1<pos_{i+1}\)，则说明\(dep_{pos_{i+1}}=dep_{pos_i}+1\)
  proof：显然\(dep_{pos_{i}}\le dep_{pos_{i+1}}\)，若\(pos_i\)与\(pos_{i+1}\)深度相等，根据树的性质，必然满足\(pos_{i+1}=pos_i+1\)，其连续与上面假设矛盾，得证。
  那么其必定满足\([pos_{i},pos_{i+1})\)中恰好某点为一段的末端点。

根据结论2，上述已经严格约束了有效性
为方便表示，令\(s_i\)表示\(i\)是否为某一段的末端点，那么将上述条件描述成

• 若\(dfs_i<dfs_{i+1}\)，则\(s_{i}=1\)
• 若对于\(\text{dfs}\)序上连续两个点\(pos_i,pos_{i+1}\)，假设其在\(\text{bfs}\)序中不连续
  则\(\sum\limits_{i=pos_i}^{pos_{i+1}-1}s_i=1\)

在第一种情况中,钦定\(i\)的状态，期望答案+1
在第二种情况中，则为钦定\([pos_i,pos_{i+1}-1)\)中的所有点的\(s\)是确定的
对于未钦定的位置，其\(s_i\)可以是\(0/1\)，故答案+0.5

loj2665

原文：https://www.cnblogs.com/Grice/p/14306160.html