Tree to Prufer Sequence

• Find the leaf node with the smallest label, and add its parent to the sequence.
• Delete that leaf node.
• Repeat the above operations until a sequence of length (n-2) is obtained.

The reverse process reconstructs the tree.

A Prufer sequence establishes a bijection between the spanning trees of a complete graph with (n) vertices and sequences of length (n-2) with values in ([1,n]).

Template: P6086 [Template] Prüfer Sequence

int f[N], p[N], d[N];
void Prufer() {
    for (int i = 1; i < n; i++) {
        f[i] = read();
        d[f[i]]++;
    }
    for (int i = 1, j = 1; i <= n - 2; i++, j++) {
        while (d[j]) j++;
        p[i] = f[j];
        while (i <= n - 2 && !(--d[p[i]]) && p[i] < j) {
            p[i + 1] = f[p[i]];
            i++;
        }
    }
}
void Tree() {
    for (int i = 1; i <= n - 2; i++) {
        p[i] = read();
        d[p[i]]++;
    }
    p[n - 1] = n;
    for (int i = 1, j = 1; i < n; i++, j++) {
        while (d[j]) j++;
        f[j] = p[i];
        while (i < n && !(--d[p[i]]) && p[i] < j) {
            f[p[i]] = p[i + 1];
            i++;
        }
    }
}

Simple Properties

• The Prufer sequence corresponds one-to-one with unrooted trees.
• The frequency of a vertex in the Prufer sequence equals its degree minus 1.
• The number of spanning trees of a complete graph with (n) vertices is (n^{n-2}). (The Prufer sequence length is (n-2), each position has (n) possibilities.)
• For a given degree sequence (d_{1\ldots n}), the number of distinct unrooted trees is (\displaystyle\frac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}). This follows from the formula for permutations with repetition.

Problem P2290 [HNOI2004] Tree Counting

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> d[i];
        all += d[i] - 1;
    }
    if (n == 1) {
        printf("%d\n", !d[1]);
        return 0;
    }
    if (all != n - 2) {
        puts("0");
        return 0;
    }
    for (int i = 1, sum = n - 2; i <= n; i++) {
        ans *= C[sum][d[i] - 1];
        sum -= d[i] - 1;
    }
    printf("%lld\n", ans);
}

Problem P2624 [HNOI2008] Mingming's Trouble

Some degrees are unspecified. (1 \le n \le 1000). Let (k) be the number of vertices with known degrees, and (s = \sum (d_i - 1)) over those vertices. The answer is:

[ \binom{n-2}{s} \cdot \frac{s!}{\prod_{i=1}^{k}(d_i-1)!} \cdot (n-k)^{n-2-s} ]

Equivalently:

[ \frac{A_{n-2}^{s} \cdot (n-k)^{n-2-s}}{\prod_{i=1}^{k}(d_i-1)!} ]

This requires high-precision arithmetic. An operator provided by a classmate for big integers:

struct BigInt {
    vector<long long> digits;
};
BigInt operator * (const BigInt& A, const BigInt& B) {
    int l1 = A.digits.size(), l2 = B.digits.size();
    int l3 = l1 + l2 - 1;
    BigInt C;
    C.digits.resize(l1 + l2 - 1);
    for (int i = 0; i < l1; i++)
        for (int j = 0; j < l2; j++)
            C.digits[i + j] += A.digits[i] * B.digits[j];
    for (int i = 0; i < l3; i++) {
        if (i != l3 - 1) 
            C.digits[i + 1] += C.digits[i] / 10;
        else if (C.digits[i] / 10) {
            C.digits.push_back(C.digits[i] / 10);
            l3++;
        }
        C.digits[i] %= 10;
    }
    return C;
}

Using this, we can solve the problem by prime factorization and multiplication. Be careful with implementation details.

Problem: Clues

Given a labeled undirected graph with (k) connected components, count the number of ways to add (k-1) edges to make the graph connected, modulo (p).

(1 \le n, m \le 10^5), (1 \le p \le 10^9).

Contract each component in to a single vertex. Let component (i) have size (s_i) and final degree (d_i).

The number of Prufer sequences is (\displaystyle\frac{(k-2)!}{\prod_{i=1}^{k}(d_i-1)!}). To account for the internal choices of wich vertex within each component connects to the outside, multiply by (\displaystyle\prod_{i=1}^{k}s_i^{d_i}).

Set (e_i = d_i - 1). Then we sum over all assignments of (e_i) with sum (k-2):

[ \sum_{\sum e_i = k-2} \binom{k-2}{e_1, e_2, \dots, e_k} \cdot \prod_{i=1}^{k} s_i^{e_i+1} ]

By the multinomial theorem, this equals:

[ (s_1 + \dots + s_k)^{k-2} \cdot \prod_{i=1}^{k} s_i ]

Since (s_1 + \dots + s_k = n), the final answer is:

[ n^{k-2} \cdot \prod_{i=1}^{k} s_i ]

We can maintain (k) and the sizes (s_i) using a union-find data structure.

Problem P5437 [XR-2] Agreement

Given a complete undirected graph with (n) vertices, the edge wieght between (i) and (j) is ((i+j)^k). Find the expected total weight of a uniformly random spanning tree, modulo (998244353).

(1 \le n \le 998244352), (1 \le k \le 10^7).

There are (n^{n-2}) spanning trees, each with (n-1) edges, so total edge appearances across all trees is ((n-1)n^{n-2}). Since the complete graph has (\frac{n(n-1)}{2}) edges, each specific edge appears in (\frac{(n-1)n^{n-2}}{n(n-1)/2} = 2n^{n-3}) trees.

Therefore, the expected total weight is:

[ \frac{2n^{n-3}}{n^{n-2}} \sum_{1 \le i < j \le n} (i+j)^k = \frac{2}{n} \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} (i+j)^k ]

Define:

[ a_n = \sum_{i=1}^{n-1} \sum_{j=i+1}^{n} (i+j)^k ]

Then:

[ a_n - a_{n-1} = \sum_{i=n+1}^{2n-1} i^k ]

One can observe that (a_n) is a polynomial in (n) of degree (k+2). We can compute the first (k+3) terms and then use interpolation to find (a_n) in (O(k)) time.

To optimize the inversion step in Lagrange interpolation (avoiding (O(k \log P)) inversions), we can use the "batch inverse" technique:

Given an array (a_1, a_2, ..., a_n), let (A = \prod a_i). Compute (A^{-1}), then each inverse is (a_i^{-1} = A^{-1} \cdot \prod_{j \ne i} a_j). Precompute prefix and suffix products.

The final answer is (\frac{2}{n} \cdot a_n) modulo (998244353). Time complexity (O(k)).

Implementation sketch:

void init() {
    f[1] = fac[0] = 1;
    for (int i = 2; i < (R << 1); i++) {
        if (!vis[i]) {
            p[++cnt] = i;
            f[i] = qpow(i, k);
        }
        for (int j = 1; j <= cnt && i * p[j] < (R << 1); j++) {
            vis[i * p[j]] = true;
            f[i * p[j]] = 1ll * f[i] * f[p[j]] % MOD;
            if (i % p[j] == 0) break;
        }
    }
    for (int i = 1; i < (R << 1); i++)
        (f[i] += f[i - 1]) %= MOD;
    for (int i = 1; i <= R; i++) {
        a[i] = ((a[i - 1] + f[i * 2 - 1] - f[i]) % MOD + MOD) % MOD;
        fac[i] = 1ll * fac[i - 1] * i % MOD;
    }
}

int b[2 * N], suf[2 * N], tot;
int calc(int n) {
    if (n <= R) return a[n];
    int A = 1, ret = 0, r1, r2;
    for (int i = 1; i <= R; i++) {
        A = 1ll * A * (n - i) % MOD;
        b[++tot] = n - i;
        int invDenom = 1ll * fac[i - 1] * fac[R - i] % MOD;
        b[++tot] = (((R - i) & 1) ? MOD - invDenom : invDenom) % MOD;
    }
    suf[tot + 1] = 1;
    for (int i = tot; i; i--)
        suf[i] = 1ll * suf[i + 1] * b[i] % MOD;
    int invSuf = qpow(suf[1], MOD - 2);
    for (int i = 1, pref = 1, tp; i <= tot; i++) {
        tp = b[i];
        b[i] = 1ll * invSuf * suf[i + 1] % MOD * pref % MOD;
        pref = 1ll * pref * tp % MOD;
    }
    for (int i = 1; i <= R; i++) {
        r1 = 1ll * A * b[2 * i - 1] % MOD;
        r2 = b[2 * i];
        (ret += 1ll * a[i] * r1 % MOD * r2 % MOD) %= MOD;
    }
    return ret;
}

int main() {
    R = k + 3;
    init();
    ans = 2ll * calc(n) % MOD * qpow(n, MOD - 2) % MOD;
    // output ans
    return 0;
}