首先要明确，对于一个结点，其儿子的遍历顺序是确定的，在 DFS 序和 BFS 序中相同。
而 BFS 序更容易确定一棵树的深度，只需要知道在哪些结点分了层。
所以可以通过 DFS 序来确定 BFS 中的分层方案。
然后分类讨论：
- \(BFS_u+1=BFS_v\)，\(DFS_u>DFS_v\)，相差恰好一层。若同层则说明 DFS 先进入了 \(v\) 所在的子树，BFS 必然也先遍历到 \(v\) 点，不合法，所以必定分层，平均贡献为 \(1\)。
- \(BFS_u+1=BFS_v\)，\(DFS_u<DFS_v\)，此时存在两种情况均可以发生：
- \(u\) 没有儿子，\(v\) 是 \(u\) 的兄弟。
- \(u\) 是 \(v\) 的父亲，\(u\) 是它所在层最后遍历到的结点，\(v\) 是它所在层最先遍历到的结点。换句话说就是 \(u\) 所在层的其它结点都没有儿子了。
这两种情况 BFS 序中之后结点分布条件完全相同，即对后面无影响，可选任意一种，平均贡献为 \(0.5\)。
刚刚我们对 BFS 中相邻的结点进行了是否分层的讨论，而 DFS 序的约束其实我们没有考虑完全：
- \(DFS_u+1=DFS_v\)，\(BFS_u>BFS_v\)，\(u\) 是 \(y\) 前面一个兄弟的子树内最后一个 DFS 到的结点，此时 \(v\) 的深度只要比 \(u\) 浅即可。但我们并不需要去进行限制，因为按 BFS 序正常做中间肯定有地方会分层。
- \(DFS_u+1=DFS_v\)，\(BFS_u<BFS_v\)，\(BFS\) 序中在 \(u\) 和 \(v\) 中间的结点肯定是前一部分与 \(u\) 深度相同，后一部分与 \(v\) 深度相同。如果 \(BFS_u+1<BFS_v\)，和上面同理，肯定有恰好一个地方会强制产生分层（否则就不合法了），而剩下那些可分可不分的就一定不能分，这里需要进行一个限制，用差分实现。
相邻结点的讨论已经足够完备了。
标签：结点,遍历,所在,NOI2013,DFS,BFS,计数,分层,P1232 From： https://www.cnblogs.com/landsol/p/17802249.html