题目比较难读，因为n很小因此可以枚举哪一个点为根节点，计算每对逆序对的贡献（就是概率）
对于一个逆序对产生的贡献，可以看成较大节点先选中的概率，可以用dp预处理求出（u,v）到父节点p的概率
倍增求lca. https://codeforces.com/contest/1541/problem/D

挺难解释。。
倍增求lca 预处理o（n），每次查询o（logn）。

vector<int> mp[maxn];
int f[maxn][20], depth[maxn];
void dfs(int u, int fa)
{
    depth[u] = depth[fa] + 1;
    f[u][0] = fa;
    for (int k = 1; k < 20; k++)
        f[u][k] = f[f[u][k - 1]][k - 1];
    for (auto v : mp[u]) {
        if (v == fa)
            continue;
        dfs(v, u);
    }
}
int lca(int u, int v)
{
    if (depth[u] > depth[v])
        swap(u, v);
    int d = depth[v] - depth[u];
    for (int i = 19; i >= 0; i--) {
        if ((d >> i) & 1)
            v = f[v][i];
    }
    if (u == v)
        return u;
    for (int i = 19; i >= 0; i--) {
        if (f[u][i] != f[v][i])
            u = f[u][i], v = f[v][i];
    }
    return f[u][0];
}

还有一个dp打表题： https://ac.nowcoder.com/acm/contest/18196/I
lkw orz！！
打表代码：

    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    for (int i = 1; i <= 100; i++) {
        for (int j = 1; j <= i; j++) {
            int len1 = j - 1;
            int len2 = dp[i - j];
            dp[i] = min(dp[i], max(len1, len2) + 1);
        }
        cout << i << " " << dp[i] << endl;
    }

～i'm waking up~