noi2013树的计数.docVIP

[noi2013]树的计数 题解 被这题虐了好久……本来是看这题解，然后晕乎乎的，没怎么看懂……然后YGW巨神质疑那个程序，于是就举出了一个反例……(rzO Orz)。于是本蒟蒻就顺着那个题解的思路和YGW的反例弄出了一种奇葩的方法…… 我们在BFS序上分割，分出每一层。这样一种分割方案对应一种树的形态。 其实，分割方案会有不同，原因在于存在某些点，他们既可以做与他相邻的点的儿子，也可以做兄弟。那么他们对ans的贡献是0.5。而那些只能做儿子的点就只能被分配到下一层，所以对ans的贡献是1.0；其它的点对分层方案没有影响，对ans就没有贡献。于是关键在于如何找到这些点。 我们把BFS序编为1..n，以此重标号DFS序。 我们从1到n遍历BFS序，根据dfs序一个一个判断。 考虑那些既可以做兄弟也可以做儿子的点。 这些点必须满足既可以做兄弟也可以做儿子（废话- -）。 可以发现，那些点刚好在BFS和DFS序都是连续的。但是这还不够。我们还必须满足这个点可以分配到下一层（因为如果可以被分配到下一层就可以做兄弟）。于是考虑两个情况： 　　1.下一层有一个点的BFS序当前点。 　　2.当前层有一个点的BFS序当前点，且这个点必须在当前层。（注：有一种情况存在一个点的BFS序当前点，但是不一定要在当前层，这种情况不影响当前点的分配方案。） 这两个情况下当前点都只能被分配到当前层。 　　第一种等价于dfs序当前点的点中存在一个bfs序当前点的点。（可以用前缀最值判断） 　　第二种等价于在dfs序中这个点的到前一个点之间有一个bfs序当前点，这相当于限制了当前点与前一个点不是同一个点的儿子。（可以用线段树判断，否则要n^2，完全可以构造数据卡掉，如bfs:1 2 3 4 5 6 7 8 ... dfs:1 3 5 7 ... 2 4 6 8 ...） 　　当排除了上面两种情况后，当前点就可以放到下面去。且把当前点放到下面去对后面所有的点的分配是没有影响的，这样保证了正确性。 考虑那些只能做儿子的点。 这种情况只出现在当前点的dfs序上一个点的dfs序。 最后贴一下卡掉那个代码的数据和我的代码 9 1 2 4 5 6 7 9 8 3 1 2 3 4 5 6 7 8 9 /************************************************************** ????Problem: 3244 ????User: lazycal ????Language: C++ ????Result: Accepted ????Time:292 ms ????Memory:7056 kb ****************************************************************/ ?? #include cstdio #include algorithm const int N = 200000 + 9; int Max[N],Min[N*4],rk[N],dfs[N],bfs[N],n; void build(const int idx,const int l,const int r) { ????if (l == r) return (void)(Min[idx] = dfs[l]); ????build(idx * 2,l,(l+r)/2); ????build(idx*2+1,(l+r)/2+1,r); ????Min[idx] = std::min(Min[idx*2],Min[idx*2+1]); } int MIN(const int idx,const int l,const int r,const int L,const int R) { ????if (L = l r = R) return Min[idx]; ????int mid = (l + r)/2,res = 0x7fffffff; ????if (L = mid) res = std::min(res,MIN(idx * 2,l,mid,L,R)); ????if (mid R) res = std::min(res,MIN(idx*2+1,mid+1,r,L,R)); ????return res; } int main() { ????#ifndef ONLINE_JUDGE ????freopen(3244.in,r,stdin); ????freopen(3244.out,w,stdout); ????#endif ????scanf(%d,n); ????for (int i = 1; i = n; ++i) { ????????scanf(%d,dfs + i); ????