「题解」Codeforces 1554E You
do_while_true
·
·
题解
问题可以转化成给每个边定向，a_i 变成了 i 点的入度。
首先考虑定向方案与合法的 a 的双射：每一个定向方式都能唯一确定一个 a；依次考虑叶子的 a，就能确定叶子与其父亲的边的定向方式，之后即可将叶子删掉。不断迭代即可得到定向方案，该定向方案唯一确定的也是原先的 a。所以定向方案可以与合法的 a 组成一组双射。
然后考虑所有的不同的 a 都能被一个删点方案生成：因为给每个点定向必然有个点的入度为 0，从这个点开始删，不断迭代，即可得到一个能够生成这个 a 的合法的删点方案。
所以答案的总和为 2^{n-1}．
入度的总数为 n-1，所以一定只有 n-1 的因数答案才不为 0。
考虑如果 k>1，怎样判断答案是不是 0？叶子是可以直接确定边要往上的，因为不能出现入度为 1，这样可以把叶子删去，删去叶子之后的叶子，挂着它的边也能定向，然后这个叶子也可以删去...这样不断做拓扑排序，即可以构造出一个方案，看这个方案满不满足条件即可。
注意到这个方案数唯一的，所以 k>1 时直接拓扑排序来判断即可。
直接这么做时间复杂度是 \mathcal{O}(n\sqrt n)，有一个显著的优化是如果只判素因子就行，再把判素因子得到的 \gcd 的 ans 加上 1。
```cpp
#include<iostream>
#include<cstdio>
#include<queue>
template <typename T> T Max(T x, T y) { return x > y ? x : y; }
template <typename T> T Min(T x, T y) { return x < y ? x : y; }
template <typename T>
T& read(T& r) {
r = 0; bool w = 0; char ch = getchar();
while(ch < '0' || ch > '9') w = ch == '-' ? 1 : 0, ch = getchar();
while(ch >= '0' && ch <= '9') r = r * 10 + (ch ^ 48), ch = getchar();
return r = w ? -r : r;
}
typedef long long ll;
const ll mod = 998244353;
ll qpow(ll x, ll y) {
ll sumq = 1;
while(y) {
if(y & 1) sumq = sumq * x % mod;
x = x * x % mod;
y >>= 1;
}return sumq;
}
#define int long long
const int N = 1000010;
int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int n, head[N], ent, ans[N], a[N], in[N], in_[N], b[N];
bool vis[N];
struct Edge {
int to, next;
}e[N << 1];
inline void add(int x, int y) {
e[++ent].to = y; e[ent].next = head[x]; head[x] = ent;
}
std::queue<int>q;
int check(int x) {
for(int i = 1; i <= n; ++i) b[i] = a[i] = 0, in[i] = in_[i], vis[i] = 0;
for(int i = 1; i <= n; ++i)
if(in[i] == 1) {
q.push(i);
}
while(!q.empty()) {
int y = q.front();q.pop(); vis[y] = 1;
for(int i = head[y]; i;i = e[i].next) {
int v = e[i].to;
if(vis[v] == 1) continue ;
if(a[y] == 0) ++a[v], a[v] %= x, ++b[v];
else ++a[y], a[y] %= x, ++b[y];
--in[v];
if(in[v] == 1) {
q.push(v);
}
}
}
int g = b[1];
for(int i = 2; i <= n; ++i) g = gcd(g, b[i]);
return g;
}
void solve() {
read(n);
for(int i = 1; i <= n; ++i) ans[i] = in_[i] = 0, head[i] = 0;
ent = 0;
for(int i = 1, u, v; i < n; ++i) read(u), read(v), add(u, v), add(v, u), in_[u]++, in_[v]++;
int m = n-1;
for(int i = 1; i * i <= m; ++i)
if(m % i == 0) {
int t = check(i);
if(t % i == 0) ans[t] = 1;
while(i != 1 && m % i == 0) m /= i;
}
if(m > 1) {
int t = check(m);
if(t % m == 0) ans[t] = 1;
}
ans[1] = qpow(2, n-1);
for(int i = 2; i <= n; ++i) ans[1] -= ans[i];
for(int i = 1; i <= n; ++i) printf("%lld ", ans[i]);
puts("");
}
signed main() {
int T; read(T);
while(T--)
solve();
return 0;
}
```