Розв'язок
Від кореня до будь-якої вершини результат побітового AND може лише втрачати одиничні біти. Для всіх некореневих вершин кількість таких бітів має бути однаковою. Позначимо цю кількість через . Якщо n>1, то 1\le k\le m: кожен сусід кореня має додатне значення, а AND на шляху до нього дорівнює саме цьому значенню.
Нехай степінь кореня дорівнює . Оскільки кореню присвоєно 2^m-1, кожен із його сусідів повинен мати рівно одиничних бітів. Для кожного сусіда є \binom{m}{k} незалежних варіантів, тому для всіх сусідів — \binom{m}{k}^{d}.
Розглянемо решту n-1-d вершин. На шляху до батька вже залишилося рівно одиничних бітів. Щоб їхня кількість не зменшилася, число в поточній вершині повинно містити одиниці на цих позиціях. Решта m-k бітів довільні, отже, для кожної такої вершини є 2^{m-k} варіантів. Усі ці вибори незалежні.
Таким чином, для фіксованого кількість розстановок дорівнює
Підсумувавши за всіма , отримаємо
Якщо n=1, відповідь для єдиного кореня дорівнює .
Важливо, що залежить лише від степеня кореня, а не від форми дерева. Тому для вершин з однаковими степенями відповідь обчислюємо тільки один раз.
Оптимізація
Біноміальні коефіцієнти обчислюємо за після підготовки факторіалів та обернених факторіалів:
Для всіх обернених факторіалів достатньо одного піднесення до степеня: спочатку знаходимо (MAXN-1)!^{-1}, а потім рухаємося назад за формулою
Для кожного степеня перебираємо від до . Позначимо q=2^{n-1-d}. Тоді
Цей множник можна підтримувати змінною : початково p=1, а після кожної ітерації p\leftarrow p\cdot q.
Покажемо, що різних степенів лише O(\sqrt n). Для n\ge2 усі степені додатні. Якщо різних степенів , їхня сума не менша за 1+2+\cdots+s=s(s+1)/2. З іншого боку, сума степенів усіх вершин дерева дорівнює 2(n-1). Тому
Отже, замість значень формули достатньо обчислити її для O(\sqrt n) різних степенів. Обчислені відповіді зберігаємо у масиві за степенем вершини.
Складність
Один виклик обчислення перебирає значень і виконує швидке піднесення до степеня на кожній ітерації, тобто займає O(m\log(d+1)) часу. Разом для одного набору даних маємо O(n+m\sqrt n\log n) часу та додаткової пам'яті.
Попередня підготовка факторіалів, обернених факторіалів і степенів двійки виконується один раз за O(MAXN+\log MOD) часу та O(MAXN) пам'яті.
Реалізація C++17
#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();
}