CF1540B Tree Array 题解

题目链接：Tree Array

题意：

给定一棵 \(n\) 个节点的树。

对于这棵树，我们通过下列方法来生成一个序列：

等概率选择这 \(n\) 个节点中的一个节点，并对这个节点打上标记（初始时没有节点被打上标记）

在所有没被打上标记且与至少一个打上标记的节点相连的节点中等概率选择一个节点并对这个节点打上标记

重复步骤 2 直到所有节点都被打上标记，此时生成的序列就是所有节点编号按照节点被打上标记的时间排序后的形成的序列。

求生成序列的期望逆序对数对 \(10^9+7\) 取模后的值。

输入：树；输出：答案

数据范围：

\(2\leq n\leq200\) ，保证给出的是棵树

首先可以发现，这个标记的过程和第一个点息息相关

考虑枚举第一个被标记的点，然后把它提成根节点。

那么现在所有的点对

是祖先关系的，一定会产生贡献 \(0/1\) 的贡献。
不是祖先关系的，当他们的 LCA 被加入后，接下来的任何标记都可以解释为：

两个栈， \(p\) 概率弹第一个栈栈顶，\(p\) 概率弹第二个栈栈顶，\(1-2p\) 概率啥也不干，问第一个栈先空的概率。

模型中两个栈就是 \(x\) 和 \(y\) 分别到 LCA 的距离，那么仅考虑 \((x,y)\) 他们的 \(p=\frac{1}{2}\) （相互独立+期望线性性）

这个可以dp预处理出来，设两个栈分别有 \(i,j\) 个元素时第一个栈先空的概率为 \(f(i,j)\) ，那么 \[ f(i,0)=0,~f(0,j)=1 \quad(i,j > 0) \\[6pt]f(i,j) = \frac{1}{2}(f(i-1,j)+f(i,j-1)) \]

于是我们只需要对每个根节点跑一遍处理一下 LCA，然后暴力枚举点对就好了

时间复杂度 \(\mathcal{O}(n^3\log n)\) ，写 Tarjan 的话就是 \(\mathcal{O}(n^3)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7, inv2 = 500000004;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define N ((int)(255))

vector<int> vec[N];
int res, fa[N][20], dp[N][N], dep[N];
int qpow(int a, int b)
{
    int r = 1;
    for(; b; b >>= 1, a = a * a % mod)
        if(b & 1) r = r * a % mod;
    return r;
}
void dfs(int u, int Fa)
{
    fa[u][0] = Fa; dep[u] = dep[Fa] + 1;
    for(int i = 1; i < 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for(int v : vec[u]) if(v != Fa) dfs(v, u);
}
int LCA(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 19; ~i; i--)
        if(dep[x] - (1 << i) >= dep[y]) x = fa[x][i];
    if(x == y) return x;
    for(int i = 19; ~i; i--)
        if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    for(int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        vec[u].push_back(v); vec[v].push_back(u);
    }
    for(int i = 1; i <= n; i++) dp[0][i] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) * inv2 % mod;
    for(int i = 1; i <= n; i++)
    {
        dfs(i, 0);
        for(int j = 1; j <= n; j++)
            for(int k = 1; k < j; k++)
            {
                int d = LCA(j, k);
                add(res, dp[dep[j] - dep[d]][dep[k] - dep[d]]);
            }
    }
    cout << res * qpow(n, mod - 2) % mod << '\n';
    return 0;
}