题解：P6277 [USACO20OPEN] Circus P

ZnPdCo · 2024-04-08 22:18:41 · 题解

发现交换操作有可传递性：如果 (x,y) 两个位置（注意我们这里是位置而不是指牛）可以互相交换，(y,z) 两个位置也可以互相交换，那么 (x,z) 两个位置必定是可以互相交换的。因为可以先交换 (x,y)，再交换 (y,z)，最后再次交换 (x,y)。

我们发现如果当前如果有 k 头牛，无论它们在哪些位置，我们总是可以移动它们到树上的 1\cdots k 号位置。也就是说，如果忽略标号的话，任意两个状态都是直达的。

所以我们固定这 k 头牛在 1\cdots k 号位置，计算有多少种有标号的排列状态。

假如 (x,y) 两头牛能够在不影响其它牛的情况下交换，我们就给它们连一条边，发现最后面会形成很多个团（完全图）。根据交换操作的可传递性，那么每一个团的情况肯定是可以互相到达的。

我们设这些团大小为 s_i，那么答案就是 \frac{k!}{\prod (s_i!)}。

考虑怎样的情况下两头牛是可以交换的：

首先，我们可以把牛从位置 1\cdots k 移出来到任意位置。

然后在不影响其它牛的情况下交换两头牛。

最后，按照相反的顺序移动回位置 1\cdots k。

此时，两头牛就是可交换的，连一条边。

考虑怎样在不影响其它牛的情况下交换两头牛：

发现当在一条没有牛的链且出现一个分支时，两头牛可以交换：

如上，位置 1 上的牛和位置 6 上的牛交换时，可以在这个没有牛且有一个分支 4 的链 2\to5 上进行交换。先把 1 上的牛移动到 4 上，再把 6 上的牛移动到 1 上，最后把移动到 4 上的牛移动到 6 上。

总结可以交换的规律：

没有牛的链；
有一个分支（有一个位置度数大于二）。

我们将其拓展一下：

在一个中间都是二度点，两端都是非二度点的链上，设两端不包括链的树的大小分别为 a、b，链的长度为 c（它们都包括两端的点）：

如上，1\to8 就是合法的中间都是二度点，两端都是非二度点的链。其中 a=5（位置 1，2，3，4，5 都是左端的树），b=5（位置 8，9，10，11，12 都是右端的树），c=4（位置 1，6，7，8 都是中间的链）。

我们发现，当 k\le(a-1)+(b-1)-1 时，两端的树上的每一个位置都可以互相交换，也就是能到达左端的牛和能到达右端的牛一定可以交换，我们对这两头牛连边。

原理：将 k 头牛任意的移动到两颗树上，留下一个空位置作为交换的分支，然后树上的任意两头牛都可以通过这个分支和没有牛的链进行交换。

总结可以交换的规律：k<(a-1)+(b-1)，也就是 k<n-c。

发现，若 (x,y) 是满足这个条件的一条链，也就是能到达 x 的牛能和能到达 y 的牛交换。以及若 (y,z) 也是满足这个条件的一条链，那么能到达 x 的牛能肯定也能和能到达 z 的牛交换。

也就是说，我们链的两端可以互相连接形成很多个连通块。

我们可以把每个满足交换条件，也就是 k<n-c 的链的两端连接起来，因为可以到达这两个位置中的一个的牛就可以和能到达另一个位置的牛交换，所以说，我们计算能到达这些点的牛的个数，即可得到 s_i，也就是团的大小。

因为当 k 从小到大枚举时，k<n-c 也就是 c<n-k 的边是越来越少的，不好维护。考虑时光倒流，将 k 从大到小枚举时，c<n-k 的边将会越来越多，用并查集即可维护。

回到刚刚那个问题，怎么计算能到达这些点的牛的个数？

正難则反，我们可以计算出无法到达这个连通块的牛的个数，再用牛的总数 k 减去即可。

如果 a_i\to b_i 不是一条满足上面交换条件的链，设连通块外的树的大小为 a_i，连通块内树的大小为 b_i，链的长度为 c_i。

那么我们能够进入到这个联通块的最多只有 b_i-1 头牛，也就是把连通块内树全部填满，那么还有 k-(b_i-1) 的牛无法与之交换。

那么总共的可到达的节点数量为：

\begin{aligned} k-\sum_{a_i\to b_i}(k-(b_i-1)) &= k-\sum_{a_i\to b_i}(k-(n-a_i-(c_i-1))) \\ &= k-\sum_{a_i\to b_i}(k-n+a_i+c_i-1) \\ \end{aligned}

发现 a_i+c_i-1 为“联通块内子树” 外的点减一（c_i 有一端在连通块内），所以设 p_i 为链方向连通块外的点的个数，有：

\begin{aligned} k-\sum_{a_i\to b_i}(k-(b_i-1)) &= k-\sum_{a_i\to b_i}(k-n+p_i+1) \\ &= k-(\sum_{a_i\to b_i}(k-n+1)+\sum_{a_i\to b_i}p_i) \end{aligned}

设连通块大小为 \text{siz}，不合法的 a_i\to b_i 个数为 \text{out}。我们发现子树外的点数和 \sum_{a_i\to b_i}p_i=n-\text{siz}。有：

\begin{aligned} k-\sum_{a_i\to b_i}(k-(b_i-1)) &= k-([\text{out}](k-n+1)+n-[\text{siz}]) \\ &= k-[\text{out}](k-n+1)-n+[\text{siz}] \\ &= ([\text{out}]-1)(n-k-1)+[\text{siz}]-1 \end{aligned}

我们维护一下连通块的 \text{out} 和 \text{siz} 即可。注意在合并的时候，双方的 \text{out} 和 \text{siz} 都会减小！

因为每一次连通块个数等于不合法链的数量加上一，而不合法链只能存活链长的时间，所以均摊之后是 O(n) 的。连通块使用 set 维护。所以时间复杂度为 O(n\log n)。精细实现能够做到更优。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
#define P 1000000007
ll n;
ll deg[N];
ll head[N], nxt[2 * N], to[2 * N], cnt;
ll fa[N], out[N], siz[N];
ll ans[N], fac[N], ifac[N];
set<ll> s;
struct node {
    ll a, b, c;
    node(ll a = 0, ll b = 0, ll c = 0):a(a), b(b), c(c) {}
} edge[N];
ll tot;
void addEdge(ll u, ll v) {
    cnt ++;
    to[cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}
ll find(ll x) {
    if(fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);
}
void merge(ll a, ll b, ll c) {
    a = find(a), b = find(b);
    fa[a] = b;
    siz[b] += siz[a] + c - 2;
    out[b] += out[a] - 2;
    s.erase(a);
}
void dfs(ll u, ll fa, ll rt, ll c) {
    if(deg[u] != 2) {
        if(rt) {
            edge[++ tot] = node(u, rt, c);
        }
        c = 1;
        rt = u;
    }
    for(ll i = head[u]; i; i = nxt[i]) {
        ll v = to[i];
        if(v == fa) continue;
        dfs(v, u, rt, c + 1);
    }
}
ll qpow(ll x, ll y) {
    if(y == 0) return 1;
    if(y % 2 == 1) return x * qpow(x, y - 1) % P;
    ll tmp = qpow(x, y / 2);
    return tmp * tmp % P;
}
int main() {
    scanf("%lld", &n);
    for(ll k = 1; k < n; k ++) {
        ll u, v;
        scanf("%lld %lld", &u, &v);
        addEdge(u, v);
        addEdge(v, u);
        deg[u] ++;
        deg[v] ++;
    }
    for(ll i = 1; i <= n; i ++) {
        if(deg[i] != 2) {
            fa[i] = i;
            siz[i] = 1;
            out[i] = deg[i];
            s.insert(i);
        }
    }
    dfs(*s.begin(), 0, 0, 0);
    sort(edge + 1, edge + 1 + tot, [&](const auto &x, const auto &y) {
        if(x.c == y.c) {
            if(x.a == y.a) return x.b < y.b;
            else return x.a < y.a;
        }
        return x.c < y.c;
    });
    fac[0] = 1;
    for(ll i = 1; i <= n; i ++) {
        fac[i] = fac[i - 1] * i % P;
    }
    ifac[n] = qpow(fac[n], P - 2);
    for(ll i = n; i >= 1; i --) {
        ifac[i - 1] = ifac[i] * i % P;
    }
    ans[n] = fac[n];
    ll pos = 1;
    for(ll k = n - 1; k >= 1; k --) {
        while(pos <= tot && k < n - edge[pos].c) {
            merge(edge[pos].a, edge[pos].b, edge[pos].c);
            pos ++;
        }
        ans[k] = fac[k];
        for(ll i : s) {
            (ans[k] *= ifac[(out[i] - 1) * (n - k - 1) + siz[i] - 1]) %= P;
        }
    }
    for(ll i = 1; i <= n; i ++) {
        printf("%lld\n", ans[i]);
    }
}