题意：给你两串序列，分别为dfs序和bfs序，让你求树的期望高度。 这题脑洞是真的大。。说实话我都不知道这道题的tag应该是什么。。 copy一下百度文库的题解
我们可以发现，所求的树之所以会有很多种，是因为出现了这种情况： 对于A、B，A既可以做B的兄弟，又可以做B的父亲。 (显然其中的一个前提是A、B在dfs、bfs序列中都必须相邻) 而这样除去A，B的关系外，对于其他任何节点之间的关系都没有任何影响。 所以这中情况对答案的贡献是0.5。 然后对于A，B，如果A只能是B的父亲(也就是BFS序列中的断层)，那么对答案的贡献为1。 所以，我们只要找出来以上两种关系，最后将贡献值加起来就是答案。 所以我们发现，可以通过O(N)来累计树上的答案。 首先设A,B为i，i+1贡献为1时： i=1（根的高度）或者A只能是B的父亲(也就是BFS序列中的断层) 写成表达式就是：（bfs[i]<bfs[i+1])&&(dfs[i]>dfs[i+1])（模拟一下断层就知道） 那好，现在问题就是贡献为0.5时如何计算，这点void copy并没有细讲 贡献为0.5时： 我们先把bfs序换成1-n，那么一个需要被答案加上贡献的A,B两点的情况必须符合下面三个性质： ①:dfs[i+1]=dfs[i]+1; 简单来讲就是dfs&bfs序必须相邻且位置先后一样 ②:dfs时在i+1点的前面点的深度不能超过i+1的深度 具体怎么搞后面会讲 ③:这里比较难描述，我借鉴一下G_word大神的说法： 假设点j为必须断层的点的前一点（该层最后一点） 对于满足 dfs[i+1]<dfs[x]<dfs[j] 的所有x 必须满足 bfs[x]>=bfs[i+1] 就是说可能与i+1同层的点 必须是i+1的兄弟 可能不大好理解 简单解释一下 如果j不是i+1的兄弟，j的老爸的bfs序肯定<bfs[i+1] 第一种情况直接判断即可。 第二种情况，我们可以用一个num[i]表示1-i中的最大深度，那么比较的时候直接进行比较就好了。。 一二种情况合起来我们就可以把这个贡献加上辣！ 第三种情况不符合时，我们不仅不能加，还得把当前积累的答案（是使用临时变量，不是最终答案）全部清零。 优化： 如果每个点都要找到条件2的断层点 就有可能导致n^2的复杂度 再介绍下由 sto AK大神 提供的小优化 可以开个临时的变量累加所有的0.5 如果在断层前遇到某个i和i+1不是兄弟 就把临时变量清0（第三种情况） 遇到断层时ans+=临时变量 还有就是情况2不能直接做，得需要用线段树进行处理，维护bfs序的区间最小值，然后对于第三种情况才可以直接计算。 如果不用线段树，是可以过官方数据的， 但NB的AK大神，轻松地构造了一个数据把没使用线段树的卡了（听G_word大神说的。。）： uses math; type node=record l,r,val:longint; end; var tr:array[0..800000]of node; a,b,dfs,bfs,num,ls,rs:array[0..800000]of longint; ans,ans1:extended; i,j,n,m,dfn:longint; procedure build(l,r:longint); var i,j,m:longint; x:longint; begin inc(dfn); x:=dfn; tr[x].l:=l; tr[x].r:=r; if l=r then begin tr[x].val:=a[l]; exit; end; m:=(l+r)div 2; ls[x]:=dfn+1; build(l,m); //build(x+x,l,m); rs[x]:=dfn+1; build(m+1,r); //build(x+x+1,m+1,r); tr[x].val:=min(tr[ls[x]].val,tr[rs[x]].val); end; function find(x,l,r:longint):longint; var m:longint; begin if (tr[x].l>=l)and(tr[x].r<=r)then exit(tr[x].val); m:=(tr[x].l+tr[x].r)div 2; find:=n; if l<=m then find:=min(find(ls[x],l,r),find); if r>m then find:=min(find(rs[x],l,r),find); end; begin readln(n); for i:=1 to n do read(a[i]); for i:=1 to n do read(b[i]); for i:=1 to n do bfs[b[i]]:=i; for i:=1 to n do a[i]:=bfs[a[i]]; for i:=1 to n do begin dfs[a[i]]:=i; if a[i]>num[i-1] then num[i]:=a[i] else num[i]:=num[i-1]; end; ans:=1; ans1:=0; dfn:=0; build(1,n); for i:=1 to n-1 do begin if (i=1)or(dfs[i]>dfs[i+1])then ans:=ans+ans1+1 else if dfs[i+1]=dfs[i]+1 then begin if num[dfs[i]]<=i+1 then ans1:=ans1+0.5; end else if find(1,dfs[i],dfs[i+1])<i then ans1:=0; end; ans:=ans+ans1; writeln(ans:0:3); end.