题目
给你一颗n个结点的树，需要执行n次以下操作：
- 选择一个未被删除结点u，令(a_u)等于与u相邻未被删除的结点数。
- 将结点u从树中删除
也就是说，n次操作完后可以得到一个序列(a={a_1,a_2,...,a_n})。问在所有可能的序列(a)中，满足以下条件：
- 序列(a)可以由上述n次操作得到
- (gcd(a_1,...,a_n)=k)
的序列有多少个？
输出(k=1,2,...,n)的答案。
题解
考虑删点顺序很麻烦，换成考虑边的贡献。对于一条边((u,v))，如果先删除点(u)，边对(u)有贡献1；如果先删的是点(v)，边对(v)有贡献1。因此，每条边贡献的一种分配对应一种删除操作生成的序列，这也说明所有可能的生成的序列有(2^{n-1})个。
设(f_k)代表有多少生成的序列满足其中每个元素都可以被(k)整数。
显然，(f_1=2^{n-1})。
对于(k>1)，可以用以下方法构造一个方案：
- 以1为根构造有根树，自底向上构造。
- 假设(u)的子树的结点都已经分配好满足整除(k)，对于和(u)相连的边没被如果没被分配给子结点必然就要分配给(u)结点。假设当前分配给(u)结点的的值为(t)。
- 如果(t)可以被(k)整除，什么完成(u)的分配；
- 否则只能从(u)和父结点相连的边获得一个贡献，得到(t+1)。如果(t+1)都不能被(k)整除，那么必定无解，否则完成分配。
从构造方法可得，对于(k>1)，(f_k=0或1)。
计算所有(f_k)的时间复杂度为(O(n^2))。又可以发现，对于(k)不整除(n-1)，(f_k=0)。因为(sum{a_i}=n-1)，如果(k|a_i)，那么有(k|n)。所以只需要检查(n)的所有因子即可。故时间复杂度为(O(nsigma_0(n)))。
最后(h_k)为答案，有(h_k=sum_limits{i=1}^{lfloorfrac{n}{k} floor}{mu(i)f_{i cdot k}})，总时间复杂度为(O(nlogn+nsigma_0(n)))。
#include <bits/stdc++.h>
#define endl '
'
#define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mp make_pair
#define seteps(N) fixed << setprecision(N)
typedef long long ll;
using namespace std;
/*-----------------------------------------------------------------*/
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
#define INF 0x3f3f3f3f
const int N = 3e5 + 10;
const int M = 998244353;
const double eps = 1e-5;
vector<int> np[N];
ll f[N], h[N], val[N];
inline ll qpow(ll a, ll b, ll m) {
ll res = 1;
while(b) {
if(b & 1) res = (res * a) % m;
a = (a * a) % m;
b = b >> 1;
}
return res;
}
bool dfs(int p, int fa, int k) {
int d = 0;
val[p] = 0;
for(int nt : np[p]) {
if(nt == fa) continue;
if(!dfs(nt, p, k)) return false;
d++;
}
val[p] += d;
if(val[p] % k != 0) {
if(p == 1 || (val[p] + 1) % k != 0) return false;
else {
val[fa]--;
val[p]++;
}
}
return true;
}
int pri[N], mu[N], cnt;
bool isnp[N];
int main() {
IOS;
mu[1] = 1;
for(int i = 2; i < N; i++) {
if(!isnp[i]) {
pri[cnt++] = i;
mu[i] = -1;
}
for(int j = 0; j < cnt && i * pri[j] < N; j++) {
isnp[i * pri[j]] = 1;
if(i % pri[j] == 0) {
mu[i * pri[j]] = 0;
break;
}
mu[i * pri[j]] = -mu[i];
}
}
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
np[i].clear();
f[i] = h[i] = 0;
}
for(int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
np[u].push_back(v);
np[v].push_back(u);
}
vector<int> d;
for(int i = 1; i * i <= n - 1; i++) {
if((n - 1) % i == 0) {
d.push_back(i);
if((n - 1) / i != i) d.push_back((n - 1) / i);
}
}
f[1] = qpow(2, n - 1, M);
for(int i = 1; i < d.size(); i++) {
f[d[i]] = dfs(1, 0, d[i]);
}
for(int i = 1; i <= n; i++) {
h[i] = f[i];
for(int j = 2; j <= n / i; j++) {
h[i] = (h[i] + mu[j] * f[i * j] + M) % M;
}
cout << h[i] << "
"[i == n];
}
}
}