也不算什么难题。。求出所有的置换，再在每个置换中讨论，ans=min(用置换中最小值换所有元素的代价；有全局最小值换置换中最小元素，用全局最小元素换所有元素，再将最小元素换回来),详见代码。。

其实有更方便的作法，但我写的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的父亲。。

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

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