AND on a Tree Again#13124

AND on a Tree Again (Editorial)

Solution

On the path from the root to any vertex, the result of bitwise AND can only lose set bits. The number of set bits must be the same for all non-root vertices. Let this number be . If n>1, then 1\le k\le m: every neighbor of the root is assigned a positive number, and the AND along the path to that neighbor is exactly this number.

Let the degree of the root be . Since the root is assigned 2^m-1, each of its neighbors must have exactly set bits. There are \binom{m}{k} independent choices for each neighbor, giving \binom{m}{k}^{d} possibilities for all neighbors.

Now consider the remaining n-1-d vertices. On the path to the parent of each such vertex, exactly set bits remain. To prevent their number from decreasing, the number assigned to the current vertex must have set bits at all these positions. The remaining m-k bits can be chosen arbitrarily, giving 2^{m-k} possibilities for each vertex. All these choices are independent.

Therefore, for a fixed , the number of valid assignments is

\binom{m}{k}^{d}\cdot 2^{(m-k)(n-1-d)}.

Summing over all possible values of , we obtain

\boxed{F(d)=\sum_{k=1}^{m}\binom{m}{k}^{d}\cdot 2^{(m-k)(n-1-d)}} \pmod{998244353}.

If n=1, the answer for the only possible root is .

Notice that depends only on the degree of the root, not on the structure of the tree. Therefore, we only need to compute the answer once for vertices with the same degree.

Optimization

We can calculate binomial coefficients in time after precomputing factorials and inverse factorials:

\binom{m}{k}=m!\,(k!)^{-1}\,((m-k)!)^{-1} \pmod{998244353}.

To compute all inverse factorials, only one modular exponentiation is needed. First, we calculate (MAXN-1)!^{-1}, then iterate backwards using

((i-1)!)^{-1}=i\,(i!)^{-1}\pmod{998244353}.

For each degree , we iterate over from down to . Let q=2^{n-1-d}. Then

2^{(m-k)(n-1-d)}=q^{m-k}.

We can maintain this factor using a variable : initially p=1, and after each iteration we update p\leftarrow p\cdot q.

Let us show that there are only O(\sqrt n) distinct degrees. For n\ge2, all vertex degrees are positive. If there are distinct degrees, their sum is at least 1+2+\cdots+s=s(s+1)/2. On the other hand, the sum of all vertex degrees in a tree equals 2(n-1). Therefore,

\frac{s(s+1)}{2}\le2(n-1), \qquad s=O(\sqrt n).

Thus, instead of evaluating the formula for all vertices, we only need to evaluate it for O(\sqrt n) distinct degrees. We store the computed answers in an array indexed by vertex degree.

Complexity

A single evaluation of iterates over values of and performs binary exponentiation with exponent in each iteration, taking O(m\log(d+1)) time. Therefore, the total time complexity per test case is O(n+m\sqrt n\log n), with auxiliary space.

The factorials, inverse factorials, and powers of two are precomputed once in O(MAXN+\log MOD) time using O(MAXN) space.

C++17 Implementation

#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int maxn = 1e5 + 10;

int fact[maxn], inv_fact[maxn], pw2[maxn];

int binpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return res;
}

void precalc() {
    fact[0] = pw2[0] = 1;
    for (int i = 1; i < maxn; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
        pw2[i] = 2LL * pw2[i - 1] % mod;
    }

    inv_fact[maxn - 1] = binpow(fact[maxn - 1], mod - 2);
    for (int i = maxn - 1; i >= 1; i--)
        inv_fact[i - 1] = 1LL * inv_fact[i] * i % mod;
}

int C(int n, int k) {
    int res = 1LL * fact[n] * inv_fact[k] % mod;
    return 1LL * res * inv_fact[n - k] % mod;
}

int calc(int n, int m, int d) {
    if (n == 1) return 1;

    int ans = 0, p = 1;
    int q = pw2[n - 1 - d];

    for (int k = m; k >= 1; k--) {
        int cur = 1LL * binpow(C(m, k), d) * p % mod;
        ans = (ans + cur) % mod;
        p = 1LL * p * q % mod;
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> deg(n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        deg[u]++;
        deg[v]++;
    }

    vector<int> seen(n, -1);
    for (int i = 0; i < n; i++) {
        int d = deg[i];
        if (seen[d] == -1) seen[d] = calc(n, m, d);
        cout << seen[d] << " \n"[i == n - 1];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precalc();

    int t;
    cin >> t;
    while (t--) solve();
}