「解题报告」P6277 [USACO20OPEN] Circus P

· · 题解

首先容易发现每种等价类的大小一定是相等的，那么最后答案就一定是 \frac{k!}{size}，size 表示等价类的大小。

我们考虑两头牛之间能不能交换，发现这种关系是具有传递性的，那么交换的关系图一定会形成若干个团，一个团之间是可以任意交换的。那么最后答案就是 \frac{k!}{\prod s_i!}，其中 s_i 表示每个团的大小。

我们考虑什么时候能交换，容易想到一种简单的交换就是在一个度数为三的点上去换。这是一个最基本的交换，只要在任意一个度数大于等于 3 且存在至少两个空位的情况下就可以在这里进行交换。

而整棵树由若干关键点划分成了若干条链，我们考虑一条由两个关键点连起来的一条链上能否进行交换。我们设两端两个关键点的子树大小分别为 a, b，中间的链长为 c，其中两个端点同时包含在链与子树内，显然有 (a - 1) + (b - 1) + c = n。

首先考虑到我们的问题是能够使得两头牛交换且不改变其它牛的位置，但是不改变其它牛的位置这个限制实际上是没有意义的，因为如果某一刻能够使得两头牛交换位置，那么我们再按照一模一样的移动倒着就能把其它所有牛全部还原回去，所以我们实际上只用考虑某一刻能否将考虑的两头牛交换即可。

那么我们考虑链上两头相邻的牛能否交换。直观的想法肯定是让这两个点左边的牛全部往左边的子树里填，右边的牛全部往右边的子树里填，这样这两头牛可以去任意一个关键点的地方去调换位置。而子树内可以包含的牛是有限的，注意到如果左右两棵子树全都填满了，那么此时这两头牛就不能交换了，这时一定有 k \ge (a - 1) + (b - 1)，而由此我们又可以推出，存在恰好 k - (a - 1) - (b - 1) 头牛之间是不能交换位置的，而这会导致此时左边的任何点都无法与右边的任何点进行交。

如果 k < (a - 1) + (b - 1)，那么说明将所有的牛全部填入子树后，一定存在一棵子树里至少有一个空。考虑链上相邻的两头牛，如果将这两头牛的左边所有牛全部填入左子树，右边所有牛全部填入右子树，那么可以发现存在一个子树至少有两个空，而通过这两个空我们就可以完成这两个点的交换了，也就是说，当 k < (a - 1) + (b - 1) 时，我们可以交换链上任意两头牛的位置。

总结一下，对于一条链，如果 k \ge (a - 1) + (b - 1)，那么存在一些牛不能互相交换，同时这些牛将左右两个集合分开，使得左右两个集合之间也不能交换。这在交换的关系图上意味着，左右两个集合不可能在同一个团内。而 k < (a - 1) + (b - 1) 时，链上的任意两个点之间都是可以交换的，这说明只要能移动到这条链上的点都是可互相交换的，这在交换的关系图上意味着，左右两个集合是在同一个团内的。

这时候问题就清晰了许多了。我们称满足 k < (a - 1) + (b - 1) 的链为合法链，那么整个交换关系图，是由若干条不合法链划分成的若干个团，而合法链将关键点连成了若干个连通块，每个连通块对应着一个团。那么，我们就只需要求出每个团的大小，就能计算出答案了。

首先链合法的条件可以改写成 k < n - c，即 n - k > c，那么发现如果我们将 k 从大往小枚举，则会依次加入每一条合法链，然后使用并查集即可维护关键点形成的连通块。那么现在问题在于，如何计算出每个连通块对应的团的大小。

团的大小并不好计算，但是我们是容易计算团外面的点数的，于是简单容斥一步就可以了。对于团外面的点数，我们考虑连通块往外连的每一条不合法链，设连通块外的子树为 a，连通块内的子树为 b，那么我们让所有的牛全部填满子树 b，则多出来的点就是这条不合法链方向的不在连通块内的点，这些点的数量等于 k - (b - 1) = k - (n - c - (a - 1)) = k - n + c + a - 1 = k - n + 1 + p，其中 p 为不合法链方向的关键点子树大小。将所有的出边求和，容易发现，\sum p = n - x，其中 x 为关键点连成的连通块点数，于是总和就是 n - x + y(k - n + 1)，拿 k 减去它就是团的点数，即 (y - 1)(n - k - 1) + x - 1。但是这个式子里面跟 k 有关系，也就是每个连通块的权值一直在变，这导致我们并不能 O(1) 维护出所有连通块的权值乘积了。但是实际上我们可以直接枚举每一个连通块进行计算答案，因为连通块数量等于不合法链的数量加一，而不合法链存在的时间等于链长，链长总和是 O(n) 的，所以每一时刻下连通块数量的总和也是 O(n) 的。于是我们可以拿链表或者 set 维护所有的连通块，每次遍历所有连通块计算答案即可。时间复杂度 O(n \log n) 或 O(n \alpha(n))。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, P = 1000000007;
int n;
vector<int> e[MAXN];
set<int> s;
int fa[MAXN], out[MAXN], siz[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
void merge(int u, int v, int w) {
    u = find(u), v = find(v);
    fa[u] = v, siz[v] += siz[u] + w - 2, out[v] += out[u] - 2;
    s.erase(u);
}
vector<tuple<int, int, int>> ed;
void dfs(int u, int pre, int rt, int dep) {
    if (e[u].size() != 2) {
        if (rt) ed.push_back({ dep, rt, u });
        rt = u, dep = 1;
    }
    for (int v : e[u]) if (v != pre) dfs(v, u, rt, dep + 1);
}
int qpow(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) ans = 1ll * ans * a % P;
        a = 1ll * a * a % P;
        b >>= 1;
    }
    return ans;
}
int fac[MAXN], inv[MAXN];
int ans[MAXN];
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v; scanf("%d%d", &u, &v);
        e[u].push_back(v), e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) if (e[i].size() != 2) s.insert(i), fa[i] = i, out[i] = e[i].size(), siz[i] = 1;
    dfs(*s.begin(), 0, 0, 1);
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = 1ll * i * fac[i - 1] % P;
    inv[n] = qpow(fac[n], P - 2);
    for (int i = n; i >= 1; i--) inv[i - 1] = 1ll * inv[i] * i % P;
    ans[n] = fac[n];
    sort(ed.begin(), ed.end());
    auto it = ed.begin();
    for (int k = n - 1; k >= 1; k--) {
        while (it != ed.end() && k < n - get<0>(*it)) merge(get<1>(*it), get<2>(*it), get<0>(*it)), it++;
        ans[k] = fac[k];
        for (int i : s) ans[k] = 1ll * ans[k] * inv[(n - 1 - k) * (out[i] - 1) + siz[i] - 1] % P;
    }
    for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
    return 0;
}