其实有更方便的作法，但我写的hash挂链+树状数组维护。。

太傻叉了。。直接贴代码。。

裸的treedp。。两遍dfs，第一遍求出g[i]表示以i为根的子树的深度和，第二遍求出f[i]表示以i为根的树的深度和。。

g[i]=sigma(g[k])+size[i]-1(k为i的子树),f[i]=f[fa[i]]+n-size[i]*2

size[i]表示以i为根的子树节点数，fa[i]表示i的父亲。。

这题其实是道水题。。平衡树的启发式合并。总的逆序对个数=左子树的+右子树的+左子树与右子树之间的。。

然后暴力合并。。每次合并时计算左右子树间的逆序对，而左右子树的之前已经递归求好了。。这次得了个教训，果然旋转还是比不旋转强= =！